Also lese ich Robert Sedgewicks Algorithmen 4. Aufl. Buch und die Methoden zum Auffinden eines Zyklus in einem gerichteten Graphen unterscheiden sich von denen zum Auffinden eines Zyklus in einem ungerichteten Graphen.

Hier ist ein Beispielcode, um einen Zyklus in einem ungerichteten Diagramm zu finden

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;
   }
}

Wenn Sedgewick jedoch versucht, einen Zyklus in einem gerichteten Graphen zu finden, verwendet er ein boolesches Array, bei dem das i-te Element dieses Arrays wahr ist, wenn der i-te Scheitelpunkt während des aktuellen Aufrufstapels untersucht wurde. Für jeden untersuchten Vertex K prüfen wir, ob das K-te Element des Booleschen Arrays wahr ist. Wenn ja, dann 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 Diagramme? Warum?