algorithm - prim - problema del arbol de minima expansion ejercicios

Actualizar árbol de expansión mínima con modificación de borde

Question

Un gráfico (bordes de peso positivo) con un MST Si algún borde, e se modifica a un nuevo valor, ¿cuál es la mejor manera de actualizar el MST sin rehacerlo completamente? Creo que esto se puede hacer en tiempo lineal. Además, parece que necesitaría un algoritmo diferente basado en si 1) e ya es parte del MST y 2) si el nuevo borde, e es más grande o más pequeño que el original

Answer 1

Hay 4 casos:

1. El borde está en MST y usted disminuye el valor de borde:
   MST actual sigue siendo MST

2. El borde no está en MST y usted disminuye el valor del borde:
   Añadir este borde a la MST. Ahora tienes exactamente 1 ciclo.
   Según la propiedad del ciclo en MST, debe encontrar y eliminar el borde con el valor más alto que se encuentre en ese ciclo. Puedes hacerlo usando dfs o bfs. Complejidad O (n).

3. Edge está en MST y usted aumenta su valor de edge:
   Quitar este borde de MST. Ahora tienes 2 componentes conectados que deben estar conectados. Puede calcular ambos componentes en O (n) (bfs o dfs). Necesita encontrar una ventaja con el valor más pequeño que conecta estos componentes. Iterar sobre los bordes en orden ascendente por su valor. Complejidad O (n).

4. Edge no está en MST e incrementas su valor de edge:
   MST actual sigue siendo MST

Answer 2

Mi solución O (n) se basa en la suposición de que, antes de comenzar a modificar los bordes, debe encontrar MST (no se incluye en el gráfico). Para hacerlo, puede usar el algoritmo de Kruskal que funciona en O (n log n), y como efecto secundario produce una lista ordenada de aristas. Su costo está dominado por la clasificación, de modo que cuando modifica el peso de un borde, puede eliminarlo de la lista ordenada en O (log n), e insertarlo nuevamente con un nuevo valor, también en O (log n), y finalmente llamar a Kruskal Algoritmo de nuevo, que ahora se ejecuta en tiempo lineal porque los bordes están ordenados.

Esta es una solución lineal que solicitó, pero parece que se puede hacer más rápido.