algorithm - harary - Ciclos en un gráfico no dirigido
graph theory harary (15)
Dado un gráfico no dirigido G = ( V , E ) con n vértices (| V | = n ), ¿cómo se puede encontrar si contiene un ciclo en O ( n )?
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 algunos resultados 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!
*/
Como otros han mencionado ... Una primera búsqueda en profundidad lo resolverá. En general, la primera búsqueda en profundidad toma O (V + E) pero en este caso usted sabe que el gráfico tiene como máximo O (V) bordes. Entonces, simplemente puede ejecutar un DFS y una vez que vea una nueva ventaja aumentar un contador. Cuando el contador ha llegado a V no tiene que continuar porque el gráfico tiene ciertamente un ciclo. Obviamente esto toma O (v).
Creo que la primera búsqueda en profundidad lo resuelve. Si un borde inexplorado conduce a un nodo visitado anteriormente, entonces el gráfico contiene un ciclo. Esta condición también lo convierte en O (n), ya que puede explorar un máximo de n bordes sin establecerlo en verdadero o sin bordes inexplorados.
Creo que la suposición de que el gráfico está conectado puede ser complicado. por lo tanto, puede usar la prueba que se muestra arriba, 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 |) .
Creo que usar DFS correctamente también depende de cómo va a representar su gráfico en el código. Por ejemplo, supongamos que está utilizando listas adyacentes para hacer un seguimiento de los nodos vecinos y su gráfico tiene 2 vértices y solo un borde: V = {1,2} y E = {(1,2)}. En este caso, comenzando desde el vértice 1, DFS lo marcará como VISITADO y pondrá 2 en la cola. Después de que saltará el vértice 2 y dado 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 Undirected (1,2) y (2,1) están el mismo borde y debe codificar de manera que DFS no los considere bordes diferentes. Mantener el nodo primario para cada nodo visitado ayudará a manejar esta situación.
Empecé a estudiar gráficos recientemente. Escribí un 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 recursión utilicé una pila para atravesar el gráfico.
En un alto nivel DFT usando una pila se hace en los siguientes pasos
- Visita un nodo
- Si el nodo no está en la lista visitada, agréguelo a la lista y empújelo hasta la parte superior de la pila
- Marque el nodo en la parte superior de la pila como el nodo actual.
- Repita lo anterior para cada nodo adyacente del nodo actual
- Si se han visitado todos los nodos, saque el nodo actual de la pila
Realicé un DFT desde cada nodo del gráfico y durante el recorrido si encontré un vértice que visité antes, verifiqué si el vértice tenía una profundidad de pila mayor que uno. También verifiqué si un nodo tenía un borde en sí mismo y si había múltiples bordes entre los nodos. La versión de la pila que originalmente escribí no era muy elegante. Leí el pseudo código de cómo se podía hacer usando la recursión y estaba limpio. Aquí hay una implementación de Java. La matriz 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;
}
}
En realidad, la búsqueda de profundidad primero (o incluso la amplitud primero) no es suficiente. Necesitas un algoritmo mucho más complejo.
Por ejemplo, supongamos que hay un gráfico con nodos {a, b, c, d} y bordes {(a, b), (b, c), (b, d), (d, c)} donde un borde (x , y) es un borde de xa y. (se ve algo así, con todos los bordes dirigidos hacia abajo).
(a)
|
|
(b)
/ /
(d) |
| |
/ /
(c)
Luego, haciendo una primera búsqueda en profundidad puede visitar el nodo (a), luego (b), luego (c), luego retroceder a (b), visitar (d) y finalmente visitar (c) nuevamente y concluir que hay un ciclo - cuando no hay Algo similar sucede con la amplitud primero.
Lo que debe hacer es realizar un seguimiento de qué nodos está en el 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 sin terminar significa que tienes un ciclo. La forma habitual de hacerlo es colorear cada nodo en blanco (aún no visitado), gris (visitar descendientes) o negro (visitar por última vez).
¡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
luego ejecutar visita (root_node) arrojará una excepción si y solo si hay un ciclo (inicialmente todos los nodos deberían ser blancos).
La respuesta es, realmente, la primera búsqueda de amplitud (o la primera búsqueda de profundidad, realmente no importa). Los detalles se encuentran 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, se alcanzó el objetivo.
Ahora imagine que el gráfico tiene ciclos y su algoritmo de búsqueda terminará e informará sobre el é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 tiene 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.
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, esa no es una pequeña cantidad de información :)
Puede usar la biblioteca de gráficos de impulso y las dependencias cíclicas . Tiene la solución para encontrar ciclos con la función back_edge .
Puedes resolverlo usando DFS. Complejidad del tiempo: O (n)
La esencia del algoritmo es que si un componente / gráfico conectado NO contiene un CICLO, siempre será un ÁRBOL. Vea aquí para prueba
Supongamos que el gráfico no tiene ciclo, es decir, es un árbol. Y si miramos un árbol, cada borde de un nodo:
1.either alcanza a su único padre, que está un nivel por encima de él.
2.o alcanza a sus hijos, que están un nivel debajo de él.
Entonces, si un nodo tiene cualquier otro borde que no se encuentre entre los dos descritos anteriormente, obviamente conectará el nodo a uno de sus antecesores que no sea el principal. Esto formará un CICLO.
Ahora que los hechos son claros, todo lo que tienes que hacer es ejecutar un DFS para el gráfico (considerando que tu gráfica está conectada, de lo contrario hazlo para todos los vértices no visitados), y SI encuentras un vecino del nodo que se VISITA y NO su padre, entonces mi amigo hay un CICLO en el gráfico, y estás HECHO.
Puede realizar un seguimiento de los padres simplemente pasando el elemento primario como parámetro cuando hace DFS para sus vecinos. Y dado que solo necesita examinar n bordes como máximo, la complejidad del tiempo será O (n).
Espero que la respuesta haya ayudado.
Un DFS simple hace el trabajo de verificar si el gráfico no dirigido dado tiene un ciclo o no.
Aquí está el código de C ++ al mismo.
La idea utilizada en el código anterior es:
Si un nodo que ya está descubierto / visitado se encuentra de nuevo y 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 anteriormente, entonces el gráfico contiene un ciclo.
Un gráfico conectado, no dirigido G que no tiene ciclos es un árbol! Cualquier árbol tiene exactamente n - 1 bordes, por lo que simplemente podemos atravesar la lista de bordes del gráfico y contar los bordes. Si contamos n - 1 bordes, entonces devolvemos "sí", pero si alcanzamos el nésimo, entonces devolvemos "no". Esto toma O (n) tiempo porque miramos a la mayoría de los n bordes.
Pero si el gráfico no está conectado, entonces tendríamos que usar DFS. Podemos atravesar los bordes y si los bordes inexplorados conducen al vértice visitado, entonces tiene un ciclo.
Un gráfico no dirigido es acíclico (es decir, un bosque) si un DFS no produce bordes posteriores. Como los bordes posteriores son aquellos bordes ( u , v ) que conectan un vértice u con un antecesor v en un árbol con profundidad inicial, por lo que los bordes posteriores no significan que solo hay bordes de árbol, por lo que no hay ciclo. Entonces podemos simplemente divertirnos con DFS. Si encuentra un borde posterior, hay un ciclo. La complejidad es O(V ) lugar de O(E + V ) . Dado que si hay un borde posterior, debe encontrarse antes de ver |V | bordes distintos Esto se debe a que en un bosque acíclico (no dirigido), |E| ≤ |V | + 1 |E| ≤ |V | + 1 |E| ≤ |V | + 1 .
Un gráfico no dirigido sin ciclo tiene | E | <| V | -1.
public boolean hasCycle(Graph g) {
int totalEdges = 0;
for(Vertex v : g.getVertices()) {
totalEdges += v.getNeighbors().size();
}
return totalEdges/2 > g.getVertices().size - 1;
}