Détection de cycle dans un graphe orienté utilisant DFS basé sur la pile

Question

En dessous de l'algo est défaillant après l'exception de dépassement de pile. S'il vous plaît laissez-moi savoir comment puis-je le corriger pour la détection de cycle dans Directed Graph ou si possible quelqu'un peut fournir algo basé sur la pile au lieu de la récursivité.

public boolean hasCycle(Graphnode<T> n) { 

    n.setMark(IN_PROGRESS); 

    for (Graphnode<T> m : n.getSuccessors()) { 
     if (m.getMark() == IN_PROGRESS) { 
      return true; 
     } 

     if (m.getMark() != DONE) { 
      if (hasCycle(m)) { 
       return true; 
       } 
     } 
    } 

    n.setMark(DONE); 

    return false; 
} 

Merci, Vikrant

Answer 1

Je n'ai pas fait ce genre de choses depuis longtemps, mais votre code semble bizarre. Votre première condition si est:

if (m.getMark() == IN_PROGRESS) { 

return true; 
} 

Je pense qu'il devrait être plutôt:

if (m.getMark() == IN_DONE) { 

return true; 
} 

Sinon, quelle est la différence entre m.getMark() == IN_PROGRESS et m.getMark() != DONE? Votre deuxième if-condition n'est jamais déclenchée.

Remarque: Si vous passez par SO, vous trouverez de nombreux algorithmes utilisant DFS ou des piles ...