Comment est-il possible que la complexité de l'algorithme de Boruvka soit O (E * logV)?

Question

1 Begin with a connected graph G containing edges of distinct weights, and an empty set of edges T 
2 While the vertices of G connected by T are disjoint: 
3 Begin with an empty set of edges E 
4 For each component: 
5  Begin with an empty set of edges S 
6  For each vertex in the component: 
7  Add the cheapest edge from the vertex in the component to another vertex in a disjoint component to S 
8  Add the cheapest edge in S to E 
9 Add the resulting set of edges E to T. 
10 The resulting set of edges T is the minimum spanning tree of G. 

De Wikipédia. Je comprends que la boucle externe est logV puisque vous rejoignez des ensembles. Mais vient ensuite la boucle interne. Si vous utilisez des relations d'équivalence pour garder une trace des ensembles, cela signifie que vous obtenez seulement l'élément représentant l'ensemble, donc vous ne pouvez pas déterminer le bord avec le plus petit poids entre les deux ensembles parce que vous ne faites pas avoir tous les éléments. Si vous modifiez la structure pour contenir des références aux enfants, vous devez toujours obtenir tous les enfants de chaque ensemble. Cela signifie, pire scénario, O (V/2) = O (V) pour chaque ensemble. Ensuite, vous devez toujours trouver le plus petit bord reliant les deux, ce qui signifie parcourir tous les bords reliant les deux composants. Vous devez donc parcourir chaque nœud et voir si son front se connecte à un élément de l'autre composant, et si c'est le cas, s'il est plus petit que le bord minimum que vous avez actuellement. Cela signifie une boucle externe pour itérer sur les nœuds et une boucle interne pour parcourir les bords de ces nœuds - O (V E). Comme il se trouve dans une boucle O (logV), vous obtenez O (logV V * E).

Maintenant, il semble que vous deviez parcourir tous les bords, mais comment choisir le bord minimum entre les 2 composants? Je peux dire si une arête donnée connecte des noeuds dans différents composants, mais je ne peux pas dire lequel les reliant a un poids minimum. Et si je reçois celui avec le poids minimum, il pourrait ne pas les relier.

Answer 1

Si les tables de hachage sont autorisées, alors je vois comment cela peut être un algorithme O (Elog N). Chaque composant est enregistré sous la forme d'un ensemble de hachage différent. Initialement, chaque ensemble contient un seul noeud. L'étape de trouver les "ponts" minimum pour tous les composants prend le temps O (E), puisque nous examinons chaque bord au plus deux fois, et nous supposons une recherche de temps constante dans les ensembles de hachage. Ensuite, nous procédons en fusionnant les ensembles, ce qui prend le temps O (N). Puisque le graphe est connecté, E> = N-1, nous avons donc un coût total de O (E) par itération.

--EDIT--

Après le commentaire de throwawayacct, il n'y a pas besoin de structures de hachage à tous. A chaque itération, nous avons un graphe de forêt résultant de l'itération précédente, donc nous pouvons recalculer ses composantes connectées en temps O (E). Cela peut être fait par exemple par une simple traversée DFS à partir de tous les nœuds, qui définit une "couleur" unique pour chaque composant. Ensuite, en balayant les bords pour trouver des ponts, nous considérons seulement les arêtes reliant des nœuds de couleur différente.