c++ - 使用 Boost Graph 搜索 DAG Graph？

Question

我需要搜索一个 DAG 图，但我不想在看到所有其他具有指向它的定向链接的节点之前前进到一个节点。

是否有现有算法来处理这种特殊情况，深度优先搜索和呼吸优先搜索不适用于这种遍历顺序。

即:

A -> B
B -> C
C -> D
A -> C

我不想在看到 B 和 C 之前到达 D。

Answer 1

您正在寻找的是 Kahn (1962) 的拓扑排序算法。这不是当前在 BGL 中实现的拓扑排序算法，它是基于 DFS 的，访问所有顶点，并以反向拓扑顺序输出结果，而是与 BFS 非常相似，并且完全按照您在您的描述中描述的方式访问顶点第一段。您必须自己编写遍历，但算法很简单。

参见拓扑排序维基百科条目中列出的第一个算法:http://en.wikipedia.org/wiki/Topological_sorting .另请参阅 Sedgewick 的“C 中的算法”中的程序 19.8。

提示 1:使用辅助数据结构来维护每个顶点的入边数，实际上不要执行“从图中删除边”部分。

提示 2:对于工作的 GPLV3 示例，您可以在我的 CoFlo 控制流图生成和分析项目中查看 Kahn 算法的实现，特别是文件 topological_visit_kahn.h，此处:http://coflo.svn.sourceforge.net/viewvc/coflo/trunk/src/controlflowgraph/topological_visit_kahn.h?view=log