algorithm - prim - arbol de expansion minima pdf

Actualización de un árbol de expansión mínima cuando se inserta un nuevo borde

Question

Me han presentado el siguiente problema en la universidad:

Sea G = (V, E) una gráfica (no dirigida) con costos c _e > = 0 en los bordes e ∈ E. Supongamos que le dan un árbol de expansión T de costo mínimo en G. Ahora suponga que se agrega un nuevo borde a G , que conecta dos nodos v , t _v ∈ V con costo c .

1. Proporcione un algoritmo eficiente para probar si T sigue siendo el árbol de expansión de costo mínimo con el nuevo borde agregado a G (pero no al árbol T ). Haga que su algoritmo se ejecute en el tiempo O (| E |). ¿Puedes hacerlo en tiempo O (| V |)? Tenga en cuenta las suposiciones que haga sobre la estructura de datos que se utiliza para representar el árbol T y el gráfico G.
2. Supongamos que T ya no es el árbol de expansión de costo mínimo. Dé un algoritmo de tiempo lineal (tiempo O (| E |)) para actualizar el árbol T al nuevo árbol de expansión de costo mínimo.

Esta es la solución que encontré:

Let e1=(a,b) the new edge added
Find in T the shortest path from a to b (BFS)
if e1 is the most expensive edge in the cycle then T remains the MST
else T is not the MST

Parece funcionar, pero puedo hacer que esto se ejecute fácilmente en tiempo O (| V |), mientras que el problema pide el tiempo O (| E |). ¿Me estoy perdiendo de algo?

Por cierto, estamos autorizados a pedir ayuda a alguien, así que no estoy haciendo trampas: D

Answer 1

Creo que su paso Find in T the shortest path from a to b es una operación de orden E.

Answer 2

Creo que un BFS sería suficiente. Y su complejidad es O (| V | + | E |) pero en un árbol | E | es menor que | V | entonces es O (2 | V |) que es O (| V |)

Answer 3

Tiene la idea correcta, aunque puede hacerlo mejor que BFS para la búsqueda de la ruta más corta si almacena el árbol de la manera correcta.

Digamos que un nodo r en T es la raíz (puede seleccionar cualquier nodo y BFS desde allí para generar esta estructura si ha marcado los bordes del árbol en una matriz o una estructura de gráfico de lista de adyacencia), y cada otro nodo tiene un puntero principal y un conteo de profundidad. Para encontrar el camino más corto entre a y b en T :

1. Sea un nodo ''más profundo''; cambiar si es necesario.
2. Recorra los enlaces principales desde a hasta llegar a b o r , almacenando la ruta recorrida y marcando los nodos visitados.
3. Si llegas a b , el camino más corto es el que se recorre.
4. Si alcanzas r , entonces también atraviesa desde b hasta la raíz; Si alcanza el nodo alcanzado en el recorrido de a a r , deténgase. Únete a los dos donde se encuentran y tendrás el camino más corto en T.

La prueba de la validez de este algoritmo se deja como un ejercicio para el lector. Esto es O (| V |) como BFS, pero generalmente también será más rápido. Solo unas pocas configuraciones MST requerirán realmente tiempo O (| V |) en la práctica. Por supuesto, generar el árbol de enlace principal toma O (| V |) tiempo para comenzar, así que esto solo ayuda en algunas circunstancias, como si usas un algoritmo de creación de MST que naturalmente crea esta estructura en el proceso de determinación del MST.

Como dijo otro comentarista, tenga en cuenta que si hay un MST para un gráfico está conectado, entonces | V | <= | E | y así O (| V |) <O (| E |).

Además, para arreglar el árbol en tiempo O (| V |), si es necesario, simplemente encuentre el borde más largo del ciclo y extráigalo, reemplazándolo con el nuevo borde. Hacer esto de manera eficiente con un MST de enlace principal también es un ejercicio para el lector.