Complejidad del tiempo del algoritmo de Fleury

Question

¿Podría ayudarme a averiguar la complejidad temporal del algoritmo de Fleury (que se usa para obtener el circuito de Eulerian)?

Answer 1

Aquí: http://roticv.rantx.com/book/Eulerianpathandcircuit.pdf puede leer, entre otras cosas, que es O (E), conteo de borde lineal.

Answer 2

El algoritmo de Fleury no está completo hasta que se especifica cómo se identifican los bordes del puente. Tarjan dio un algoritmo de tiempo lineal para identificar todos los puentes (ver http://en.wikipedia.org/wiki/Bridge_(graph_theory)), por lo que una implementación ingenua que reordene el algoritmo de Tarjan después de cada borde borrado sería O (E^2). Probablemente haya mejores formas de volver a calcular el conjunto de puentes, pero también hay un mejor algoritmo O (E). (Ver http://www.algorithmist.com/index.php/Euler_tour#Fleury.27s_algorithm; no es mi sitio :))

Answer 3

algoritmo de Fleury implica siguientes pasos:

1. Asegúrese de que la gráfica tiene 0 ó 2 vértices impares.

2. Si hay 0 vértices impares, comience en cualquier lugar. Si hay 2 vértices impares, comienza en uno de ellos.

3. Siga los bordes de a uno por vez. Si puede elegir entre un puente y un puente, siempre elija el que no sea puente.

4. Detener cuando se queden sin bordes.

Si se encuentran los puentes a cabo por el algoritmo de Tarjan y estos puentes se almacenan en una matriz de adyacencia, entonces no necesita ejecutar el algoritmo de Tarjan cada vez para comprobar si un borde es un puente o no. Podemos verificarlo en O (1) vez para todas las demás consultas de bridge. Por lo tanto, la complejidad del tiempo del algoritmo de Flury se puede reducir a O (V + E) {ya que este es un DFS} pero este método necesita O (V2) espacio extra para almacenar puentes.