CODEWITHSUNDEEP
algorithmdata-structuresgraph-algorithm
Rutuparn Dalvi
Rutuparn Dalvi

Reputation: 21

Kruskal's MST : Union operation using Union-Find DS: Guarantee on join taking place between the nodes with least edge weight

In the Minimum Spanning Tree, we require to join the edges with minimum weight before we move on to other edges. To perform the join we use the union operation of the UF DS, which joins the representative elements of the disjoint data sets. Is there a guarantee that the representative elements will be the nodes with least edge weight that we intend to join? The join could very well take place at other nodes of the components to be joined, if I am thinking this right.

Thanks

Upvotes: 2

Views: 133

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65458

No, there's no such guarantee. Fortunately, Kruskal's uses the disjoint-set data structure to maintain the connectivity of the edges scanned so far, and the representatives don't matter for this purpose. If you want the tree structure in the end, you need to do something different (DFS on the set of edges, sub a dynamic tree for the disjoint-set data structure so that you can join the actual endpoints, use Prim's instead).

Upvotes: 2

Related Questions