Prim’s Algorithm Explained with Example

• Explains Minimum Spanning Trees (MSTs) from the ground up and why they are critical in cost-efficient network design
• Breaks down Prim’s Algorithm step by step, showing how it grows an MST using a greedy approach
• Covers algorithm logic, pseudocode, and implementation choices, including adjacency matrix vs adjacency list
• Walks through a complete example, clearly showing how the MST is built and why each edge is chosen
• Provides ready-to-use implementations in C, C++, Python, and Java, along with performance considerations

Every major network you use today, including Wi-Fi, electricity grids, and transportation routes, was made possible by an effective solution to a cost-minimization issue. Prim’s Algorithm is one of the core ideas that makes this possible.

If you’re learning data structures, preparing for interviews, or working with graphs in real systems, understanding Prim’s Algorithm is not optional. It directly connects theory (graphs, greedy strategy) with practical optimization problems where cost, distance, or resources must be minimized.

Prim's Algorithm is widely used in competitive programming, examinations, interviews, and actual network design. It also scales well with priority queues. Gaining proficiency in it entails studying how optimum systems are constructed rather than merely remembering code.

When designing networks, whether for computers, power systems, roads, or communication, finding the most efficient way to connect everything is essential. This is where the concept of Minimum Spanning Trees (MSTs) comes in.

What is a Spanning Tree?

 A spanning tree is a special kind of subgraph formed from a connected, undirected graph.

• It includes all the vertices (nodes) from the original graph.
• It is a tree, meaning it has no cycles (no closed loops), and it is minimally connected; removing even a single edge would disconnect it.

 In simple terms, a spanning tree connects all points in a network using the minimum number of connections needed, without forming any loops.

What is a Minimum Spanning Tree (MST)?

A spanning tree containing an additional condition is called a minimal spanning tree. Among all possible spanning trees for a given graph, the MST is the one with the smallest total edge weight. The "weight" here usually represents cost, distance, time, or any measure you want to minimize.

In other words, an MST connects all the vertices together with the least possible total cost.

Example: Imagine cities connected by roads, where each road has a cost to build. A minimum spanning tree would connect all cities together with the least total cost, ensuring there are no unnecessary roads.

Why MSTs Matter?

Minimum spanning trees are extremely important in real-world optimization problems, such as:

• Telecommunications: Designing telephone, internet, or fiber optic networks with the minimum infrastructure cost while still connecting all users.
  
• Electrical Grids: Planning efficient layouts for connecting power stations and distribution centers while using the least amount of wiring and resources.
  
• Computer Networks: Setting up local area networks (LANs) or larger systems where the goal is to minimize cabling costs while maintaining full connectivity.
  
• Road Networks: Developing road or rail systems that connect multiple cities or towns using the least amount of roadway construction, reducing both cost and environmental impact.

Prim's Algorithm, one of the most important tools for finding minimum spanning trees, has a fascinating history that spans multiple mathematicians and decades.

1930: The Beginning — Vojtěch Jarník

The original concept was first described by Vojtěch Jarník, a Czech mathematician. Jarník developed a method for efficiently connecting points in a graph with the least total edge weight, laying the early foundations for what we now recognize as Prim’s Algorithm.

1957: Rediscovery — Robert C. Prim

Almost three decades later, the idea was rediscovered independently by Robert C. Prim, an American mathematician working at Bell Labs. Prim refined the method into a more practical form, suitable for use in real-world applications such as telecommunications network design.

1959: Further Popularization — Edsger W. Dijkstra

In 1959, the famous computer scientist Edsger W. Dijkstra built upon Prim’s work. Dijkstra's improvements and his broader contributions to graph algorithms helped popularize the method even further in the growing field of computer science.

Because of these multiple contributions, the algorithm is known by several names, including:

• Jarník’s Algorithm
• Prim–Jarník Algorithm
• Prim–Dijkstra Algorithm
• DJP Algorithm (short for Dijkstra, Jarník, and Prim)

