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

user_15274883 0
Viewed 29

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

graph-algorithm data-structures algorithm
1 Answers

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).

user_21446690
Related