graph - first - Detectar ciclos en un gráfico usando DFS: 2 enfoques diferentes y cuál es la diferencia

detect cycle in undirected graph

Question

Tenga en cuenta que un gráfico se representa como una lista de adyacencia.

He oído hablar de 2 enfoques para encontrar un ciclo en un gráfico:

1. Mantenga una matriz de valores booleanos para realizar un seguimiento de si ha visitado un nodo anteriormente. Si te quedas sin nuevos nodos para ir (sin tocar un nodo que ya has visitado), entonces solo retrocede y prueba con una nueva rama.

2. El de CLRS o Skiena de Cormen: para la búsqueda de profundidad en gráficos no dirigidos, hay dos tipos de aristas, arbol y reverso. El gráfico tiene un ciclo si y solo si existe un borde posterior.

¿Alguien puede explicar cuáles son los bordes posteriores de un gráfico y cuál es la diferencia entre los 2 métodos anteriores?

Gracias.

Actualización: Aquí está el código para detectar ciclos en ambos casos. Graph es una clase simple que representa todos los nodos de gráfico como números únicos para simplificar, cada nodo tiene sus nodos vecinos adyacentes (g.getAdjacentNodes (int)):

public class Graph {
private int[][] nodes; // all nodes; e.g. int[][] nodes = {{1,2,3}, {3,2,1,5,6}...};
public int[] getAdjacentNodes(int v) {
return nodes[v];
}
// number of vertices in a graph
public int vSize() {
return nodes.length;
}
}

Código de Java para detectar ciclos en un gráfico no dirigido:

 public class DFSCycle {
private boolean marked[];
private int s;
private Graph g;
private boolean hasCycle;
// s - starting node
public DFSCycle(Graph g, int s) {
this.g = g;
this.s = s;
marked = new boolean[g.vSize()];
findCycle(g,s,s);
}
public boolean hasCycle() {
return hasCycle;
}
public void findCycle(Graph g, int v, int u) {
marked[v] = true;
for (int w : g.getAdjacentNodes(v)) {
if(!marked[w]) {
marked[w] = true;
findCycle(g,w,v);
} else if (v != u) {
hasCycle = true;
return;
}
}
}
}

Código de Java para detectar ciclos en un gráfico dirigido:

public class DFSDirectedCycle {
private boolean marked[];
private boolean onStack[];
private int s;
private Graph g;
private boolean hasCycle;
public DFSDirectedCycle(Graph g, int s) {
this.s = s
this.g = g;
marked = new boolean[g.vSize()];
onStack = new boolean[g.vSize()];
findCycle(g,s);
}
public boolean hasCycle() {
return hasCycle;
}
public void findCycle(Graph g, int v) {
marked[v] = true;
onStack[v] = true;
for (int w : g.adjacentNodes(v)) {
if(!marked[w]) {
findCycle(g,w);
} else if (onStack[w]) {
hasCycle = true;
return;
}
}
onStack[v] = false;
}
}

Answer 1

Aquí está el código que he escrito en C basado en DFS para averiguar si un gráfico indirecto dado está conectado / cíclico o no. con algunos resultados de muestra al final. Espero que sea útil :)