Prim's Algorithm worked at Bell Labs, paired with Dijkstra’s influential optimization strategies, ensured that the algorithm became a standard approach for computing minimum spanning trees in both academic study and modern practical applications.

Prim's​‍​‌‍​‍‌​‍​‌‍​‍‌ algorithm is among the greedy algorithms which is employed to obtain a minimum spanning tree (MST) from a connected, undirected graph. A minimum spanning tree is the set of edges with the minimum total weight, which connects all the vertices of the graph, and does not contain any cycles. 

The procedure of the algorithm is to initially take any vertex and then expand the MST by one edge each time. It goes on adding the least edge, which links a vertex in the MST with a vertex outside the MST. The process is repeated until all vertices become part of the ​‍​‌‍​‍‌​‍​‌‍​‍‌MST.

Prim’s Algorithm can be implemented in several ways depending on the graph’s size and density, as well as the programming language used. Below, you’ll find a clear algorithm and pseudocode, explanations of key implementation choices, and sample code in Python, C++, and Java.

Prim's Algorithm starts from a single node and grows the MST one edge at a time.

Algorithm Steps:

1. Start: Pick any node to start.
2. Initialization: Add all edges connected to the start node into a priority queue (min-heap based on weight).
3. Selection: Pick the edge with the least weight.
4. Expansion: If it connects to an unvisited node, add the edge and the new node to the MST.
5. Repeat: Insert new edges connected to the new node into the queue.
6. Stop: When all nodes are part of the MST.

Important: Cycles are automatically avoided because we only add edges leading to new nodes.

Pseudocode for Prim’s Algorithm

The following pseudocode outlines the general steps of Prim’s Algorithm in a language-agnostic way:

PRIM(G = (V, E), w):
    for each vertex v in V:
        key[v] ← ∞
        parent[v] ← NIL
        inMST[v] ← false

    choose any start vertex s
    key[s] ← 0

    while there exists a vertex u not in MST:
        u ← vertex with minimum key[u] such that inMST[u] = false
        inMST[u] ← true

        for each vertex v adjacent to u:
            if inMST[v] = false and w(u, v) < key[v]:
                key[v] ← w(u, v)
                parent[v] ← u

    return parent

Alternatively, here’s a more formal pseudocode variant:

T ← ∅
U ← {starting_vertex}

while U ≠ V do
    let (u, v) be the lowest-cost edge
        such that u ∈ U and v ∈ (V − U)
    T ← T ∪ {(u, v)}
    U ← U ∪ {v}

return T

Implementation Approaches: Adjacency Matrix vs. Adjacency List

• Adjacency Matrix:

It is good for dense graphs (a graph in which most of the vertices are interconnected). The matrix allows quick lookups but utilizes more memory for large, sparse graphs.

• Adjacency List:

It is better for sparse graphs (a graph in which most of the vertices are not interconnected). When used along with a priority queue (min-heap), this approach becomes more efficient in terms of both time and space.

Tip:

For dense graphs, an adjacency matrix with O(V²) complexity is acceptable. For large or sparse graphs, use an adjacency list and a priority queue for optimal O(E log V) performance.

“Let’s now see how these steps work on an actual graph.”

One of the best ways to understand Prim’s Algorithm is to follow the example of a simple, weighted, undirected graph, which is done here, step by step, the algorithm grows the Minimum Spanning Tree (MST), and how the auxiliary data structures change at each ​‍​‌‍​‍‌​‍​‌‍​‍‌step.

Consider the graph:

     A
   /    \
  1      3
 B----C
  \      / 
   2   4
     D

Vertices: {A, B, C, D}

Edges:

• A-B: 1
• A-C: 3
• B-D: 2
• C-D: 4
• B-C: 5

Step-by-Step Execution

We​‍​‌‍​‍‌​‍​‌‍​‍‌ will use an adjacency matrix representation along with a simple array to indicate which nodes are part of the MST.

