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