拓扑排序

Question

请考虑我的教科书中给出的以下拓扑排序算法:

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"

Answer 1

你的修复是正确的.如果未将图中的所有节点都推入S,则该图包含至少一个强连接组件.换句话说,你有一个周期.