Finden eines Zyklus in einem ungerichteten Graph vs Finden eines in einem gerichteten Graph

Question

So lese ich Robert Sedgewicks Algorithmen 4. Ausgabe. Buch und die Methoden zum Finden eines Zyklus in einem gerichteten Graph ist anders als die zum Finden eines Zyklus in einem ungerichteten Graphen.

Hier ist Beispielcode einen Zyklus in einem ungerichteten Graphen

public class Cycle { 
    public boolean[] marked; 
    public boolean hasCycle; 

    public Cycle(Graph G) { 
     marked = new boolean[G.V()]; // G.V() is the number of vertices in the graph G 
     for (int s = 0; s < G.V(); ++s) { 
     if (!marked[s]) 
      dfs(G, s, s); 
     } 
    } 

    private void dfs(Graph G, int v, int u) { 
     marked[v] = true; 
     for (int w : G.adj(v)) //iterate through vertices adjacent to v 
     if (!marked[w]) 
      dfs(G, w, v) 
     else if (w != u) hasCycle= true; 
    } 

    public boolean hasCycle() { 
     return hasCycle; 
    } 
} 

jedoch zu finden, wenn einen Zyklus in einem gerichteten Graphen zu finden versuchen, Sedgewick ein boolean-Array verwendet, wo das i-te Element des Arrays ist wahr wenn der i-te Knoten während des aktuellen Aufruf-Stacks untersucht wurde. Für jeden untersuchten Knoten K prüfen wir, ob das K-te Element des Booleschen Arrays wahr ist. Wenn es so ist, haben wir einen Zyklus. Meine Frage ist, warum es notwendig ist, dieses boolesche Array für einen gerichteten Graphen zu verwenden. Sollte der Ansatz, den ich gerade aufgeführt habe, nicht speichereffizienter sein? Und funktioniert dieser Ansatz nur für ungerichtete Graphen? Warum?

Answer 1

Sie können nicht den gleichen Algorithmus verwenden: Der obige Algorithmus untersucht einfach alle verbundenen Komponenten des Graphen. Wenn Sie einen bereits markierten Eckpunkt treffen, müssen zwei verschiedene Pfade zu erreichen, und in einem ungerichteten Graphen muss ein Zyklus sein. Wenn nicht, können Sie mit der nächsten verbundenen Komponente fortfahren - Sie müssen die gerade fertiggestellte Komponente nicht mehr bereinigen.

Auf der anderen Seite, wenn Sie ein gerichteten Graphen haben, zwei verschiedene Wege zum gleichen Vertex keinen Zyklus machen. Sie benötigen also einen anderen Algorithmus (z. B. müssen Sie möglicherweise alle Schritte rückgängig machen, die Sie zurückverfolgen.)