增強圖庫：防止DFS訪問未連接的節點

Question

我有一個雙向圖。某些頂點未連接。我使用boost :: depth_first_search來遍歷頂點。我也提供起始源節點。我看到連接的節點完成後，也會處理未連接的頂點。我怎樣才能防止訪問這樣的節點？事實上，我如何告訴DFS只訪問那些從源節點可到達的節點，而不訪問其他任何東西？

我有以下代碼：

/// Define vertex properties. 
struct NodeProperty 
{ 
    unsigned  id;    /// Id. 
    unsigned  kind;   /// Kind. 
    unsigned  depth;   /// Depth. 
    unsigned  layer_color;  /// Layer color. 
    unsigned  signal_color; /// Signal color. 
    unsigned  sch_color;  /// Sch color. 
    CBoundingBox bounds;   /// Bounds of polygon. 

    NodeProperty() 
     : id(0), kind(0), depth(0), layer_color(0), signal_color(0), sch_color(0), bounds(0,0,0,0) 
    { 
     ; 
    } 
}; 
/// Define net topology graph. 
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, NodeProperty> Graph; 

class receiver_visitor : public boost::default_dfs_visitor 
{ 
    public: 
     receiver_visitor(std::vector<Vertex>& r) 
      : res(r) 
     { 
      ; 
     } 

     void discover_vertex(Vertex v, Graph const& g) const 
     { 
      std::cout << "Visit: " << v << std::endl; 
      if (g[v].sch_color) { 
       res.push_back(g[v].sch_color); 
      } 
     } 

     std::vector<Vertex>& res; 
}; 

std::vector<std::size_t> 
NetTopology::getReceivers(std::size_t src) const 
{ 
    std::vector<Vertex> r; 
    receiver_visitor vis(r); 
    boost::depth_first_search(data_->g, boost::visitor(vis).root_vertex(src)); 

    return r; 
} 

Answer 1

你想用depth_first_visit，不depth_first_search。