Initialization

Start vertex: A
Selected vertices: {A}
MST edges: (empty)

Edge candidates:

• A–B (1)
• A–C (3)

Step 1: Add the Smallest Edge

Choose: A–B (weight 1, the smallest among candidates)

Add to MST: A–B
Selected vertices: {A, B}
MST edges: {A–B}

New edge candidates:

• A–C (3)
• B–D (2)
• B–C (5)

Step 2: Add the Next Smallest Edge

Choose: B–D (weight 2)

Add to MST: B–D
Selected vertices: {A, B, D}
MST edges: {A–B, B–D}

New edge candidates:

• A–C (3)
• D–C (4)
• B–C (5)

Step 3: Add the Next Smallest Edge

Choose: A–C (weight 3)

Add to MST: A–C
Selected vertices: {A, B, C, D}
MST edges: {A–B, B–D, A–C}

Step 4: All Vertices Included

The MST is complete (it contains V-1 = 3 edges).

Final MST edges:

• A–B
• B–D
• A–C

Total weight:
1 + 2 + 3 = 6

Graph Mapping

We map vertices to indices for implementation:

C Implementation (Adjacency Matrix)

#include <stdio.h>
#include <limits.h>

#define V 4

int minKey(int key[], int mstSet[]) {
    int min = INT_MAX, minIndex;
    for (int v = 0; v < V; v++)
        if (!mstSet[v] && key[v] < min)
            min = key[v], minIndex = v;
    return minIndex;
}

void primMST(int graph[V][V]) {
    int parent[V], key[V], mstSet[V];

    for (int i = 0; i < V; i++)
        key[i] = INT_MAX, mstSet[i] = 0;

    key[0] = 0;
    parent[0] = -1;

    for (int count = 0; count < V - 1; count++) {
        int u = minKey(key, mstSet);
        mstSet[u] = 1;

        for (int v = 0; v < V; v++)
            if (graph[u][v] && !mstSet[v] && graph[u][v] < key[v]) {
                parent[v] = u;
                key[v] = graph[u][v];
            }
    }

    printf("Edge   Weight\n");
    for (int i = 1; i < V; i++)
        printf("%d - %d    %d\n", parent[i], i, graph[i][parent[i]]);
}

int main() {
    int graph[V][V] = {
        {0, 1, 3, 0},
        {1, 0, 5, 2},
        {3, 5, 0, 4},
        {0, 2, 4, 0}
    };

    primMST(graph);
    return 0;
}

C++ Implementation (Adjacency Matrix)

#include <iostream>
#include <climits>
using namespace std;

#define V 4

int minKey(int key[], bool mstSet[]) {
    int min = INT_MAX, minIndex;
    for (int v = 0; v < V; v++)
        if (!mstSet[v] && key[v] < min)
            min = key[v], minIndex = v;
    return minIndex;
}

void primMST(int graph[V][V]) {
    int parent[V], key[V];
    bool mstSet[V];

    for (int i = 0; i < V; i++)
        key[i] = INT_MAX, mstSet[i] = false;

    key[0] = 0;
    parent[0] = -1;

    for (int count = 0; count < V - 1; count++) {
        int u = minKey(key, mstSet);
        mstSet[u] = true;

        for (int v = 0; v < V; v++)
            if (graph[u][v] && !mstSet[v] && graph[u][v] < key[v]) {
                parent[v] = u;
                key[v] = graph[u][v];
            }
    }

    cout << "Edge   Weight\n";
    for (int i = 1; i < V; i++)
        cout << parent[i] << " - " << i << "    " << graph[i][parent[i]] << endl;
}

int main() {
    int graph[V][V] = {
        {0, 1, 3, 0},
        {1, 0, 5, 2},
        {3, 5, 0, 4},
        {0, 2, 4, 0}
    };

    primMST(graph);
    return 0;
}

Python Implementation (Adjacency Matrix)

import sys

V = 4

