Ciclos en un Gráfico No Dirigido

En realidad, la búsqueda primero en profundidad (o de hecho primero en amplitud) no es suficiente. Necesitas un algoritmo más complejo.

Por ejemplo, supongamos que hay grafo con nodos {a,b,c,d} y los bordes {(a,b),(b,c),(b,d),(d,c)} donde una arista (x,y) es una arista de x a y. (se ve algo así, con todos los bordes dirigidos hacia abajo.)

    (a)
     |
     |
    (b)
    / \ 
  (d)  |
   |   |
    \ /
    (c)

Luego, haciendo la primera búsqueda en profundidad, puede visitar el nodo (a), luego (b), luego (c), luego volver a (b), luego visitar (d) y finalmente visitar (c) de nuevo y concluyen que hay un ciclo when cuando no lo hay. Una cosa similar sucede con la amplitud primero.

Lo que necesita hacer es realizar un seguimiento de qué nodos está en medio de la visita. En el ejemplo anterior, cuando el algoritmo alcanza (d) ha terminado de visitar (c) pero no (a) o (b). Así que volver a visitar un nodo terminado está bien, pero visitar un nodo inacabado significa que tiene un ciclo. La forma habitual de hacerlo es colorear cada nodo blanco (aún no visitado), gris (descendientes visitantes) o negro (terminado visitar).

Aquí hay un pseudo código!

define visit(node n):
  if n.colour == grey: //if we're still visiting this node or its descendants
    throw exception("Cycle found")

  n.colour = grey //to indicate this node is being visited
  for node child in n.children():
    if child.colour == white: //if the child is unexplored
      visit(child)

  n.colour = black //to show we're done visiting this node
  return

Entonces ejecutar visit(root_node) lanzará una excepción si y solo si hay un ciclo (inicialmente todos los nodos deben ser blancos).

Un grafo G conectado, no dirigido que no tiene ciclos es un árbol! Cualquier árbol tiene exactamente n-1 aristas, por lo que simplemente podemos recorrer la lista de aristas del gráfico y contar las aristas. Si contamos los bordes n-1, regresamos "sí", pero si alcanzamos el enésimo borde, regresamos"no". Esto toma O (n) tiempo porque nos fijamos en la mayoría de n bordes.

Pero si el gráfico no está conectado,entonces tendríamos que usar DFS. Podemos atravesar los bordes y si algún borde inexplorado conduce al vértice visitado entonces tiene ciclo.

Puede resolverlo usando DFS. Complejidad temporal: O (n)

La esencia del algoritmo es que si un componente/gráfico conectado NO contiene un CICLO, siempre será un ÁRBOL.Ver aquí para la prueba

Supongamos que el gráfico no tiene ciclo, es decir, es un árbol. Y si nos fijamos en un árbol, cada borde de un nodo:

1.cualquiera de los dos alcanza a su único padre, que es un nivel por encima de él.

2.o alcanza a sus hijos, que están un nivel por debajo se.

Entonces, si un nodo tiene cualquier otra arista que no esté entre las dos descritas anteriormente, obviamente conectará el nodo a uno de sus ancestros que no sea su padre. Esto formará un CICLO.

Ahora que los hechos están claros, todo lo que tiene que hacer es ejecutar un DFS para el gráfico (teniendo en cuenta que su gráfico está conectado, de lo contrario hacerlo para todos los vértices no visitados), y SI encuentra un vecino del nodo que se VISITA y NO su padre, entonces mi amigo hay un CICLO en el gráfico, y estás ACABADO.

Puede realizar un seguimiento del padre simplemente pasando el padre como parámetro cuando hace DFS para sus vecinos. Y dado que solo necesita examinar n aristas como máximo, la complejidad temporal será O(n).

Espero que la respuesta haya ayudado.

Por cierto, si usted sabe que está conectado, entonces simplemente es un árbol (por lo tanto no hay ciclos) si y solo si |E|=|V|-1. Por supuesto que no es una pequeña cantidad de información:)

La respuesta es, realmente, la búsqueda primero en amplitud (o la búsqueda primero en profundidad, realmente no importa). Los detalles están en el análisis.

Ahora, ¿qué tan rápido es el algoritmo?

Primero, imagine que el gráfico no tiene ciclos. El número de aristas es entonces O (V), el gráfico es un bosque, objetivo alcanzado.

Ahora, imagine que el gráfico tiene ciclos, y su algoritmo de búsqueda terminará e informará de éxito en el primero de ellos. El gráfico no está dirigido, y por lo tanto, cuando el algoritmo inspecciona un borde, solo hay dos posibilidades: O ha visitado el otro extremo del borde, o lo ha hecho y luego, este borde cierra un círculo. Y una vez que ve el otro vértice del borde, ese vértice es "inspeccionado", por lo que solo hay O(V) de estas operaciones. El segundo caso se alcanzará solo una vez durante la ejecución del algoritmo.

Creo que la suposición de que el gráfico está conectado puede ser difícil. por lo tanto, puede utilizar la prueba mostrada anteriormente, que el tiempo de ejecución es O(|V|). si no, entonces |E|>|V|. recordatorio: el tiempo de ejecución de DFS es O(|V|+|E|).

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

