Итак, я читаю Алгоритмы Роберта Седжвика, 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;
}
}
Однако при попытке найти цикл в ориентированном графе Sedgewick использует логический массив, где i-й элемент этого массива равен true, если i-я вершина была проверена во время текущего стека вызовов. Для каждой проверенной вершины K мы проверяем, является ли K-й элемент логического массива истинным. Если это так, то у нас есть цикл. Мой вопрос в том, почему необходимо использовать этот логический массив для ориентированного графа. Разве подход, который я только что перечислил, не должен быть более эффективным с точки зрения -памяти? И работает ли этот подход только для неориентированных графов? Зачем?