Buscador de Camino Euleriano

Pseudocódigo

La prueba de existencia es pura cuenta y ocupa una sola pasada. Solo si esa prueba tiene éxito construyes el recorrido, usando Hierholzer en lugar de retroceso ingenuo.

// Existencia, grafo no dirigido y conexo:
//   0 vértices de grado impar -> circuito euleriano
//   2 vértices de grado impar -> camino euleriano
//   cualquier otro caso       -> ninguno de los dos

Hierholzer(grafo, inicio):
    pila = [inicio]; recorrido = []

    mientras la pila no esté vacía:
        u = pila.cima
        si u tiene alguna arista incidente sin usar (u,v):
            marcar esa arista como usada
            pila.meter(v)
        si no:
            recorrido.añadir(pila.sacar())

    invertir(recorrido)

Hierholzer funciona porque nunca tiene que adivinar. Camina hasta quedarse atascado, lo que en un grafo con todos los grados pares solo puede ocurrir de vuelta en el inicio, y luego injerta desvíos desde los vértices que aún tienen aristas sin usar. Cada vértice se entra y se sale el mismo número de veces, que es exactamente lo que garantiza el grado par, así que las piezas siempre se funden en un único recorrido cerrado.

Ejemplo resuelto, paso a paso

Construye un circuito euleriano sobre dos triángulos que comparten un único vértice, tomando los vecinos por orden alfabético.

Grafo de ejemplo: Aristas no dirigidas A-B, B-C, C-A formando un triángulo, y C-D, D-E, E-C formando un segundo, unidos por C.

1. Comprobar primero los grados. A tiene grado 2, B tiene 2, C tiene 4, D tiene 2 y E tiene 2. Todos los grados son pares y el grafo es conexo, así que existe un circuito euleriano y puede empezar en cualquier parte.
2. Caminar hasta atascarse. Desde A toma A-B, luego B-C, y desde C toma C-A. Ahora estás de vuelta en A con sus dos aristas usadas, así que el paseo se atasca. Fíjate en que se atascó en el vértice de partida, algo que los grados pares hacen inevitable.
3. Injertar el segundo triángulo. Al deshacer la pila se llega a C, que todavía tiene sin usar C-D y C-E. Camina C-D, luego D-E, luego E-C, y ahora C también está agotado.
4. Desenrollar hasta el recorrido. Sin aristas sin usar en ninguna parte, la pila se vacía en orden y el resultado invertido es el circuito.

El circuito euleriano es A a B a C a D a E a C a A, usando las seis aristas exactamente una vez y regresando al inicio. Fíjate en que C aparece dos veces en el recorrido, algo permitido y esperado: un recorrido euleriano puede revisitar vértices libremente, lo único que no puede es reutilizar una arista. Esa es toda la diferencia con un camino hamiltoniano, que visita cada vértice una vez y no se preocupa por las aristas.

Complejidad y de dónde sale

Tiempo: O(V + E) · Espacio: O(V + E)

El recuento de grados es una pasada sobre las aristas con O(E), y la comprobación de conectividad es un recorrido con O(V + E). Hierholzer mete y saca cada aparición de vértice una vez y marca cada arista como usada exactamente una vez, así que es O(E) siempre que cada vértice mantenga un puntero dentro de su lista de adyacencia en lugar de volver a escanearla desde el principio. Sin ese puntero, la búsqueda interior degrada a O(V·E). El espacio son las marcas de aristas usadas más la pila y el recorrido, que guardan O(E) entradas. Merece la pena señalar el contraste con los caminos hamiltonianos: el euleriano es lineal, el hamiltoniano es NP-completo, y la razón es puramente que las aristas se pueden contar localmente por grado y los vértices no.

Cuándo usar Camino Euleriano (No Dirigido) y cuándo no

Los problemas eulerianos son fáciles; los hamiltonianos, superficialmente parecidos, no lo son. Comprueba cuál tienes en realidad.

Errores frecuentes

• Olvidar el requisito de conectividad. Los grados pares por sí solos no bastan. Un grafo formado por dos triángulos disjuntos tiene todos los grados pares y ningún circuito euleriano, porque ningún recorrido puede saltar entre componentes. Todas las aristas deben estar en una única componente conexa, y los vértices aislados de grado cero pueden ignorarse sin problema.
• Confundir euleriano con hamiltoniano. El euleriano usa cada arista una vez y puede repetir vértices; el hamiltoniano visita cada vértice una vez y puede saltarse aristas. Suenan parecido y tienen dificultades radicalmente distintas: lineal frente a NP-completo.
• Reescanear las listas de adyacencia en Hierholzer. Si la búsqueda de una arista sin usar empieza cada vez desde el principio de la lista del vértice, el algoritmo se vuelve cuadrático. Mantén un iterador por vértice que solo avance, ya que una arista usada nunca vuelve a ser útil.
• Aplicar la regla de grados no dirigida a un grafo dirigido. Los grafos dirigidos necesitan que el grado de entrada iguale al de salida en cada vértice para un circuito, o exactamente un vértice con salida menos entrada igual a 1 y otro con entrada menos salida igual a 1 para un camino. Contar el grado total da la respuesta equivocada.
• Empezar un camino en el vértice equivocado. Cuando exactamente dos vértices tienen grado impar, el recorrido debe empezar en uno de ellos y terminar en el otro. Empezar en cualquier otro sitio significa quedarse atascado con aristas sobrantes.

Preguntas frecuentes

¿Qué es un camino euleriano?

Un camino euleriano es un recorrido que usa cada arista de un grafo exactamente una vez. Puede visitar vértices más de una vez. Si además regresa al vértice de partida se llama circuito euleriano. La idea procede de Euler resolviendo el problema de los siete puentes de Konigsberg en 1736, lo que fundó la teoría de grafos.

¿Cuándo existe un camino euleriano?

En un grafo no dirigido conexo, existe un circuito euleriano cuando todos los vértices tienen grado par, y existe un camino euleriano cuando exactamente dos vértices tienen grado impar, en cuyo caso el camino debe empezar en uno y terminar en el otro. Cualquier otro número de vértices de grado impar significa que no existe ninguno de los dos. Todas las aristas deben estar además en una única componente conexa.

¿Cuál es la diferencia entre caminos eulerianos y hamiltonianos?

Un camino euleriano usa cada arista una vez y puede revisitar vértices; un camino hamiltoniano visita cada vértice una vez y puede ignorar aristas. La diferencia de dificultad es enorme: decidir si existe un camino euleriano cuesta O(V + E) contando grados, mientras que la pregunta hamiltoniana es NP-completa.

¿Cómo funciona el algoritmo de Hierholzer?

Camina por aristas sin usar hasta atascarse, lo que en un grafo de grados pares solo puede ocurrir en el vértice de partida. Después retrocede por la pila, y siempre que encuentra un vértice con aristas sin usar recorre un nuevo ciclo cerrado desde ahí y lo injerta. Vaciar la pila produce el recorrido completo en orden inverso, y toda la ejecución es O(E).

¿Cuál es la complejidad temporal de hallar un camino euleriano?

O(V + E). Contar grados es O(E), comprobar la conectividad es un recorrido, y Hierholzer marca cada arista como usada exactamente una vez. El detalle clave de implementación es un puntero por vértice dentro de la lista de adyacencia para que las búsquedas de aristas sin usar nunca reescaneen, lo que lo mantiene lineal en lugar de cuadrático.