Trier topologiques

Question

Tenir compte l'algorithme suivant pour le tri topologique dans mon livre:

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" 

J'ai essayé la mise en œuvre du mot pour mot algorithme, mais trouvé qu'il se plaignait toujours d'un dicycle, si le graphique est acyclique ou ne pas. Ensuite, j'ai découvert que les 2 dernières lignes ne rentraient pas correctement. La boucle while immédiatement avant la sortie se termine lorsque S est vide. Donc, à chaque fois, il est assuré que la condition if sera vraie.

Comment puis-je corriger cet algorithme pour vérifier correctement un dicycle?

Edit:

Actuellement, je suis tout simplement le problème longe S, en vérifiant la valeur de i à la fin:

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

Answer 1

Votre solution est correcte. Si vous n'avez pas poussé tous les nœuds du graphique sur S, le graphique contient au moins un composant fortement connecté. En d'autres termes, vous avez un cycle.