#include<stdio.h>
#include<stdlib.h>

/****Global Variables****/
int A[20][20],visited[20],v=0,count=0,n;
int seq[20],s=0,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!

*/

Un DFS simple hace el trabajo de comprobar si el gráfico no dirigido dado tiene un ciclo o no.

Aquí está el código C++ para el mismo.

La idea utilizada en el código anterior es:

Si un nodo que ya está descubierto / visitado se encuentra de nuevo y es no es el nodo padre, entonces tenemos un ciclo.

Esto también se puede explicar a continuación (mencionado por @Rafał Dowgird

Si un borde inexplorado conduce a un nodo visitado antes, entonces el gráfico contiene un ciclo.

Un gráfico no dirigido es acíclico (es decir, un bosque) si un DFS no produce bordes traseros. Ya que los bordes traseros son esos bordes (u, v) conectar un vértice u a un antepasado v en un árbol de profundidad, por lo que no hay bordes traseros significa que solo hay bordes de árbol, por lo que no hay ciclo. Así que podemos simplemente divertido DFS. Si encuentran el borde trasero, hay un ciclo. Complejidad es O(V ) en lugar de O(E + V ). Ya que si hay un borde posterior, debe ser encontrado antes de ver |V | bordes distintos. Esto se debe a que en un acíclico (no dirigido) bosque, |E| ≤ |V | + 1.

Empecé a estudiar gráficos recientemente. Escribí un fragmento de código en Java que podría determinar si un gráfico tiene ciclos. Usé DFT para encontrar ciclos en el gráfico. En lugar de recursividad usé una pila para recorrer el gráfico.

En un DFT de alto nivel utilizando una pila se realiza en los siguientes pasos

1. Visita un nodo
2. Si el nodo no está en la lista visitada, agréguelo a la lista y púlselo a la parte superior de la pila
3. Marque el nodo en la parte superior de la pila como el nodo.
4. Repita lo anterior para cada nodo adyacente del nodo actual
5. Si todos los nodos han sido visitados pop el nodo actual fuera de la pila

Realicé un DFT de cada nodo del Gráfico y durante el recorrido si me encontré con un vértice que visité anteriormente, comprobé si el vértice tenía una profundidad de pila mayor que uno. También comprobé si un nodo tenía un borde a sí mismo y si había múltiples bordes entre los nodos. La versión de pila que escribí originalmente no era muy elegante. Leí el pseudo código de cómo se podía hacer usando recursión y estaba limpio. Aquí hay una implementación de Java. El array LinkedList representa un gráfico. con cada nodo y sus vértices adyacentes denotados por el índice de la matriz y cada elemento respectivamente

class GFG {
Boolean isCyclic(int V, LinkedList<Integer>[] alist) {
    List<Integer> visited = new ArrayList<Integer>();
    for (int i = 0; i < V; i++) {
        if (!visited.contains(i)) {
            if (isCyclic(i, alist, visited, -1))
                return true;
        }
    }
    return false;
}

Boolean isCyclic(int vertex, LinkedList<Integer>[] alist, List<Integer> visited, int parent) {
    visited.add(vertex);
    for (Iterator<Integer> iterator = alist[vertex].iterator(); iterator.hasNext();) {
        int element = iterator.next();
        if (!visited.contains(element)) {
            if (isCyclic(element, alist, visited, vertex))
                return true;
        } else if (element != parent)
            return true;
    }
    return false;
}

}

Puedes usar boost graph library y dependencias cíclicas. Tiene la solución para encontrar ciclos con la función back_edge.

Como otros han mencionado... Una primera búsqueda en profundidad lo resolverá. En general profundidad primera búsqueda toma O (V + E) pero en este caso usted sabe que el gráfico tiene como máximo O(V) bordes. Así que simplemente puede ejecutar un DFS y una vez que vea un nuevo borde aumentar un contador. Cuando el contador ha alcanzado V usted no tiene que continuar porque el gráfico tiene ciertamente un ciclo. Obviamente esto toma O (v).

Creo que usar DFS correctamente también depende de cómo vas a representar tu gráfico en el código. Por ejemplo, supongamos que está utilizando listas adyacentes para realizar un seguimiento de los nodos vecinos y su gráfico tiene 2 vértices y solo una arista: V={1,2} y E={(1,2)}. En este caso a partir del vértice 1, DFS lo marcará como VISITADO y pondrá 2 en la cola. Después de eso hará estallar el vértice 2 y puesto que 1 es adyacente a 2, y 1 es VISITADO, DFS concluirá que hay un ciclo (que es incorrecto). En otras palabras en los gráficos no dirigidos (1,2) y (2,1) son la misma arista y debe codificar de una manera que DFS no los considere diferentes aristas. Mantener el nodo padre para cada nodo visitado ayudará a manejar esta situación.

Un gráfico no dirigido sin ciclo tiene |E|

public boolean hasCycle(Graph g) {

   int totalEdges = 0;
   for(Vertex v : g.getVertices()) {
     totalEdges += v.getNeighbors().size();
   }
   return totalEdges/2 > g.getVertices().size - 1;

}