Encontrar um ciclo em um gráfico não direcionado versus encontrar um em um gráfico direcionado
Então estou lendo o Algorithms 4th ed de Robert Sedgewick. livro e os métodos para encontrar um ciclo em um grafo direcionado é diferente daquele para encontrar um ciclo em um grafo não direcionado.
Aqui está um código de exemplo para encontrar um ciclo em um gráfico não direcionado
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;
}
}
No entanto, ao tentar encontrar um ciclo em um grafo direcionado, o Sedgewick usa uma matriz booleana onde o elemento de ith dessa matriz é verdadeiro se o vértice i foi examinado durante a pilha de chamadas atual. Para cada vértice K examinado, verificamos se o elemento Kth da matriz booleana é verdadeiro. Se for, então temos um ciclo. Minha pergunta é: por que é necessário usar esse array booleano para um gráfico direcionado? A abordagem que acabei de mencionar não deveria ser mais eficiente em termos de memória? E essa abordagem funciona apenas para gráficos não direcionados? porque?