¿Qué es un algoritmo eficiente para encontrar un circuito euleriano en un gráfico no dirigido?

El algoritmo de Fluery mencionado en otra respuesta es elegante pero no eficiente.

Un algoritmo más eficiente es el siguiente. Si el gráfico no está conectado o hay al menos un vértice de grado impar, entonces el gráfico no tiene un recorrido de Euler. De lo contrario, construimos un recorrido de la siguiente manera. Elija algún vértice v para comenzar. Siga atravesando bordes no utilizados hasta que alcancemos un vértice que no incide en ningún borde no utilizado; este vértice debe ser el vértice v en el que comenzó. Mientras hace esto, coloque los vértices encontrados en una lista vinculada en el orden encontrado (el primer y último vértices son v).

Bucle: recorre la lista vinculada hasta encontrar un vértice w que incide en un borde no utilizado. Ahora comenzando en w, siga atravesando bordes no utilizados hasta que nos quedemos atascados nuevamente (es decir, lleguemos a un vértice que no incide en un borde no utilizado) y coloque los vértices encontrados en una lista vinculada en el orden encontrado. ¡ Debemos quedarnos atascados en el vértice w! Inserte esta nueva lista vinculada en la antigua lista vinculada en lugar del vértice w. Repita a partir del recién agregado vecino de w.

Cuando llegamos al final de la lista vinculada, hemos terminado y la lista vinculada contiene los vértices en el orden de un Tour Euler.

En realidad, puede escribir este algoritmo de manera más elegante de la siguiente manera.

Inicialice S en una pila vacía y C en una lista vacía
Elige un vértice v
Repita hasta que v no incide en un borde no utilizado y S está vacío
si v no incide en ningún borde no utilizado
luego anteponer v a C
v = pila emergente S
de lo contrario, empuje v sobre la pila S
para algún borde no utilizado (v, w)
marque (v, w) como se usa
v = w
Al final: C es una lista de vértices en el orden encontrado en un Euler Tour

El primer bucle en el algoritmo anterior crea una lista vinculada, mientras que en la segunda versión creamos una pila de estos mismos vértices, ejecutando repetidamente la cláusula else hasta que no podamos seguir adelante. Luego, seguir repetidamente la cláusula then equivale a recorrer la lista vinculada desde la primera versión en el orden inverso. Repetimos hasta encontrar un vértice con un borde no utilizado, en cuyo caso ejecutamos repetidamente la cláusula else que encuentra un subciclo que se empalma en la lista / ciclo original.

Tenga en cuenta que si cambia “anteponer” a “agregar” en esta versión, obtendrá la misma lista de vértices, pero estarán en el orden opuesto al que “atravesó” el Recorrido de Euler, es decir, corresponde a recorrer el Recorrido el ” otro camino alrededor.