kruskal algorithm for finding minimum spanning tree in python

def runKruskalAlgorithm(edges, n):
    # stores the edges present in the MST
    MST = []

    # Initilize Disjoint class
    # Create a singleton set for each element of the universe
    ds = DisjointSet()
    ds.makeSet(n)

    index = 0

    # sort edges by increasing weight 

    edges.sort(key=lambda x: x[2])

    # MST contains v-1 edges 
    while len(MST) != n - 1:
        # consider the next edge with the minimum weight from the graph
        (src, dest, weight) = edges[index]

        index = index + 1

        # find the root of the sets to which two end points
        # vertices of the next edge belongs
        x = ds.find(src)
        y = ds.find(dest)

        # if both end points have different parents, they belong to 
        # different connected components and can be included in MST
        if x != y:
            MST.append((src, dest, weight))
            ds.union(x, y)

    return MST

if __name__ == "__main__":
    # (u, v, w) triplet represent undirected edge from 
    # vertex u to vertex v having weight w
    edges = [
        (0, 1, 7), (1, 2, 8), (0, 3, 5), (1, 3, 9), (1, 4, 7), (2, 4, 5),
        (3, 4, 15), (3, 5, 6), (4, 5, 8), (4, 6, 9), (5, 6, 9)
    ]

    edges_new = []

    for edge in edges:
        (s, d, w) = edge
        w = random.randint(1,20)
        edge = (s, d, w)
        edges_new.append(edge)

    print('edges=' , edges_new)

    # total number of edges 7
    n = 7

    # construct graph
    e = runKruskalAlgorithm(edges_new, n)

    print("mst: ", e)
preveen-stack / nodejs

kruskal algorithm for finding minimum spanning tree in python #29
