拓扑排序
考虑一下我的教科书中给出的以下拓扑排序算法：
Input: A digraph G with n vertices
Output: A topological ordering v1,v2...vn of G, or the non-existence thereof.
S is an empty stack
for each vertex u in G do
incount(u) = indeg(u)
if incount(u) == 0 then
S.push(u)
i = 1
while S is non-empty do
u = S.pop()
set u as the i-th vertex vi
i ++
for each vertex w forming the directed edge (u,w) do
incount(w) --
if incount(w) == 0 then
S.push(w)
if S is empty then
return "G has a dicycle"
我尝试逐字实现该算法，但发现它总是抱怨双循环，无论图是否是非循环的。然后，我发现最后两行不正确。当 S 为空时，紧邻其之前的 while 循环将退出。因此，每次都能确保 if 条件成立。
我怎样才能纠正这个算法以正确检查双轮车？
编辑：
目前，我只是通过检查最后 i 的值来绕过 S 问题：
if i != n + 1
return "G has a dicycle"
Consider the following algorithm for topological sort given in my textbook:
Input: A digraph G with n vertices
Output: A topological ordering v1,v2...vn of G, or the non-existence thereof.
S is an empty stack
for each vertex u in G do
incount(u) = indeg(u)
if incount(u) == 0 then
S.push(u)
i = 1
while S is non-empty do
u = S.pop()
set u as the i-th vertex vi
i ++
for each vertex w forming the directed edge (u,w) do
incount(w) --
if incount(w) == 0 then
S.push(w)
if S is empty then
return "G has a dicycle"
I tried implementing the algorithm word-for-word but found that it always complained of a dicycle, whether the graph was acyclic or not. Then, I discovered that the last 2 lines don't fit in correctly. The while loop immediately prior to it exits when S is empty. So, each time, it is assured that the if condition will hold true.
How can I correct this algorithm to properly check for a dicycle?
Edit:
Presently, I'm simply skirting the S problem, by checking the value of i at the end:
if i != n + 1
return "G has a dicycle"
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
您的修复是正确的。如果您没有将图中的所有节点推送到
S上，则该图至少包含一个强连通分量。换句话说，你有一个循环。Your fix is correct. If you didn't push all the nodes in the graph onto
S, the graph contains at least one strongly connected component. In other words, you have a cycle.