考虑我教科书中给出的拓扑排序算法:
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"
我尝试逐字实现该算法,但发现它总是抱怨出现了一个环路,无论图形是否为非循环。然后,我发现最后两行不正确。紧接在其前面的 while 循环在 S 为空时立即退出。所以,每次可以确保 if 条件将成立。
如何纠正此算法以正确检查循环?
编辑:
目前,我只是通过在结尾检查 i 的值来规避 S 问题:
if i != n + 1
return "G has a dicycle"