Нахождение цикла в неориентированном графе против нахождения цикла в ориентированном графе

Итак, я читаю Алгоритмы Роберта Седжвика, 4-е изд. Книга и методы для нахождения цикла в ориентированном графе отличаются от методов для нахождения цикла в неориентированном графе.

Вот пример кода, чтобы найти цикл в неориентированном графе

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

Однако при попытке найти цикл в ориентированном графе Седжвик использует логический массив, в котором i-й элемент этого массива имеет значение true, если i-я вершина была проверена во время текущего стека вызовов. Для каждой проверенной вершины K мы проверяем, является ли K-й элемент логического массива истинным. Если это так, то у нас есть цикл. Мой вопрос: почему необходимо использовать этот логический массив для ориентированного графа. Не должен ли подход, который я только что перечислил, быть более эффективным с точки зрения памяти? И работает ли этот подход только для неориентированных графов? Зачем?

Ответы на вопрос(1)

Ваш ответ на вопрос