Encontrar un ciclo en un gráfico no dirigido versus encontrar uno en un gráfico dirigido

Question

Así que estoy leyendo los algoritmos de Robert Sedgewick 4a ed. el libro y los métodos para encontrar un ciclo en un gráfico dirigido son diferentes a los de encontrar un ciclo en un gráfico no dirigido.

Aquí es código de ejemplo para encontrar un ciclo en un grafo no dirigido

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

Sin embargo, cuando se trata de encontrar un ciclo en un grafo dirigido, Sedgewick utiliza un matriz booleana donde el elemento i-ésimo de esa matriz es cierto si el i-ésimo vértice se ha examinado durante la pila de llamadas actual. Para cada vértice K examinado, verificamos si el elemento Kth de la matriz booleana es verdadero. Si es así, entonces tenemos un ciclo. Mi pregunta es, ¿por qué es necesario usar esa matriz booleana para un gráfico dirigido. ¿No debería el enfoque que acabo de enumerar ser más eficiente con la memoria? ¿Y este enfoque solo funciona para gráficos no dirigidos? ¿por qué?

Answer 1

No puede usar el mismo algoritmo: el algoritmo anterior simplemente explora todos los componentes conectados del gráfico. Si encuentra un vértice ya marcado, debe haber dos rutas diferentes para alcanzarlo, y en un gráfico no dirigido debe haber un ciclo. De lo contrario, puede continuar con el siguiente componente conectado; no es necesario que limpie el componente que acaba de terminar.

Por otro lado, si usted tiene un gráfico dirigido , dos caminos diferentes para el mismo vértice no hacer un ciclo de. Por lo tanto, necesita un algoritmo diferente (por ejemplo, puede que tenga que limpiar los pasos que rastrea).