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

Итак, я читаю Алгоритмы Роберта Седжвика, 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-й элемент логического массива истинным. Если это так, то у нас есть цикл. Мой вопрос: почему необходимо использовать этот логический массив для ориентированного графа. Не должен ли подход, который я только что перечислил, быть более эффективным с точки зрения памяти? И работает ли этот подход только для неориентированных графов? Зачем?

 gooser10 июн. 2012 г., 22:35
На самом деле это не предполагает самоконтроля. Я думаю, что алгоритм, который я только что опубликовал, может работать для ориентированных графов, я просто не уверен
 xvatar10 июн. 2012 г., 22:31
может быть, он предполагает, что в ориентированном графе может быть сам цикл
 xvatar10 июн. 2012 г., 22:41
ответ ниже имеет смысл ..

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

Решение Вопроса

Вы не можете использовать один и тот же алгоритм. Приведенный выше алгоритм просто исследует все связанные компоненты графа. Если вы столкнулись с уже отмеченной вершиной, должно бытьtwo different paths чтобы достичь его, и вundirected graph there must be a cycle, Если нет, вы можете перейти к следующему подключенному компоненту - не нужно очищать только что завершенный компонент.

С другой стороны, если у вас естьdirected graphдва разных пути к одной и той же вершинеdon't make a cycle, Таким образом, вам нужен другой алгоритм (например, вам может понадобиться очистить все шаги, которые вы отслеживаете).

 gooser10 июн. 2012 г., 22:45
Спасибо, это имеет смысл. Просто придумал контрпримерi.imgur.com/uBWTZ.png

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