def min_key(key, mst_set):
    min_val = sys.maxsize
    min_index = -1
    for v in range(V):
        if not mst_set[v] and key[v] < min_val:
            min_val = key[v]
            min_index = v
    return min_index

def prim_mst(graph):
    key = [sys.maxsize] * V
    parent = [-1] * V
    mst_set = [False] * V

    key[0] = 0

    for _ in range(V - 1):
        u = min_key(key, mst_set)
        mst_set[u] = True

        for v in range(V):
            if graph[u][v] and not mst_set[v] and graph[u][v] < key[v]:
                key[v] = graph[u][v]
                parent[v] = u

    print("Edge   Weight")
    for i in range(1, V):
        print(f"{parent[i]} - {i}    {graph[i][parent[i]]}")

graph = [
    [0, 1, 3, 0],
    [1, 0, 5, 2],
    [3, 5, 0, 4],
    [0, 2, 4, 0]
]

prim_mst(graph)

Java Implementation (Adjacency Matrix)

class PrimAlgorithm {
    static final int V = 4;

    int minKey(int key[], boolean mstSet[]) {
        int min = Integer.MAX_VALUE, minIndex = -1;
        for (int v = 0; v < V; v++)
            if (!mstSet[v] && key[v] < min) {
                min = key[v];
                minIndex = v;
            }
        return minIndex;
    }

    void primMST(int graph[][]) {
        int parent[] = new int[V];
        int key[] = new int[V];
        boolean mstSet[] = new boolean[V];

        for (int i = 0; i < V; i++) {
            key[i] = Integer.MAX_VALUE;
            mstSet[i] = false;
        }

        key[0] = 0;
        parent[0] = -1;

        for (int count = 0; count < V - 1; count++) {
            int u = minKey(key, mstSet);
            mstSet[u] = true;

            for (int v = 0; v < V; v++)
                if (graph[u][v] != 0 && !mstSet[v] && graph[u][v] < key[v]) {
                    parent[v] = u;
                    key[v] = graph[u][v];
                }
        }

        System.out.println("Edge   Weight");
        for (int i = 1; i < V; i++)
            System.out.println(parent[i] + " - " + i + "    " + graph[i][parent[i]]);
    }

    public static void main(String[] args) {
        PrimAlgorithm obj = new PrimAlgorithm();
        int graph[][] = {
            {0, 1, 3, 0},
            {1, 0, 5, 2},
            {3, 5, 0, 4},
            {0, 2, 4, 0}
        };
        obj.primMST(graph);
    }
}

Output

Edge   Weight
0 - 1     1
1 - 3     2
0 - 2    3

Advanced: Parallel and Distributed Implementations

Prim's Algorithm for extremely large graphs may be modified to work in parallel or distributed computing environments. Nevertheless, only a few parts of the algorithm (like updating minimum edge weights) can be parallelized efficiently. These methods are more sophisticated and are generally employed in high-performance computing situations.

Summary:

Prim’s Algorithm can be implemented using different data structures and programming languages. For dense graphs, use an adjacency matrix; for sparse graphs, an adjacency list with a priority queue is more efficient. The pseudocode and code samples above provide a practical starting point for implementing Prim’s Algorithm in real-world scenarios.

Prim’s Algorithm can have different performance depending on how the graph is represented and which data structure is used to select the minimum edge.

Key Note:

• V = number of vertices
• E = number of edges

Bottom Line:

The same algorithm can be slow or fast depending on the data structure that is used; therefore, choose the data structure carefully.

Prim's Algorithm is a fundamental instrument in addressing real-world problems of the nature where one is required to connect multiple points with minimal total cost. Being efficient and greedy in nature, the algorithm is the most suitable choice in various domains to a great extent. These domains represent some of the most significant scenarios where Prim's Algorithm is meaningfully implemented:

1. Network Design

Telecommunications and Internet Cabling:

