MST Kruskal's algorithm in Python

Question

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

Answer 1

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.