Solución:
Creo que la búsqueda en profundidad lo resuelve. Si un borde inexplorado conduce a un nodo visitado antes, 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 quedarse sin bordes inexplorados.
En realidad, la búsqueda en profundidad primero (o de hecho primero en amplitud) no es suficiente. Necesita un algoritmo algo más complejo.
Por ejemplo, suponga 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 una arista de xay. (se parece a esto, con todos los bordes dirigidos hacia abajo).
(a)
|
|
(b)
/
(d) |
| |
/
(c)
Luego, hacer una búsqueda en profundidad primero puede visitar el nodo (a), luego (b), luego (c), luego retroceder hasta (b), luego visitar (d), y finalmente visitar (c) nuevamente y concluir que hay un ciclo – cuando no lo hay. Algo similar sucede con la amplitud primero.
Lo que debe hacer es realizar un seguimiento de los nodos que está en el medio de la visita. En el ejemplo anterior, cuando el algoritmo llega a (d) ha terminado de visitar (c) pero no (a) o (b). Entonces, volver a visitar un nodo terminado está bien, pero visitar un nodo sin terminar significa que tiene un ciclo. La forma habitual de hacerlo es colorear cada nodo de blanco (aún no visitado), gris (descendientes visitantes) o negro (visita finalizada).
aquí hay un pseudocó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 visit (root_node) arrojará una excepción si y solo si hay un ciclo (inicialmente, todos los nodos deben ser blancos).
¡Un gráfico G conectado y 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 n – 1 aristas, devolvemos “sí”, pero si llegamos a la n-ésima arista, devolvemos “no”. Esto lleva O (n) tiempo porque miramos en 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 algún borde inexplorado conduce al vértice visitado, entonces tiene un ciclo.