# Python Program to Find Minimum Spanning Tree using Kruskal’s Algorithm

«
»

This is a Python program to find a minimum spanning tree of an undirected weighted graph using Krusal’s algorithm.

Problem Description

A spanning tree of a graph can be defined as a graph with minimal set of edges that connect all vertices. A minimum spanning tree of a graph is a spanning tree of the graph with least weight (where the weight is computed by adding the weights of all the edges in the spanning tree). In general, a graph can have multiple minimum spanning trees. The problem is to find a minimum spanning tree of a graph.

Problem Solution

1. Create classes for Graph and Vertex.
2. Create a function mst_krusal that takes a Graph object g as argument.
3. The function will return a Graph object which is a minimum spanning tree of the graph g.
4. An empty graph called mst is created which will hold a MST of the graph g.
5. The algorithm works by first sorting all the edges of g in ascending order by weight.
6. Then the smallest edge is taken from the sorted list.
7. If that edge does not form a cycle when added to mst, it is added.
8. Then the next smallest edge is taken and step 7 is performed again.
9. The above is performed until mst has the same number of vertices as g.
10. To determine whether adding an edge will form a cycle, each vertex in g is assigned a component.
11. When any vertex is added to the MST, its component is updated.
12. If both vertices of an edge belong to the same component, then adding the edge will form a cycle.

Program/Source Code

Here is the source code of a Python program to find the minimum spanning tree of an undirected weighted graph using Krusal’s algorithm. The program output is shown below.

```class Graph:
def __init__(self):
# dictionary containing keys that map to the corresponding vertex object
self.vertices = {}

"""Add a vertex with the given key to the graph."""
vertex = Vertex(key)
self.vertices[key] = vertex

def get_vertex(self, key):
"""Return vertex object with the corresponding key."""
return self.vertices[key]

def __contains__(self, key):
return key in self.vertices

"""Add edge from src_key to dest_key with given weight."""

def does_vertex_exist(self, key):
return key in self.vertices

def does_edge_exist(self, src_key, dest_key):
"""Return True if there is an edge from src_key to dest_key."""
return self.vertices[src_key].does_it_point_to(self.vertices[dest_key])

def display(self):
print('Vertices: ', end='')
for v in self:
print(v.get_key(), end=' ')
print()

print('Edges: ')
for v in self:
for dest in v.get_neighbours():
w = v.get_weight(dest)
print('(src={}, dest={}, weight={}) '.format(v.get_key(),
dest.get_key(), w))

def __len__(self):
return len(self.vertices)

def __iter__(self):
return iter(self.vertices.values())

class Vertex:
def __init__(self, key):
self.key = key
self.points_to = {}

def get_key(self):
"""Return key corresponding to this vertex object."""
return self.key

"""Make this vertex point to dest with given edge weight."""
self.points_to[dest] = weight

def get_neighbours(self):
"""Return all vertices pointed to by this vertex."""
return self.points_to.keys()

def get_weight(self, dest):
"""Get weight of edge from this vertex to dest."""
return self.points_to[dest]

def does_it_point_to(self, dest):
"""Return True if this vertex points to dest."""
return dest in self.points_to

def mst_krusal(g):
"""Return a minimum cost spanning tree of the connected graph g."""
mst = Graph() # create new Graph object to hold the MST

if len(g) == 1:
u = next(iter(g)) # get the single vertex
return mst

# get all the edges in a list
edges = []
for v in g:
for n in v.get_neighbours():
# avoid adding two edges for each edge of the undirected graph
if v.get_key() < n.get_key():
edges.append((v, n))

# sort edges
edges.sort(key=lambda edge: edge.get_weight(edge))

# initially, each vertex is in its own component
component = {}
for i, v in enumerate(g):
component[v] = i

# next edge to try
edge_index = 0

# loop until mst has the same number of vertices as g
while len(mst) < len(g):
u, v = edges[edge_index]
edge_index += 1

# if adding edge (u, v) will not form a cycle
if component[u] != component[v]:

if not mst.does_vertex_exist(u.get_key()):
if not mst.does_vertex_exist(v.get_key()):

# merge components of u and v
for w in g:
if component[w] == component[v]:
component[w] = component[u]

return mst

g = Graph()
print('Undirected Graph')
print('mst')
print('display')
print('quit')

while True:
do = input('What would you like to do? ').split()

operation = do
suboperation = do
if suboperation == 'vertex':
key = int(do)
if key not in g:
else:
elif suboperation == 'edge':
src = int(do)
dest = int(do)
weight = int(do)
if src not in g:
print('Vertex {} does not exist.'.format(src))
elif dest not in g:
print('Vertex {} does not exist.'.format(dest))
else:
if not g.does_edge_exist(src, dest):
else:

elif operation == 'mst':
mst = mst_krusal(g)
print('Minimum Spanning Tree:')
mst.display()
print()

elif operation == 'display':
g.display()
print()

elif operation == 'quit':
break```
Program Explanation

1. An instance of Graph is created.
2. A menu is presented to the user to perform various operations on the graph.
3. mst_krusal is called to get a minimum spanning tree of the graph.
4. This is then displayed.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
Runtime Test Cases
```Case 1:
Undirected Graph
mst
display
quit
What would you like to do? add vertex 1
What would you like to do? add vertex 2
What would you like to do? add vertex 3
What would you like to do? add vertex 4
What would you like to do? add vertex 5
What would you like to do? add vertex 6
What would you like to do? add edge 1 2 10
What would you like to do? add edge 1 5 30
What would you like to do? add edge 1 4 40
What would you like to do? add edge 2 5 20
What would you like to do? add edge 4 5 40
What would you like to do? add edge 5 3 40
What would you like to do? add edge 5 6 70
What would you like to do? add edge 3 6 50
What would you like to do? mst
Minimum Spanning Tree:
Vertices: 1 2 3 4 5 6
Edges:
(src=1, dest=4, weight=40)
(src=1, dest=2, weight=10)
(src=2, dest=5, weight=20)
(src=2, dest=1, weight=10)
(src=3, dest=5, weight=40)
(src=3, dest=6, weight=50)
(src=4, dest=1, weight=40)
(src=5, dest=2, weight=20)
(src=5, dest=3, weight=40)
(src=6, dest=3, weight=50)

What would you like to do? quit

Case 2:
Undirected Graph
mst
display
quit
What would you like to do? add vertex 1
What would you like to do? add vertex 2
What would you like to do? add vertex 3
What would you like to do? add edge 1 2 10
What would you like to do? add edge 1 3 20
What would you like to do? add edge 2 3 30
What would you like to do? mst
Minimum Spanning Tree:
Vertices: 1 2 3
Edges:
(src=1, dest=3, weight=20)
(src=1, dest=2, weight=10)
(src=2, dest=1, weight=10)
(src=3, dest=1, weight=20)

What would you like to do? quit```

Sanfoundry Global Education & Learning Series – Python Programs.

To practice all Python programs, here is complete set of 150+ Python Problems and Solutions. 