CODEWITHSUNDEEP
minimum-spanning-treekruskals-algorithmunion-find
OOProg
OOProg

Reputation: 189

In Kruskal's Algorithm, why does the union procedure check whether r_x == r_y since the opposite was required to call union()?

In Algorithms [DPV] Section 5.1.3, the authors outlined Kruskal's Algorithm. In the algorithm itself, while iterating through all edges on the graph, they compare whether find(u) != find(v). If so, they eventually call the union() procedure on u and v. In union there is a comparison of r_x and r_y which is essentially find(x) and find(y) from the for loop in "kruskal(G,w)". Why are they checking whether find(x) == find(y) in union if the condition for calling union was that find(x) != find(y)?

procedure kruskal(G,w):
for all u in V:
    makeset(u)
X={}
sort the edges E by weight
for all edges {u,v} in E:
    if find(u) != find(v)
        add edge {u,v} to X
        union(u,v)


procedure union(x,y):
r_x = find(x)
r_y = find(y)
if r_x = r_y: return
....more code here

Upvotes: 1

Views: 48

Answers (0)

Related Questions