# MST Kruskal's algorithm in Python

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
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)
#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)

# 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.KruskalMST()


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.