带拓扑排序的打印（不检测）循环
这是《数据结构与算法分析》第三版中的一个问题，在我们的一次考试中也被问到。 写出一种算法，对由邻接表表示的图进行拓扑排序，并进行修改 如果找到的话，算法会打印出一个循环。首先，用几句话解释一下你的想法 句子。 （不要使用深度优先搜索，我们只想对基本拓扑进行修改 排序。）
答案是： 如果没有顶点的入度为 0，我们可以通过向后追踪顶点来找到循环： 正入度；由于回溯上的每个顶点都有正入度，我们最终 两次到达一个顶点，就找到了环路。
我不明白追溯的部分。“追溯”是什么意思，我想知道这个答案的伪代码会是什么样？感谢任何帮助。
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.)
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.
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.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
Kahns 算法的工作原理是选择一个入度为 0 的节点，并删除其所有出边（这可能会产生入度为 0 的新节点）。如果找不到更多入度为 0 的节点（并且图现在不为空），则它包含一个循环。
要打印循环，请从任意位置开始，然后沿着传入边缘进行打印。由于节点数量有限，因此在某个时刻您必须第二次到达某个节点。这是你的循环，要打印它，只需再运行一次即可。
假设我们的图是：
该图的反转，则
拓扑排序以
a开头，将其删除。b现在是b <-- c现在我们从任意位置开始，比如
d并向后搜索。由于我们之前见过
b，它一定是循环的一部分。要打印，我们再次点击链接并得到b <-- c <-- b。如果存在任何死胡同 - 例如
a- 它会在检测循环之前被拓扑排序算法删除。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.
Say our graph is:
inversion of this graph then is
Topological sort starts with
a, removes it.bnow isb <-- cNow we start anywhere, say,
dand search backwards.Since we've seen
bbefore, it must be part of the cycle. To print, we follow the links again and getb <-- c <-- b.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.完成拓扑排序过程后（即选择入度为0的顶点，将其删除，将其子入度减1，然后重复该过程），如果假设还有一些顶点需要探索，我们可以' t 找到任何入度为 0 的顶点，这意味着我们在由剩余的未探索顶点形成的子图中存在一个循环，因为在 DAG 中必须至少有一个入度为 0 的顶点。然后从这些剩下的顶点中拾取一个顶点，沿着图追踪，直到到达起始顶点，这就是循环。
After completing the process of topological sorting( i.e., selecting a vertex with in-degree 0, removing it, decreasing its children indegree by 1, then repeat the process), if suppose there are still some vertices left to be explored and we can't find any vertex with in-degree 0, this means that we have a cycle in the subgraph formed by leftover unexplored vertices since in a DAG there must be at least one vertex with in-degree 0. We then pick-up a vertex from these left-over vertices, trace around the graph until you reach the starting vertex, this is the cycle.