One of the applications of Prim's Algorithm is in the design of layouts for cable installations (telephone lines, fiber optic cables, and internet backbones) that are cost-effective. The objective is to connect all users or stations with minimum total wiring cost and, at the same time, ensure full connectivity and no redundant loops.

Example:

A telecommunications company wants to connect several cities with fiber optic cables. Each possible connection has an associated cost based on distance and terrain. By modeling this as a weighted graph and applying Prim’s Algorithm, the company can determine the cheapest set of connections that link all cities.

2. Electrical Grid and Circuit Design

Power Distribution Networks:
When planning the layout for electrical grids or circuit wiring, minimizing the amount of wire (and thus the cost and loss) is crucial. Prim’s Algorithm helps design networks that connect all substations or components using the minimum total length of wire.

Example:

An engineer designs the power lines needed to connect a group of substations, ensuring all are linked with the least amount of cable, reducing both installation and transmission losses.

3. Transportation and Road Construction

Road, Railway, and Pipeline Networks:

The planning of the construction of roads, railways, or pipelines that connect several cities, factories, or distribution points is done by the use of Prim's Algorithm by governments and companies. The objective is to reduce the building costs as much as possible while keeping the system accessible.

Example:

A logistics company needs to lay out new roads to connect warehouses in different regions. Using Prim’s Algorithm ensures the network is fully connected with the least total road length.

4. Computer and Data Networks

LAN and WAN Setup:

Prim's​‍​‌‍​‍‌​‍​‌‍​‍‌ Algorithm in computer networking is used to create local area networks (LANs) or wide area networks (WANs) that require the connection of all devices with the least possible cabling costs and without any redundant ​‍​‌‍​‍‌​‍​‌‍​‍‌connections.

5. Cluster Analysis in Data Science

Hierarchical Clustering:

Prim’s Algorithm is used in data science for hierarchical (agglomerative) clustering. By treating data points as nodes and distances as weights, the algorithm helps in grouping similar data points by constructing a minimum spanning tree that reveals natural clusters.

6. Maze and Map Generation

Procedural Content Generation:
Game developers and researchers use Prim’s Algorithm to generate mazes and maps. By applying the algorithm to a grid graph with randomly assigned weights, it produces mazes with a single, unique path between any two points.

Example:

The creation of this maze, which uses Prim's algorithm on a randomly weighted grid graph, is one of the numerous uses for Prim's method.

7. Urban Planning and Utility Layout

Water Supply and Irrigation Systems:
Designing the layout for water pipes or irrigation channels to connect all houses or fields while using the least amount of piping is another classic application.

8. Geographical Mapping and Surveying

Connecting Survey Points:
Surveyors use Prim’s Algorithm to connect multiple geographical points (like mountain peaks or survey markers) with the shortest possible network, reducing costs and effort.

Why Choose Prim’s Algorithm?

• Efficiency on Dense Graphs:

Prim’s Algorithm is especially efficient for dense graphs, where most nodes are interconnected.

• Incremental Solutions:

It’s ideal when connections need to be built incrementally or when real-time updates are required.

• Simplicity and Adaptability:

Its an easy approach that makes it easy to implement and adapt for various practical problems.

Limitations and Considerations

• Requires a Connected Graph:
  Prim’s​‍​‌‍​‍‌​‍​‌‍​‍‌ Algorithm can only produce a minimum spanning tree that shows the connected part of the graph. For a graph that is not connected, you need to separately process each component.
• Scalability:
  In case of very large networks, it is necessary to use optimized data structures (like heaps) if you want the algorithm to run at a practical speed

Summary:

Prim’s Algorithm is essentially a cost-minimization game in the fields of network design, infrastructure planning, data analysis, and pretty much everywhere else. The algorithm’s influence on the world can be seen in the less obvious cases, like the cables that are used to provide you with the internet connection and the roads and pipelines that connect cities and ​‍​‌‍​‍‌​‍​‌‍​‍‌resources.

