CODEWITHSUNDEEP
python-3.xminimum-spanning-treekruskals-algorithm
VRM
VRM

Reputation: 103

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

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.

Upvotes: 0

Views: 63

Answers (1)

funnydman
funnydman

Reputation: 11326

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.

Upvotes: 0

Related Questions