Więc czytam Algorithms Roberta Sedgewicka 4 ed. książka i metody znalezienia cyklu na wykresie kierowanym różnią się od tego, który znajduje się na wykresie nieukierunkowanym.

Oto przykładowy kod, aby znaleźć cykl na nieukierunkowanym wykresie

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

Jednakże, próbując znaleźć cykl na ukierunkowanym wykresie, Sedgewick używa tablicy logicznej, w której i-ty element tej tablicy jest prawdziwy, jeśli i-ty wierzchołek został sprawdzony podczas bieżącego stosu wywołań. Dla każdego badanego wierzchołka K sprawdzamy, czy K-ty element tablicy boolowskiej jest prawdziwy. Jeśli tak, to mamy cykl. Moje pytanie brzmi, dlaczego konieczne jest użycie tej tablicy boolowskiej dla grafu kierowanego. Czy podejście, które właśnie wymieniłem, nie powinno być bardziej efektywne pod względem pamięci? Czy to podejście działa tylko dla grafów nieukierunkowanych? czemu?