How to Find Minimum Spanning Tree Using Prim’s Algorithm in Python

Submitted by razormist on Sunday, March 15, 2026 - 22:50.

In this tutorial, we will learn how to program “How to Find a Minimum Spanning Tree Using Prim’s Algorithm in Python.” The main objective is to understand how to find a minimum spanning tree using Prim’s Algorithm. This tutorial will guide you step by step through the process of finding a minimum spanning tree. By the end of this tutorial, you will have a solid understanding of how Prim’s Algorithm works in Python, helping you strengthen your problem-solving abilities and improve your overall coding skills in data structure implementation.

This topic is straightforward and easy to understand. By simply following the instructions provided, you will be able to complete it with ease. The program will guide you step by step through the process of implementing Prim’s Algorithm to find a Minimum Spanning Tree. So, let’s dive into the coding process and start implementing the solution to gain a deeper understanding of graph algorithms in Python.

Getting Started:

First you will have to download & install the Python IDLE's, here's the link for the Integrated Development And Learning Environment for Python https://www.python.org/downloads/.

Creating Main Function

This is the main function of the application. The following code will display a simple GUI in terminal console that will display program. To do this, simply copy and paste these blocks of code into the IDLE text editor.

class Graph:
    def __init__(self):
        self.vertices = {}
 
    def add_vertex(self, key):
        vertex = Vertex(key)
        self.vertices[key] = vertex
 
    def get_vertex(self, key):
        return self.vertices[key]
 
    def __contains__(self, key):
        return key in self.vertices
 
    def add_edge(self, src_key, dest_key, weight=1):
        self.vertices[src_key].add_neighbour(self.vertices[dest_key], weight)
 
    def does_edge_exist(self, src_key, 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(f'(src={v.get_key()}, dest={dest.get_key()}, weight={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 self.key
 
    def add_neighbour(self, dest, weight):
        self.points_to[dest] = weight
 
    def get_neighbours(self):
        return self.points_to.keys()
 
    def get_weight(self, dest):
        return self.points_to[dest]
 
    def does_it_point_to(self, dest):
        return dest in self.points_to
 
 
def mst_prim(g):
 
    mst = Graph()
 
    if not g:
        return mst
 
    nearest_neighbour = {}
    smallest_distance = {}
    unvisited = set(g)
 
    u = next(iter(g))
    mst.add_vertex(u.get_key())
    unvisited.remove(u)
 
    for n in u.get_neighbours():
        if n is u:
            continue
        nearest_neighbour[n] = mst.get_vertex(u.get_key())
        smallest_distance[n] = u.get_weight(n)
 
    while smallest_distance:
 
        outside_mst = min(smallest_distance, key=smallest_distance.get)
        inside_mst = nearest_neighbour[outside_mst]
 
        mst.add_vertex(outside_mst.get_key())
 
        mst.add_edge(outside_mst.get_key(), inside_mst.get_key(),
                     smallest_distance[outside_mst])
        mst.add_edge(inside_mst.get_key(), outside_mst.get_key(),
                     smallest_distance[outside_mst])
 
        unvisited.remove(outside_mst)
 
        del smallest_distance[outside_mst]
        del nearest_neighbour[outside_mst]
 
        for n in outside_mst.get_neighbours():
 
            if n in unvisited:
 
                if n not in smallest_distance:
                    smallest_distance[n] = outside_mst.get_weight(n)
                    nearest_neighbour[n] = mst.get_vertex(outside_mst.get_key())
 
                else:
                    if smallest_distance[n] > outside_mst.get_weight(n):
                        smallest_distance[n] = outside_mst.get_weight(n)
                        nearest_neighbour[n] = mst.get_vertex(outside_mst.get_key())
 
    return mst
 
 
# MAIN PROGRAM
while True:
 
    print("\n============= Find Minimum Spanning Tree Using Prim’s Algorithm =============\n")
 
    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("\nWhat would you like to do? ").split()
 
        if len(do) == 0:
            continue
 
        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(f"Vertex {src} does not exist.")
                elif dest not in g:
                    print(f"Vertex {dest} does not exist.")
                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_prim(g)
 
            print("\nMinimum Spanning Tree:")
            mst.display()
            print()
 
        elif operation == "display":
 
            g.display()
            print()
 
        elif operation == "quit":
            break
 
        else:
            print("Invalid command.")
 
    # Try Again Option
    opt = input("\nDo you want to try again? (yes/no): ").strip().lower()
 
    if opt == "no":
        print("Exiting program...")
        break
    elif opt != "yes":
        print("Invalid choice. Exiting program...")
        break

This Python program implements an undirected weighted graph using `Graph` and `Vertex` classes. Users can add vertices and edges, display the graph, and compute the Minimum Spanning Tree (MST) using Prim’s algorithm, which builds the MST by repeatedly connecting the nearest unvisited vertex with the smallest edge weight. The program features an interactive console menu with input validation, allowing users to manage the graph and view the MST efficiently.

Output:

There you have it we successfully created How to Find Minimum Spanning Tree Using Prim’s Algorithm in Python. I hope that this simple tutorial help you to what you are looking for. For more updates and tutorials just kindly visit this site. Enjoy Coding!

More Tutorials for Python Language

Python Tutorials