topológica Ordenar

Question

Considere el siguiente algoritmo para la clasificación topológica dado en mi libro de texto:

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" 

Probé la implementación de la palabra por palabra algoritmo, pero encontré que siempre se quejaba de un diciclo, si la gráfica era acíclico o no. Luego, descubrí que las últimas 2 líneas no encajan correctamente. El ciclo while inmediatamente anterior sale cuando S está vacío. Entonces, cada vez, se asegura que la condición if será verdadera.

¿Cómo puedo corregir este algoritmo para verificar correctamente un diciclo?

Editar:

Actualmente, estoy simplemente bordeando el problema S, comprobando el valor de i al final:

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

Answer 1

Su solución es correcta. Si no empujó todos los nodos en el gráfico en S, el gráfico contiene al menos un componente fuertemente conectado. En otras palabras, tienes un ciclo.