1
\$\begingroup\$

I have this code for finding MST for undirected weighted graph, currently works for graphs with maximum 10 vertices. How can I update the code to scale for larger graphs?

# Python program for Kruskal's algorithm to find Minimum Spanning Tree
# of a given connected, undirected and weighted graph

from collections import defaultdict

#Class to represent a graph
class Graph:

    def __init__(self,vertices):
        self.V= vertices #No. of vertices
        self.graph = [] # default dictionary to store graph


    # function to add an edge to graph
    def addEdge(self,u,v,w):
        self.graph.append([u,v,w])

    # A utility function to find set of an element i
    # (uses path compression technique)
    def find(self, parent, i):
        if parent[i] == i:
            return i
        return self.find(parent, parent[i])

    # A function that does union of two sets of x and y
    # (uses union by rank)
    def union(self, parent, rank, x, y):
        xroot = self.find(parent, x)
        yroot = self.find(parent, y)

        # Attach smaller rank tree under root of high rank tree
        # (Union by Rank)
        if rank[xroot] < rank[yroot]:
            parent[xroot] = yroot
        elif rank[xroot] > rank[yroot]:
            parent[yroot] = xroot
        #If ranks are same, then make one as root and increment
        # its rank by one
        else :
            parent[yroot] = xroot
            rank[xroot] += 1

    # The main function to construct MST using Kruskal's algorithm
    def KruskalMST(self):

        result =[] #This will store the resultant MST

        i = 0 # An index variable, used for sorted edges
        e = 0 # An index variable, used for result[]

        #Step 1:  Sort all the edges in non-decreasing order of their
        # weight.  If we are not allowed to change the given graph, we
        # can create a copy of graph
        self.graph =  sorted(self.graph,key=lambda item: item[2])
        #print self.graph

        parent = [] ; rank = []

        # Create V subsets with single elements
        for node in range(self.V):
            parent.append(node)
            rank.append(0)

        # Number of edges to be taken is equal to V-1
        while e < self.V -1 :

            # Step 2: Pick the smallest edge and increment the index
            # for next iteration
            u,v,w =  self.graph[i]
            i = i + 1
            x = self.find(parent, u)
            y = self.find(parent ,v)

            # If including this edge does't cause cycle, include it
            # in result and increment the index of result for next edge
            if x != y:
                e = e + 1  
                result.append([u,v,w])
                self.union(parent, rank, x, y)          
            # Else discard the edge

        # print the contents of result[] to display the built MST
        print "Following are the edges in the constructed MST"
        for u,v,weight  in result:
            #print str(u) + " -- " + str(v) + " == " + str(weight)
            print ("%d -- %d == %d" % (u,v,weight))
 g = Graph(14)
 g.addEdge(0, 1, 7)
 g.addEdge(0, 3, 3)
 g.addEdge(1, 2, 3)
 g.addEdge(1, 4, 2)
 g.addEdge(2, 5, 2)
 g.addEdge(3, 4, 3)
 g.addEdge(3, 6, 2)
 g.addEdge(4, 5, 5)
 g.addEdge(4, 7, 7)
 g.addEdge(5, 8, 3)
 g.addEdge(6, 7, 3)
 g.addEdge(6, 9, 1)
 g.addEdge(7, 8, 7)
 g.addEdge(7, 10, 3)
 g.addEdge(9, 12, 4)
 g.addEdge(9, 10, 1)
 g.addEdge(10, 11, 6)
 g.addEdge(10, 13, 7)
 g.addEdge(11, 12, 6)
 g.addEdge(11, 14, 2)
 g.addEdge(12, 13, 4)
 g.addEdge(13, 14, 5)

 g.KruskalMST()
\$\endgroup\$
2
\$\begingroup\$

Why do you assume this code is limited to 10 vertices? This code comes from: http://www.geeksforgeeks.org/greedy-algorithms-set-2-kruskals-minimum-spanning-tree-mst/

But you have an error in use:

 g = Graph(14)

Defines a graph with 14 vertices but then you used 0-14 which is 15 vertices. Either use:

 g = Graph(15)

Or remove all the edges with vertex 14.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.