What is the logic behind this index in Kruskal's minimum spanning tree algorithm?

Question

I don't understand why we are increasing e += 1 when the parents are not same. And why the while loop stops based on e's value? Why we need that index?

def kruskal(self):
    i, e = 0, 0
    ds = dst.disjointSet(self.nodes)
    self.graph = sorted(self.graph, key=lambda graph:graph[2])
    while e < self.v - 1:   # vertices start from zero thats why -1
        s,d,w = self.graph[i]
        i += 1
        x = ds.findParent(s)
        y = ds.findParent(d)
        if x != y:
            e += 1
            self.MST.append([s,d,w])
            ds.union(x, y)
    self.printSolution()

ds is disjointSet's object where findParent and union methods are.

funnydman · Accepted Answer · 2022-08-01 16:08:58Z

0

Variable e, I'd rather call it edges, represents a number of edges here. You may ask a question what is the mininum number of edges needed to connect n vertices? You can easily prove that's n - 1. So we iterate until we have a necessary number of edges to connect all vertices. We're checking parents x!=y to be sure there's no cycle.

answered Aug 1, 2022 at 16:08

funnydman

11.8k4 gold badges51 silver badges67 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

What is the logic behind this index in Kruskal's minimum spanning tree algorithm?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related