4

我开始尝试增强图形类。为此,我创建了一个简单的示例,如下所示。通过深度优先搜索算法遍历图形时,我没有添加一个节点。这是代码:

#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
2
3
4
5

但是 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不是节点本身,而只是它们的索引,如 nm 刚刚建议的那样。因此,仅添加边并不是我认为的最终解决方案,因为删除其中一个顶点不能按预期工作。

4

1 回答 1

2

从文档中:

如果图的 VertexList 是 vecS,则图具有通过 vertex_index_t 属性的属性映射访问的内置顶点索引。索引在 [0, num_vertices(g)) 范围内并且是连续的。当一个顶点被删除时,索引会被调整,以便它们保留这些属性。

我不认为文档明确说明这vertex_descriptor只是索引。文档中的一些示例表明情况确实如此。其他示例被vertex_descriptor视为黑匣子。

于 2012-07-13T15:01:46.647 回答