Então estou lendo o Algorithms 4th ed de Robert Sedgewick. livro e os métodos para encontrar um ciclo em um grafo direcionado é diferente daquele para encontrar um ciclo em um grafo não direcionado.

Aqui está um código de exemplo para encontrar um ciclo em um gráfico não direcionado

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

No entanto, ao tentar encontrar um ciclo em um grafo direcionado, o Sedgewick usa uma matriz booleana onde o elemento de ith dessa matriz é verdadeiro se o vértice i foi examinado durante a pilha de chamadas atual. Para cada vértice K examinado, verificamos se o elemento Kth da matriz booleana é verdadeiro. Se for, então temos um ciclo. Minha pergunta é: por que é necessário usar esse array booleano para um gráfico direcionado? A abordagem que acabei de mencionar não deveria ser mais eficiente em termos de memória? E essa abordagem funciona apenas para gráficos não direcionados? porque?