Prim’s Algorithm: Finding the Minimum Spanning Tree

In the world of computer science and artificial intelligence, efficiency reigns supreme. Whether designing communication networks, electronic circuits, or even analyzing data connections, one question continually arises: how can we connect all the points in a system at the lowest possible cost?

This is precisely the challenge that Prim’s algorithm tackles with remarkable success. Far from being merely an academic curiosity, it is a fundamental tool whose “greedy” logic proves surprisingly powerful. In this article, we will break down how it works and explore the scenarios in which it outperforms alternatives such as Kruskal’s algorithm.

The Foundations of the Minimum Spanning Tree

Before diving into code, it’s essential to fully understand the problem we aim to solve. Prim’s algorithm operates on graphs, mathematical structures composed of points (called nodes or vertices) connected by lines (edges). Each edge carries a “weight,” which can represent distance, financial cost, travel time, or any other metric. The goal is to find a Minimum Spanning Tree (MST).

Problem Definition

Imagine you’re an engineer tasked with connecting several cities via a fiber-optic network. You have two objectives: every city must be connected to all others (either directly or indirectly), and the total cost of cable used must be as low as possible. A spanning tree is a subset of the possible connections that links all nodes without forming any cycles (since a cycle would waste cable). The minimum spanning tree is therefore the spanning tree whose sum of edge weights is the smallest among all possible spanning trees. It represents the optimal solution to our networking problem, ensuring full connectivity at minimal cost.

Greedy Logic

The elegance of Prim’s algorithm lies in its strategically simple approach: it employs a greedy strategy. This means that at each step of building the tree, it makes the locally optimal choice, the one that appears best at that moment, without considering future consequences.

Concretely, it systematically selects the least-cost edge that connects a new node (a city not yet wired) to the set of nodes already connected. Although this strategy may seem short-sighted, it has been mathematically proven to be globally optimal for this specific problem. By repeatedly adding the cheapest possible connection that does not create a cycle, we are guaranteed, by mathematical proof, that the final result will be the tree with the minimal total cost.

Real-World Applications

Although the fiber-optic network example is highly intuitive, Prim’s algorithm has a wide range of applications, many of which operate invisibly in our daily lives. In electronics, it is used to design traces on printed circuit boards, minimizing the total length of copper wiring. In logistics and infrastructure planning, it helps design efficient water or electrical distribution networks. In artificial intelligence and data clustering, variants of this algorithm can group data points by identifying the underlying “skeletal” connections within a point cloud. Whenever elements must be interconnected in the most cost-effective way, Prim’s algorithm provides a robust and efficient solution.

Algorithm Mechanics and Operation

Now that we’ve laid the theoretical groundwork, let’s examine how Prim’s algorithm builds this optimal tree step by step. Its process is highly intuitive and can be likened to an oil stain gradually spreading outward, starting from a single point and continuously expanding to incorporate the nearest, most cost-effective connection until the entire graph is covered.

Principle of Incremental Construction

The algorithm starts from an arbitrarily chosen node. This node forms our initial tree. The process then iterates as follows :

1. Examine all edges that extend from the current partial tree to nodes not yet included in it.
2. Identify the least-cost edge among them.
3. Add this edge and the new node it connects to our tree.
4. Repeat this process until all nodes in the graph are included in the tree.

At each step, our connected “territory” expands by absorbing the nearest and least-cost neighbor, ensuring optimal growth.

Key Data Structures

To implement this logic efficiently, the algorithm relies on a few key data structures to keep track of its progress. Two essential arrays—named intuitively for clarity in Python, are :

• distances: An array that stores, for each node not yet in the tree, the minimum cost required to connect it to the current tree. Initially, all these distances are set to infinity.
• parents: An array that records, for each node, which node in the current tree provides the cheapest connection to it. This allows us to reconstruct the edges of the final minimum spanning tree once the algorithm completes.

Together, these two arrays form the algorithm’s memory, enabling it—at each iteration—to determine the best next move without having to recompute all possible options from scratch.

Cycle Handling

A legitimate question is: how does the algorithm ensure it never creates a cycle? The answer lies in its construction method. Since it always connects a node outside the current tree to a node inside it, it never links two nodes that are already part of the tree. By this simple rule, forming a cycle becomes mathematically impossible. Every new edge adds a fresh “branch” to the tree without ever closing a loop, thereby guaranteeing the acyclic structure required for a spanning tree.

Practical Implementation in Python

