Topolojik Sıralama

Question

benim kitabında verilen topolojik sıralama için aşağıdaki algoritmayı düşünün: Ben algoritma sözcüğü kelimesine uygulamak çalıştı ama grafik asiklik olup ya da her zaman, bir dicycle şikayet bulundu

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" 

değil. Sonra, son 2 hattın doğru şekilde uymadığını keşfettim. S boş olduğunda, while döngüsünden hemen önce çıkar. Yani, her seferinde, koşulun doğru olup olmayacağı garanti edilir.

Bir diskotek için uygun şekilde denetlemek için bu algoritmayı nasıl düzeltebilirim?

Düzenleme:

Halen, ben sadece sonunda i değerini kontrol ederek, S sorunu süpürgelik ediyorum:

if i != n + 1 
    return "G has a dicycle" 

Answer 1

Kişisel düzeltme doğrudur. Grafikteki tüm düğümleri S'a zorlamadıysanız grafik, en az bir tane güçlü bağlanmış bileşen içerir. Başka bir deyişle, bir döngünüz var.