Gráfico de poda para detectar ciclos: ¿mejor que DFS?

Question

Por podar un grafo no dirigido G, me refiero a eliminar iterativamente todas las hojas (nodos de grado 1) junto con la arista incidente de un grafo hasta que se quede con un único nodo (G no contenía ningún ciclo) o al menos 2 aristas (G contiene un ciclo). Esto también se denomina 2 núcleos del gráfico.

¿No es éste un algoritmo más sencillo para detectar ciclos que el DFS habitualmente sugerido?

También funcionaría en grafos dirigidos mediante la poda de nodos con sólo aristas entrantes.

Answer 1

Una de las ventajas de DFS es que es un algoritmo único que hace muchas cosas. Para cuando lo hayas implementado cinco veces, no pensarás en ningún otro algoritmo más fácil :) También encontrar un ciclo, mientras que la poda de hojas en algunos casos sólo detectar si un ciclo está presente o no.

Sin embargo, si eso es todo lo que necesitas, también se puede utilizar el algoritmo de poda. Hay que tener cuidado al implementarlo para que sea competitivo con DFS. En general, DFS tarda $O(|E|)$ tiempo para recorrer todo el gráfico; sin embargo, está garantizado que encontrará un ciclo en $O(|V|)$ tiempo, si es que existe.

Resulta tentador iniciar el algoritmo de poda calculando la secuencia de grados del grafo. Sin embargo, si hacemos eso ingenuamente, entonces habremos tomado $O(|E|)$ tiempo sólo para ese primer paso, ¡cuando el gráfico es denso! Esto es fácil de evitar si tenemos cuidado: mientras calculas los grados de los vértices, controla el número total de aristas procesadas y detente si $|E| \ge |V|$ . En ese caso, ya sabemos que habrá un ciclo - y si $|E| < |V|$ entonces calculamos la secuencia de grados en $O(|V|)$ tiempo.

Pasado ese paso, un esbozo de cómo podríamos terminar el algoritmo en $O(|V|)$ tiempo es a:

• Recorre todos los vértices uno a uno en el bucle principal.
• Siempre que encuentre un vértice de grado $1$ Pode y ir inmediatamente a su único vecino - para actualizar sus adyacencias y comprobar si ese vecino tiene ahora grado $1$ . Es posible que haya que repetirlo varias veces. Cuando hayas terminado, vuelve al punto donde estabas en el bucle principal.
• Vértices de grado $0$ también deben podarse, aunque no tenemos que hacer nada especial con ellos.
• Una vez finalizado el bucle principal, existe un ciclo si no se han podado todos los vértices.

En realidad, no es necesario calcular de antemano la secuencia de titulaciones. Es posible combinarlo con el bucle principal: cada vez que veamos un vértice, lo único que tenemos que hacer es comprobar si tiene el grado $0$ o $1$ que se puede hacer en $O(1)$ tiempo sin computar su grado.

No creo que esto sea particularmente más sencillo que DFS, pero es una alternativa viable.