Let’s now move from theory to practice. Here’s how to implement Prim’s algorithm in Python, translating the formal pseudocode into clean, functional, and easy-to-understand code. We’ll represent our graph using an adjacency matrix, where graph[i][j] holds the weight of the edge between nodes i and j.

Initializing Variables

The first step is to set up our data structures. We need the number of nodes (n), the distances array, the parents array to reconstruct the tree, and a set to keep track of nodes already visited. We choose a starting point (here, node 0) and initialize its distance to 0.

import sys  # To use infinity

def prim_algorithm(graph):
    n = len(graph)
    
    # Array to store the Minimum Spanning Tree (MST)
    parents = [-1] * n
    
    # Array to store the minimum distances to the tree
    distances = [sys.maxsize] * n
    
    # Boolean list to track nodes already included in the MST
    visited = [False] * n
    
    # Start with the first node
    distances[0] = 0
    parents[0] = -1  # The first node is the root

import sys  # To use infinity

def prim_algorithm(graph):
    n = len(graph)
    
    # Array to store the Minimum Spanning Tree (MST)
    parents = [-1] * n
    
    # Array to store the minimum distances to the tree
    distances = [sys.maxsize] * n
    
    # Boolean list to track nodes already included in the MST
    visited = [False] * n
    
    # Start with the first node
    distances[0] = 0
    parents[0] = -1  # The first node is the root

Main Loop and Updates

The core of the algorithm is a loop that runs n times (once for each node to be added). Within this loop, we first find the unvisited node with the smallest distance. Once found, we mark it as visited. Then, we update the distances of all its neighbors: if a neighbor can be reached at a lower cost through the node we just added, we update both its distance and its parent.

    for _ in range(n):
        # 1. Find the unvisited node with the minimum distance
        min_dist = sys.maxsize
        u = -1
        for i in range(n):
            if not visited[i] and distances[i] < min_dist:
                min_dist = distances[i]
                u = i
        
        # 2. Add this node to our tree
        if u == -1:
            break  # Handles the case where the graph is not connected
        visited[u] = True
        
        # 3. Update distances of its neighbors
        for v in range(n):
            if graph[u][v] > 0 and not visited[v] and graph[u][v] < distances[v]:
                distances[v] = graph[u][v]
                parents[v] = u

    for _ in range(n):
        # 1. Find the unvisited node with the minimum distance
        min_dist = sys.maxsize
        u = -1
        for i in range(n):
            if not visited[i] and distances[i] < min_dist:
                min_dist = distances[i]
                u = i
        
        # 2. Add this node to our tree
        if u == -1:
            break  # Handles the case where the graph is not connected
        visited[u] = True
        
        # 3. Update distances of its neighbors
        for v in range(n):
            if graph[u][v] > 0 and not visited[v] and graph[u][v] < distances[v]:
                distances[v] = graph[u][v]
                parents[v] = u

Complete Code commented

Here is the complete code, assembled into a function that takes the graph’s adjacency matrix as input and prints both the edges of the Minimum Spanning Tree (MST) and its total cost.

import sys

def prim_algorithm(graph):
    """
    Implementation of Prim's algorithm to find the Minimum Spanning Tree (MST).
    :param graph: Adjacency matrix representing a weighted undirected graph.
    """
    n = len(graph)
    
    # Array to store the MST (via parent pointers)
    parents = [-1] * n
    
    # Array to store the minimum cost to connect each node to the MST
    distances = [sys.maxsize] * n
    
    # Boolean list to track which nodes are already included in the MST
    visited = [False] * n
    
    # Start with node 0; its distance is 0
    distances[0] = 0
    parents[0] = -1  # Root node has no parent

    # Main loop: run once for each node
    for _ in range(n):
        # 1. Find the unvisited node with the smallest distance (greedy choice)
        min_dist = sys.maxsize
        u = -1
        for i in range(n):
            if not visited[i] and distances[i] < min_dist:
                min_dist = distances[i]
                u = i
        
        # If no valid node is found, the graph may be disconnected—exit early
        if u == -1:
            break

        # 2. Mark node u as visited (add it to the MST)
        visited[u] = True
        
        # 3. Update distances of all neighbors of u
        for v in range(n):
            # If there's an edge from u to v, v is unvisited,
            # and connecting via u gives a lower cost...
            if graph[u][v] > 0 and not visited[v] and graph[u][v] < distances[v]:
                # ...update v's distance and parent
                distances[v] = graph[u][v]
                parents[v] = u
                
    # Output the result
    print("Edges of the Minimum Spanning Tree:")
    total_cost = 0
    for i in range(1, n):
        weight = graph[i][parents[i]]
        print(f"Edge: {parents[i]} - {i}  Cost: {weight}")
        total_cost += weight
    print(f"Total cost of the tree: {total_cost}")

