c – 提升图的遍历显示“隐藏”节点

#include <boostgraphadjacency_list.hpp>
#include <boostgraphdepth_first_search.hpp>
#include <iostream>

typedef boost::adjacency_list<boost::listS,boost::vecS,boost::undirectedS> GraphType;
typedef boost::graph_traits<GraphType>::vertex_descriptor VertexType;

class VertexVisitor : public boost::default_dfs_visitor
{
public:
  void discover_vertex(VertexType v,GraphType g)
  {
    std::cout << v << std::endl;
  }
};

int main() 
{ 
  GraphType g;
  boost::add_edge(1,2,g);
  boost::add_edge(1,3,g);
  boost::add_edge(2,4,g);
  boost::add_edge(4,5,g);

  VertexVisitor vis;
  boost::depth_first_search(g,boost::visitor(vis));

  return 0;
}

这个的输出是

0
1
2
3
4
5

但是0来自哪里,我从未添加过它？这是某种虚拟节点吗？但如果是这样,为什么它会在遍历中被访问,我怎样才能达到预期的行为呢？

编辑1：尝试之后,PlasmaHH建议,并通过我发现的增强代码调试,boost :: add_edge调用图的顶点结构的调整大小.因此,搜索算法添加和访问了更多元素,尽管它们彼此不相连.顺便说一句：我正在使用boost 1.47.

编辑2：已经表明,depth_first_search的行为(除了它的原生差异)与breadth_first_search算法不同,因为DFS遍历图中的所有节点,即使它们没有连接.我无法看到它的好处,因为我只是想找到一个从一个节点到另一个节点的路径,这个路径连接到这个节点,但没问题.如前所述,我的问题的解决方案是使用BFS算法,该算法不遍历所有子图.对于那些感兴趣的人,我添加了一个小例子：

#include <boostgraphadjacency_list.hpp>
#include <boostgraphdepth_first_search.hpp>
#include <boostgraphbreadth_first_search.hpp>
#include <iostream>

typedef boost::adjacency_list<boost::listS,boost::undirectedS>  GraphType;
typedef boost::graph_traits<GraphType>::vertex_descriptor VertexType;

class DFSVertexVisitor : public boost::default_dfs_visitor
{
public:
  void discover_vertex(GraphType::vertex_descriptor v,GraphType g)
  {
    std::cout << v << std::endl;
  }
};

class BFSVertexVisitor : public boost::default_bfs_visitor
{
public:
  void discover_vertex(GraphType::vertex_descriptor v,GraphType g)
  {
    std::cout << v << std::endl;
  }
};


int main(int argc,char *argv[])
{
  GraphType g;
  boost::add_edge(1,g);

  std::cout << "Performing BFS" << std::endl;
  BFSVertexVisitor bfsVisitor;
  boost::breadth_first_search(g,boost::vertex(1,g),boost::visitor(bfsVisitor));

  std::cout << "Performing DFS" << std::endl;
  DFSVertexVisitor dfsVisitor;
  boost::depth_first_search(g,boost::visitor(dfsVisitor).root_vertex(1));

  return 0;
}

注意,节点4和5没有连接到节点1,2和3！

输出：

Performing BFS
1
2
3
Performing DFS
1
2
3
0
4
5

编辑3：我不得不重新思考.我与add_edge连接的数字不是节点本身,只是它们的索引只是建议的n.m.因此,添加边缘并不是我认为的最终解决方案,因为删除其中一个顶点不会按预期工作.