遍历boost图时显示“隐藏”的节点

Question

遍历boost图时显示“隐藏”的节点

4

我开始尝试使用boost图形类。为此，我创建了一个简单的示例，如下所示。当通过深度优先搜索算法遍历图形时，出现了一个我没有添加的节点。以下是代码：

#include <boost\graph\adjacency_list.hpp>
#include <boost\graph\depth_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,3,g);
  boost::add_edge(1,4,g);
  boost::add_edge(4,5,g);

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

  return 0;
}

这个的输出结果是：

但是0是从哪里来的，我从未添加过它？这是一种虚拟节点吗？但如果是这样，为什么在遍历时会访问它，如何实现所需的行为？

编辑1：在尝试了PlasmaHH建议并调试了boost代码后，我发现boost :: add_edge调用了图的顶点结构的调整大小。因此，更多的元素被添加并被搜索算法访问，尽管它们彼此没有连接。顺便说一句：我正在使用boost 1.47。

编辑2：已经证明，depth_first_search除了本质上的区别之外，与breadth_first_search算法不同，因为DFS遍历图中的所有节点，即使它们没有连接。我看不到其中的好处，因为我只想找到一个与此连接的节点到另一个节点的路径，但没关系。如前所述，解决我的问题的方法是使用BFS算法，它不会遍历所有子图。对于那些感兴趣的人，我添加了一个小例子：

#include <boost\graph\adjacency_list.hpp>
#include <boost\graph\depth_first_search.hpp>
#include <boost\graph\breadth_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 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, 2, g);
  boost::add_edge(2, 3, g);
  boost::add_edge(1, 3, g);
  boost::add_edge(4, 5, 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所建议的那样。因此，仅仅添加边不是最终解决方案，因为删除其中一个顶点并不能按预期工作。

- AquilaRapax

我对boost图没有经验，但我注意到当尝试这个测试用例（顺便恭喜你创建了一个！）时，不需要添加超过第一条边就可以得到一个0节点。但是当在0,1处添加一条边时，只有0,1。所以我尝试只在8,9处添加一条边，然后我从0到9都有了。也许这样会有所帮助。 - PlasmaHH

这确实非常奇怪，但感谢您的提示。我会对此进行更多的调查。 - AquilaRapax

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- n. m. · Accepted Answer

来自文档：

如果图的VertexList是vecS，则可以通过vertex_index_t属性的属性映射访问内置顶点索引。这些索引落在[0，num_vertices(g))范围内，并且是连续的。当删除顶点时，调整索引以保留这些属性。

我认为文档没有明确说明 vertex_descriptor 只是索引。文档中的一些示例表明这确实是情况。其他示例将 vertex_descriptor 视为一个黑盒子。