2

我有一个由邻接表表示的图。我为它应用 depth_first_visit 算法。一切正常。问题是该算法只访问与我的起点顶点相连的顶点。如果我有单独的顶点（没有任何连接），则不会遍历它们。当然，我已经通过找到未访问的顶点然后从它们开始算法来解决这个问题，但是在文档中写道，那些“分离的”顶点也应该被遍历。问题 - 我做错了什么吗？

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, Vertex, Edge > GraphType;

vector<default_color_type> color_map(num_vertices(m_graph));

depth_first_visit(
       m_graph,
       *vp.first,
       custom_dfs_visitor(m_currentPath, visited),
       make_iterator_property_map(
           color_map.begin(),
           get(vertex_index, m_graph),
           color_map[0]),
       Terminator(m_currentPath)
    );
4

2 回答 2

1

“如果一个图是断开连接的，DFS 不会访问它的所有顶点。有关详细信息，请参阅查找连通分量算法。” 参考：算法专家

你没有做错什么。您的修复（查找其他未访问的节点，并再次启动算法）是其他实现所做的。

作为进一步可见的证据，请查看TimL 页面上的这个出色的实现。您可以继续单击并观看正在执行的 DFS。（向下滚动到页面中间。）

于 2013-06-05T23:15:21.723 回答
1

看起来您的算法是正确的，因为这本质上是 DFS 所做的：它遍历所有连接的节点，这意味着您需要分别在每个连接的组件上运行它。根据您的用例，您可能需要研究用于查找连接组件的算法，这些算法利用某种 DFS 或 BFS 算法。

于 2013-06-05T23:21:31.650 回答