# Example usage
example_graph = [
    [0, 2, 0, 6, 0],
    [2, 0, 3, 8, 5],
    [0, 3, 0, 0, 7],
    [6, 8, 0, 0, 9],
    [0, 5, 7, 9, 0]
]

prim_algorithm(example_graph)

import sys

def prim_algorithm(graph):
    """
    Implementation of Prim's algorithm to find the Minimum Spanning Tree (MST).
    :param graph: Adjacency matrix representing a weighted undirected graph.
    """
    n = len(graph)
    
    # Array to store the MST (via parent pointers)
    parents = [-1] * n
    
    # Array to store the minimum cost to connect each node to the MST
    distances = [sys.maxsize] * n
    
    # Boolean list to track which nodes are already included in the MST
    visited = [False] * n
    
    # Start with node 0; its distance is 0
    distances[0] = 0
    parents[0] = -1  # Root node has no parent

    # Main loop: run once for each node
    for _ in range(n):
        # 1. Find the unvisited node with the smallest distance (greedy choice)
        min_dist = sys.maxsize
        u = -1
        for i in range(n):
            if not visited[i] and distances[i] < min_dist:
                min_dist = distances[i]
                u = i
        
        # If no valid node is found, the graph may be disconnected—exit early
        if u == -1:
            break

        # 2. Mark node u as visited (add it to the MST)
        visited[u] = True
        
        # 3. Update distances of all neighbors of u
        for v in range(n):
            # If there's an edge from u to v, v is unvisited,
            # and connecting via u gives a lower cost...
            if graph[u][v] > 0 and not visited[v] and graph[u][v] < distances[v]:
                # ...update v's distance and parent
                distances[v] = graph[u][v]
                parents[v] = u
                
    # Output the result
    print("Edges of the Minimum Spanning Tree:")
    total_cost = 0
    for i in range(1, n):
        weight = graph[i][parents[i]]
        print(f"Edge: {parents[i]} - {i}  Cost: {weight}")
        total_cost += weight
    print(f"Total cost of the tree: {total_cost}")

# Example usage
example_graph = [
    [0, 2, 0, 6, 0],
    [2, 0, 3, 8, 5],
    [0, 3, 0, 0, 7],
    [6, 8, 0, 0, 9],
    [0, 5, 7, 9, 0]
]

prim_algorithm(example_graph)

Performance and comparison of strategic

A good developer doesn’t choose an algorithm based on elegance alone, but also on performance. Let’s examine how Prim’s algorithm behaves and when it is the most appropriate choice.

Analysis of the complexity (O(n2))

In our straightforward implementation using an adjacency matrix, the time complexity is O(n²), where n is the number of nodes. Why? The main loop runs n times, and within it, we have another loop that scans all n nodes to find the unvisited node with the smallest distance. This results in n × n = n² operations. This performance is perfectly acceptable for graphs of moderate size. Importantly, this complexity depends solely on the number of nodes—not on the number of edges.

Duel Prim vs Kruskal

Prim’s algorithm isn’t the only player in this field. Its main rival is Kruskal’s algorithm. So, which one should you choose? The answer depends on the density of your graph.

• Prim’s algorithm excels on dense graphs—those with many edges (i.e., a number of edges close to n²). Since its performance depends only on the number of nodes and not on the number of edges, it remains efficient even when nearly every node is connected to every other node.
• Kruskal’s algorithm, which sorts all edges by weight, performs better on sparse graphs—those with relatively few edges (close to n). In such cases, the overhead of sorting a small number of edges is outweighed by the efficiency gained from processing only the necessary connections, making Kruskal the preferred choice for sparse networks.

In summary, if your network has a very large number of possible connections, prefer Prim. If connections are sparse, Kruskal will likely be faster.

Opening IA

Prim’s algorithm is far more than a theoretical exercise. It is a perfect example of a greedy approach that leads to a globally optimal solution. Its ability to build cost-efficient networks makes it an invaluable tool across numerous fields.

For us, as AI enthusiasts, the underlying concepts of graphs and optimal pathfinding are everywhere. They form the foundation of pathfinding in robotics (how a robot finds the shortest route), social network analysis, and even the optimization of neural network architectures. Mastering Prim’s algorithm thus means acquiring a fundamental building block for designing smarter, more efficient systems.