Un gráfico (bordes de peso positivo) con un MST Si un borde, e se modifica a un nuevo valor, ¿cuál es la mejor manera de actualizar el MST sin rehacerlo por completo? Creo que esto se puede hacer en tiempo lineal. Además, parece que necesitaría un algoritmo diferente en función de 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 originalActualizar árbol de expansión mínimo con modificación de borde
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 proporciona con 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 bordes. Su costo está dominado por la clasificación, por lo 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 como usted solicitó, pero parece que se puede hacer más rápido.
Hay 4 casos:
Edge está en MST y disminuyendo el valor del borde:
actual MST sigue siendo MST
Edge no está en MST y la disminución value of edge:
Agregue este borde al MST. Ahora tienes exactamente 1 ciclo.
Basado en cycle property en MST necesita encontrar y eliminar el borde con el valor más alto que está en ese ciclo. Puedes hacerlo usando dfs o bfs. Complejidad O (n).
Edge está en MST y el aumento de su valor de borde:
Poner esta borde del MST. Ahora tiene 2 componentes conectados que deberían estar conectados. Puede calcular ambos componentes en O (n) (bfs o dfs). Necesita encontrar el borde con el valor más pequeño que conecta estos componentes. Iterate sobre los bordes en orden ascendente por su valor. Complejidad O (n).
Edge no está en MST y el aumento de su valor de borde:
actual MST MST sigue siendo
CASO 3. NO ES O (N). para iterar sobre los bordes en orden ascendente. Necesitamos ordenarlos. hay O (n^2) bordes. incluso si tomamos los bordes ordenados que calculamos durante la creación de mst, todavía tendría que pasar por estos (todos pueden ser en el peor de los casos) bordes. –
Podría ser O (n). 1. Quite el borde cuyo peso se aumentó y realice un seguimiento de los dos nodos que estaban conectados por este borde 2. Ejecute bfs/dfs comenzando con estos dos nodos que ahora están en 2 conjuntos disjuntos. Deberías de alguna manera hash los vértices visitados para que puedas acceder a ellos en O (1). Crearía dos tablas hash, una para cada conjunto disjunto. 3. Pasa por todos los bordes en E-E 'donde G = (V, E) y MST = (V, E'). Si cualquier borde contiene 1 nodo de cada hashtable, conecta los dos conjuntos disjuntos. Mantenga una variable mínima para determinar qué borde conectó los dos conjuntos y tuvo el menor peso. O (E) – Olshansk
Olshansk, O (E) es O (n^2), como señaló Ashish.Hasta donde puedo decir, la eliminación requiere O (n^2), porque para cada borde (supongamos que ya está ordenado en una lista), necesitamos encontrar el borde más pequeño que conecta los dos árboles de expansión. Esto puede llevar hasta O (n^2) si el único borde que los conecta es también el borde con el valor más alto. –
Unfortunetly en el algoritmo de Kruskal necesita unión-que no es O (1) ;/ –