Deje G (V, E) ser un gráfico conectado, no dirigido, dar un algoritmo O (| V | + | E |) para calcular una ruta en G que atraviesa cada borde en E exactamente una vez en cada dirección?

Primero, resolvamos el problema más simple donde el gráfico es un árbol. La solución aquí es sencilla. Haz un DFS desde cualquier vértice. Cada vez que pasa de un padre a un hijo, el borde se atravesará en la dirección hacia adelante y cuando regrese, se atravesará en la dirección inversa .

Si usamos el mismo algoritmo en un gráfico general, terminaremos atravesando solo los bordes en un árbol DFS del gráfico. Los bordes que nos faltarán serán aquellos entre vértices y sus antepasados no inmediatos en el árbol. Una ligera modificación asegurará que estos bordes también se cuiden. Esencialmente, cada vez que veas tal borde, solo recorrelo en ambas direcciones. Sin embargo, debemos asegurarnos de no contar dos veces dichos bordes tanto en el ancestro como en el descendiente; esto se puede garantizar manteniendo las profundidades de todos los vértices y atravesando el borde solo desde un vértice de menor profundidad a una mayor profundidad [ 1]

  def dfs (u):
   te marca como visitado
   para todas las v adyacentes a u:
     si v no se visita
       establecer profundidad [v] = profundidad [u] +1
       borde transversal u-> v
       dfs (v)
       borde transversal v-> u
     más si profundidad [v]> profundidad [u]:
       borde transversal u-> v
       borde transversal v-> u

[1] Me había perdido por completo el tema del doble conteo hasta que Garima Dhanania señaló el error después de dos años completos: -o. La versión anterior de esta respuesta tenía la solución incorrecta en la que atravesaba cada borde del árbol que no era dfs a cada vértice que no era el padre inmediato. Esto resultaría en un doble recuento, como lo mostró en su ejemplo.

AlgoritmosAlgoritmos degrafosprogramación de computadorasTeoría de grafos