#include<stdio.h>
#include<stdlib.h>
/****Global Variables****/
int A[20][20],visited[20],count=0,n;
int seq[20],connected=1,acyclic=1;
/****DFS Function Declaration****/
void DFS();
/****DFSearch Function Declaration****/
void DFSearch(int cur);
/****Main Function****/
int main()
{
int i,j;
printf("/nEnter no of Vertices: ");
scanf("%d",&n);
printf("/nEnter the Adjacency Matrix(1/0):/n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&A[i][j]);
printf("/nThe Depth First Search Traversal:/n");
DFS();
for(i=1;i<=n;i++)
printf("%c,%d/t",''a''+seq[i]-1,i);
if(connected && acyclic) printf("/n/nIt is a Connected, Acyclic Graph!");
if(!connected && acyclic) printf("/n/nIt is a Not-Connected, Acyclic Graph!");
if(connected && !acyclic) printf("/n/nGraph is a Connected, Cyclic Graph!");
if(!connected && !acyclic) printf("/n/nIt is a Not-Connected, Cyclic Graph!");
printf("/n/n");
return 0;
}
/****DFS Function Definition****/
void DFS()
{
int i;
for(i=1;i<=n;i++)
if(!visited[i])
{
if(i>1) connected=0;
DFSearch(i);
}
}
/****DFSearch Function Definition****/
void DFSearch(int cur)
{
int i,j;
visited[cur]=++count;
seq[count]=cur;
for(i=1;i<count-1;i++)
if(A[cur][seq[i]])
acyclic=0;
for(i=1;i<=n;i++)
if(A[cur][i] && !visited[i])
DFSearch(i);
}

Muestra de salida:

majid@majid-K53SC:~/Desktop$ gcc BFS.c
majid@majid-K53SC:~/Desktop$ ./a.out
************************************
Enter no of Vertices: 10
Enter the Adjacency Matrix(1/0):
0 0 1 1 1 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 1 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 1 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 1 0 0 0
The Depdth First Search Traversal:
a,1 c,2 d,3 f,4 b,5 e,6 g,7 h,8 i,9 j,10
It is a Not-Connected, Cyclic Graph!
majid@majid-K53SC:~/Desktop$ ./a.out
************************************
Enter no of Vertices: 4
Enter the Adjacency Matrix(1/0):
0 0 1 1
0 0 1 0
1 1 0 0
0 0 0 1
The Depth First Search Traversal:
a,1 c,2 b,3 d,4
It is a Connected, Acyclic Graph!
majid@majid-K53SC:~/Desktop$ ./a.out
************************************
Enter no of Vertices: 5
Enter the Adjacency Matrix(1/0):
0 0 0 1 0
0 0 0 1 0
0 0 0 0 1
1 1 0 0 0
0 0 1 0 0
The Depth First Search Traversal:
a,1 d,2 b,3 c,4 e,5
It is a Not-Connected, Acyclic Graph!
*/

Answer 2

Para completar, es posible encontrar ciclos en un gráfico dirigido usando DFS (de wikipedia ):

 L ← Empty list that will contain the sorted nodes
while there are unmarked nodes do
select an unmarked node n
visit(n)
function visit(node n)
if n has a temporary mark then stop (not a DAG)
if n is not marked (i.e. has not been visited yet) then
mark n temporarily
for each node m with an edge from n to m do
visit(m)
mark n permanently
unmark n temporarily
add n to head of L

Answer 3

Respondiendo mi pregunta:

El gráfico tiene un ciclo si y solo si existe un borde posterior. Un borde posterior es un borde que es de un nodo a sí mismo (autovío) o uno de sus antecesores en el árbol producido por DFS formando un ciclo.

Ambos enfoques anteriores realmente significan lo mismo. Sin embargo, este método se puede aplicar solo a gráficos no dirigidos .

La razón por la cual este algoritmo no funciona para los gráficos dirigidos es que en un gráfico dirigido 2 rutas diferentes al mismo vértice no forman un ciclo. Por ejemplo: A -> B, B -> C, A -> C - no hacer un ciclo mientras que en los no dirigidos: A - B, B - C, C - A lo hace.

Encuentra un ciclo en gráficos no dirigidos

Un gráfico no dirigido tiene un ciclo si y solo si una búsqueda en profundidad (DFS) encuentra un borde que apunta a un vértice ya visitado (un borde posterior).

Encuentra un ciclo en gráficos dirigidos

Además de los vértices visitados, necesitamos realizar un seguimiento de los vértices que se encuentran actualmente en la pila de recursión de funciones para el cruce de DFS. Si alcanzamos un vértice que ya está en la pila de recursión, entonces hay un ciclo en el árbol.

Actualización: el código de trabajo está en la sección de preguntas de arriba.