algorithm - 打印(不检测)循环与拓扑排序

Question

这是数据结构和算法分析第 3 版中的一个问题，我们的其中一个考试中也提出了这个问题。 写下一个算法，对由邻接表表示的图进行拓扑排序，修改 如果找到，算法会打印出一个循环。首先，说明一下你的想法 句子。 (不要使用深度优先搜索，我们只想修改基本拓扑 排序。)

答案是: 如果没有顶点的入度为 0，我们可以通过向后追踪顶点来找到一个循环 正入度；由于回溯上的每个顶点都有正入度，我们最终 两次到达一个顶点，环就找到了。

追溯部分没看懂，“追溯”是什么意思，不知道这个答案的伪代码会是怎样？感谢任何帮助。

Answer 1

Kahns 算法的工作原理是选择入度为 0 的节点，并删除其所有出边(这可能会产生入度为 0 的新节点)。如果没有找到更多的入度为 0 的节点(并且图现在不为空)，则它包含一个循环。

要打印循环，从任何地方开始，然后跟随传入的边缘。由于节点的数量是有限的，所以在某些时候你必须第二次到达一个节点。这是您的周期，要打印它，只需再运行一次。

假设我们的图是:

a --> b
b --> c, d
c --> b

这个图的反转是

a <-- 
b <-- a, c
c <-- b
d <-- b

拓扑排序以a开始, 删除它。 b现在是 b <-- c

现在我们从任何地方开始，比如说，d并向后搜索。

d <-- b <-- c <-- b

自从我们看到b之前，它必须是循环的一部分。要打印，我们再次点击链接并获得 b <-- c <-- b .

如果有任何死胡同 - 例如 a - 它会在检测到循环之前就已经被拓扑排序算法删除。