Mise à jour minimum spanning tree avec modification de bord
Un graphique (positive poids des arêtes) avec une MST
Si certains de bord, e est modifié à une nouvelle valeur, quelle est la meilleure façon de mettre à jour le MST sans devoir tout refaire. Je pense que cela peut être fait en temps linéaire. Aussi, il semble que j'aurais besoin d'un algorithme différent selon que 1) e est déjà une partie du MST, et 2) si la nouvelle arête e est plus grande ou plus petite que l'originale
OriginalL'auteur Peeber Burns | 2012-03-29
Vous devez vous connecter pour publier un commentaire.
Il y a 4 cas:
De bord est en MST et vous décroissant de bord:
Actuel MST est toujours MST
Bord n'est pas en MST et vous décroissant de bord:
Ajouter cette bord de la MST. Maintenant, vous avez exactement 1 cycle.
Basé sur cycle de la propriété dans MST vous avez besoin pour trouver et enlever les bordures avec la valeur la plus élevée qui est sur ce cycle. Vous pouvez le faire en utilisant dfs ou bfs. Complexité O(n).
De bord est en MST et vous en augmentant sa valeur de bord:
Supprimer cet avantage de MST. Maintenant, vous avez 2 composantes connexes qui doivent être connectés. Vous pouvez calculer à la fois les composants en O(n) (bfs ou dfs). Vous avez besoin de trouver de bord avec la plus petite valeur qui relie ces composants. Itérer sur les arêtes par ordre croissant de leur valeur. Complexité O(n).
Bord n'est pas en MST et vous en augmentant sa valeur de bord:
Actuel MST est toujours MST
Il pourrait être O(n). 1. Retirez l'arête dont le poids a été augmenté, et de garder la trace des deux nœuds connectés par cette arête 2. Exécuter bfs/dfs a partir de ces deux nœuds qui sont maintenant en 2 ensembles disjoints. Vous devez en quelque sorte de hachage les sommets visités de sorte que vous pouvez y avoir accès en O(1). Je voudrais créer deux tables de hachage, une pour chaque disjoints ensemble. 3. Boucle sur toutes les arêtes de E-E' où G=(V,E) et MST=(V,E'). Si tout bord contient 1 nœud de chaque table de hachage, il relie les deux ensembles disjoints. Maintenir un min variable pour déterminer le bord de qui reliait les deux ensembles et ont le plus faible poids. O(E)
Olshansk, O(E) est O(n^2), Ashish souligné. Aussi loin que je peux dire, l'élimination nécessite O(n^2), parce que pour chaque arête (à supposer triés déjà dans une liste), nous avons besoin de trouver la plus petite arête qui relie les deux arbres de recouvrement. Cela peut prendre jusqu'à O(n^2) si le bord seulement qui les relie est également à la pointe de la technologie avec la valeur la plus élevée.
Il est O(n). Lorsque la variable n'est pas spécifié, il se réfère à la taille de l'entrée de l'algorithme, qui, dans ce cas, sans doute inclut le graphe G. Si ... n Θ (V+E). En passant, O est la limite supérieure de ... f(n) est O(g(n)) signifie que f(n)<=des multiples * g(n) (pour n grand). Dire une fonction f(n) est O(n^2) pourrait signifier qu'il est f(n)=1 ou f(n)=n.
Intuitivement, je comprends les cas 1 et 4, mais quelqu'un peut-il m'aider en donnant une preuve formelle d'entre eux s'il vous plaît?
OriginalL'auteur Jarosław Gomułka
Mon O(n) la solution est basée sur l'hypothèse, qu'avant de vous commencer à modifier les bords, vous devriez trouver les MST (n'est pas donné avec le graphique). Pour ce faire, vous pouvez utiliser Kruskal algorithme qui fonctionne en temps O(n log n), et comme un effet secondaire produit de la liste triée des bords. Son coût est dominé par le tri, de sorte que lorsque vous modifier le poids d'un bord, vous pouvez le supprimer de liste triée en O(log n), et insérez-le de nouveau avec la nouvelle valeur, également en O(log n), et enfin l'appel de Kruskal algorithme de nouveau, qui maintenant s'exécute en temps linéaire, car les bords sont triés.
C'est un linéaire de la solution comme vous l'avez demandé, mais il semble que cela peut être fait plus rapidement.
Sûr, mais inverse Ackermann exécution est très rapide.
OriginalL'auteur KCH