印刷（未检测）周期拓扑排序 [英] Printing(not detecting) cycle with topological sort

问题描述

这是一个数据结构与算法分析第三版这还要求我们考试的一个问题。 写下一个算法，拓扑排序邻接表psented图再$ P $，修改 这样，该算法打印出一个周期，如果它被找到。首先，解释了一些自己的想法 句子。 （请勿使用深度优先搜索，我们希望的基本拓扑的只是修改 排序。）

This is a question in a Data Structures and Algorithm Analysis 3rd edition which was also asked in one of our exams. Write down an algorithm to topologically sort a graph represented by an adjacency list, modified such that the algorithm prints out a cycle, if it is found. First, explain your idea in a few sentences. (Don’t use depth first search, we want just a modification of the basic topological sort.)

答案是： 如果没有顶点有入度为0，我们可以通过顶点跟踪向后找到一个循环 正入度;由于在追溯每个顶点具有积极的入度，我们最终 达到顶点两次，并且循环已发现

And the answer is: If no vertex has indegree 0, we can find a cycle by tracing backwards through vertices with positive indegree; since every vertex on the trace back has a positive indegree, we eventually reach a vertex twice, and the cycle has been found.

我不明白的部分跟踪back.What它通过追溯的意思是，我不知道怎么会变成这样回答的伪code会？鸭preciate任何帮助。

I didn't understand the part tracing back.What does it mean by "tracing back", and I wonder how would the pseudocode of this answer would be?. Appreciate any help.

推荐答案

Kahns算法通过选择具有入度0的节点，并删除所有出边（这可能会产生与入度0新节点）。如果发现入度0的没有更多的节点（与图形不为空现在），它包含了一个周期。

Kahns algorithm works by choosing a node with indegree 0, and removing all its outgoing edges (which may produce new nodes with indegree 0). If no more nodes of indegree 0 are found (and the graph is not empty now), it contains a cycle.

要打印的周期，从任何地方开始，并按照传入的边缘。既然有节点的有限数，在某些时候，你必须达到一个节点的第二时间。这是你的周期，将其打印出来，只要运行它另一个时间。

To print the cycle, start anywhere, and follow the incoming edges. Since there is a finite number of nodes, at some point you have to reach a node the second time. This is your cycle, to print it, just run it another time.

说我们的图是：

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

该图的反转则是

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

拓扑排序始于 A ，删除它。 B 现在 B＆LT; - ç

Topological sort starts with a, removes it. b now is b <-- c

现在我们开始的任何地方，比方说， D 键，向后搜索。

Now we start anywhere, say, d and search backwards.

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

既然我们已经看到 B 之前，它必须是循环的一部分。要打印，我们再次按照链接，并获得 B＆LT; - C＆LT; - B

Since we've seen b before, it must be part of the cycle. To print, we follow the links again and get b <-- c <-- b.

如果有任何死胡同 - 如 A - 它会一直在拓扑排序算法已经之前检测周期删除

If there were any dead end - such as a - it would have been removed by the topological sort algorithm already prior to detecting the cycle.

这篇关于印刷（未检测）周期拓扑排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！