Minimum Spanning Tree (MST) problems can be solved using multiple algorithms. While Prim’s Algorithm is one of the most popular, it is important to understand how it compares with other well-known approaches, such as Kruskal’s, Borůvka’s, and even why it is often confused with Dijkstra’s Algorithm. Each algorithm follows a greedy algorithm strategy, but their behavior, efficiency, and use cases differ.

Key Takeaway

All​‍​‌‍​‍‌​‍​‌‍​‍‌ MST algorithms are based on greedy principles, however, they vary in the way they choose edges and their size. Prim’s Algorithm is best suited for dense, connected graphs, while Kruskal’s is a good choice for sparse or disconnected graphs. Borůvka’s is perfect for parallel environments, and Dijkstra’s, although similar, is intended for shortest paths, not MST ​‍​‌‍​‍‌​‍​‌‍​‍‌construction.

Prim's Algorithm is a fundamental tool for solving minimum spanning tree problems efficiently. By building the MST one node at a time and always choosing the minimum available edge, Prim’s algorithm ensures optimality using a greedy approach.

With efficient implementations using heaps, the Prims Algorithm can solve massive MST problems in practical time, impacting areas ranging from network design to machine learning.

Mastering​‍​‌‍​‍‌​‍​‌‍​‍‌ Prim's is essential to any one who is serious about data structures, algorithms, and computational problem-solving.

Advice for Learners

1. Prim’s Algorithm builds the MST incrementally, always choosing the minimum-weight edge that connects a visited vertex to an unvisited one.
2. A unconnected graph must be analyzed for each component since the approach only works with connected, weighted, undirected graphs.
3. Performance is largely influenced by the choice of data structures:
   
   • Adjacency Matrix → O(V²) (dense graphs)
   • Adjacency List + Heap → O(E log V) (sparse graphs)
4. Prim's algorithm does not need any extra mechanisms to prevent cycles since it by definition, never connects a pair of vertices that are already in the MST.

1. What is Prim’s Algorithm?

The Minimum Spanning Tree (MST) in a weighted, undirected graph may be found using Prim's Algorithm, a greedy technique. It adds the shortest edge connecting a vertex in the MST to a vertex outside the MST, starting at any random node and continuing until all vertices are included in the MST.

2. How does Prim’s Algorithm work?

Prim’s Algorithm gets its work done by the selection of a start node. Then, by adding the least edge that connects a vertex within the MST to a vertex outside the MST, the process is repeated until the MST contains all the vertices and the total edge weight is minimum.

3. What is the time complexity of Prim’s Algorithm?

The time complexity of the Prim's Algorithm is O(E logV) if a priority queue (min-heap) is used for the implementation. In this expression, E stands for the number of edges, and V is the number of vertices. This method is quite powerful for large graphs and works very well if the graph is dense and the correct data structure is used.

4. Can Prim’s Algorithm handle disconnected graphs?

No, Prim's Algorithm requires the graph to be connected. If the graph is disconnected, it will only find the MST of the connected components. Each disconnected part would need to be processed separately.

5. What is the difference between Prim's and Kruskal's algorithms?

Prim's and Kruskal's algorithms both attain the MST goal, but they think differently. With Prim's algorithm, the MST is constructed by adding edges from one vertex, whereas Kruskal’s algorithm first orders all edges and then adds them one by one. Prim’s is a good choice for dense graphs, while Kruskal’s is better for sparse graphs.

6. What data structures are used in Prim’s Algorithm?

In a typical situation, a priority queue (min-heap) is required in Prim's Algorithm so the smallest edge can be selected efficiently. Also, a set can be used to keep track of visited vertices, and an adjacency list or matrix can be used to represent the graph structure.

7. What are some real-world applications of Prim’s Algorithm?

Prim’s Algorithm is used in network design problems, such as designing the least-cost telecom or computer networks. It is also used in geographical mapping, electrical circuit design, and any application requiring an efficient way to connect all nodes with minimal total edge cost.