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

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.

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.

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 = {} def add_vertex(self, key): """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 def add_edge(self, src_key, dest_key, weight=1): """Add edge from src_key to dest_key with given weight.""" self.vertices[src_key].add_neighbour(self.vertices[dest_key], 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 def add_neighbour(self, dest, weight): """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 mst.add_vertex(u.get_key()) # add a copy of it to mst 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[0].get_weight(edge[1])) # 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]: # add to mst if not mst.does_vertex_exist(u.get_key()): mst.add_vertex(u.get_key()) if not mst.does_vertex_exist(v.get_key()): mst.add_vertex(v.get_key()) mst.add_edge(u.get_key(), v.get_key(), u.get_weight(v)) mst.add_edge(v.get_key(), u.get_key(), u.get_weight(v)) # 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('Menu') print('add vertex <key>') print('add edge <src> <dest> <weight>') print('mst') print('display') print('quit') while True: do = input('What would you like to do? ').split() operation = do[0] if operation == 'add': suboperation = do[1] if suboperation == 'vertex': key = int(do[2]) if key not in g: g.add_vertex(key) else: print('Vertex already exists.') elif suboperation == 'edge': src = int(do[2]) dest = int(do[3]) weight = int(do[4]) 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): g.add_edge(src, dest, weight) g.add_edge(dest, src, weight) else: print('Edge already exists.') elif operation == 'mst': mst = mst_krusal(g) print('Minimum Spanning Tree:') mst.display() print() elif operation == 'display': g.display() print() elif operation == 'quit': break

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.

Case 1: Undirected Graph Menu add vertex <key> add edge <src> <dest> <weight> 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 Menu add vertex <key> add edge <src> <dest> <weight> 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__.

**If you find any mistake above, kindly email to [email protected]**

**Related Posts:**

- Check Information Technology Books
- Practice Programming MCQs
- Check Python Books
- Apply for Programming Internship
- Apply for Python Internship