topologico Ordina

Question

Si consideri il seguente algoritmo per topologico sorta dato nel mio libro di testo:

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" 

ho provato attuare l'algoritmo parola per parola, ma ho trovato che si lamentava sempre di un dicycle, se il grafico è aciclico o non. Poi, ho scoperto che le ultime 2 righe non si adattano correttamente. Il ciclo while immediatamente precedente alla sua uscita quando S è vuoto. Quindi, ogni volta, è assicurato che la condizione if rimarrà vera.

Come posso correggere questo algoritmo per controllare correttamente un ciclo?

Edit:

Attualmente, sto semplicemente costeggiando il problema S, controllando il valore dei alla fine:

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

Answer 1

il fix è corretto. Se non hai spinto tutti i nodi nel grafico su S, il grafico contiene almeno un componente fortemente connesso. In altre parole, hai un ciclo.