Encontrar un ciclo en un gráfico no dirigido versus encontrar uno en un gráfico dirigido

Así que estoy leyendo Algorithms de Robert Sedgewick, 4ª ed. El libro y los métodos para encontrar un ciclo en un gráfico dirigido son diferentes a los de encontrar un ciclo en un gráfico no dirigido.

Aquí está el código de ejemplo para encontrar un ciclo en un gráfico no dirigido

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

Sin embargo, al tratar de encontrar un ciclo en un gráfico dirigido, Sedgewick utiliza una matriz booleana en la que el elemento iith de esa matriz es verdadero si el vértice ith se ha examinado durante la pila de llamadas actual. Para cada vértice K examinado, verificamos si el elemento Kth de la matriz booleana es verdadero. Si es así, entonces tenemos un ciclo. Mi pregunta es, ¿por qué es necesario usar esa matriz booleana para un gráfico dirigido? ¿No debería ser más eficiente la memoria el enfoque que acabo de enumerar? ¿Y este enfoque solo funciona para gráficos no dirigidos? ¿por qué?

Respuestas a la pregunta(1)

Su respuesta a la pregunta