Prim's Minimum Spanning Tree Algorithm: Notes, Example, Code & Complexity

Prim's Minimum Spanning Tree Algorithm

Prim's algorithm is a greedy algorithm used to find a Minimum Spanning Tree (MST) of a connected, undirected, weighted graph.

It starts from one vertex and grows the MST one vertex at a time by choosing the cheapest edge that connects the current tree to a new vertex.

A priority queue or min-heap is commonly used to pick the next minimum edge efficiently.

Mental Model

Think of Prim's algorithm as building a network from one starting location. At every step, look at all cables leaving the already connected area and choose the cheapest cable that reaches a new location.

What is Prim's Minimum Spanning Tree Algorithm?

Prim's algorithm finds a minimum spanning tree of a weighted, undirected graph. A minimum spanning tree connects all vertices with the minimum possible total edge weight and contains no cycle.

Unlike Kruskal's algorithm, which sorts all edges globally, Prim's algorithm grows one connected tree. It begins from any vertex, then repeatedly selects the minimum-weight edge that goes from the current MST to a vertex not yet included.

Input: A connected, undirected, weighted graph.
Output: V - 1 edges forming a minimum spanning tree.
Greedy choice: choose the cheapest outgoing edge from the current tree.
Main data structure: priority queue, min-heap, or adjacency matrix depending on implementation.
Goal: minimize total connection cost, not shortest distance from the start vertex.

Important Terms

Term	Meaning
Spanning Tree	A tree that connects all vertices of a connected graph without cycles
Minimum Spanning Tree	A spanning tree with the smallest possible total edge weight
MST Set	The vertices already included in the growing MST
Key Value	The cheapest edge weight currently known for adding a vertex to the MST
Parent Array	Stores which vertex connects each selected vertex to the MST

Where Prim's Algorithm Is Used

Prim is useful when we need to connect many points with minimum total cost and the graph is naturally represented by adjacency lists or adjacency matrices.

Designing low-cost cable, fiber, or electric networks.
Connecting buildings, cities, routers, or stations with minimum total wiring.
Building network backbones when all nodes must remain connected.
Clustering and graph-based data analysis.
DAA exams and interviews where greedy MST algorithms are tested.

Conditions for Prim's Algorithm

The graph should be undirected.
The graph should be connected if we want one MST.
Edge weights can be positive, zero, or negative.
If the graph is disconnected, Prim can be restarted from each component to create a minimum spanning forest.
Prim is not a shortest path algorithm; use Dijkstra for shortest paths with non-negative weights.

Prim Algorithm Steps

The algorithm keeps a growing tree and a record of the cheapest way to add every outside vertex.

Step 1: Choose any start vertex.
Step 2: Mark the start vertex key value as 0 and all other key values as infinity.
Step 3: Pick the vertex outside the MST with the smallest key value.
Step 4: Add that vertex to the MST.
Step 5: For each neighbor not yet in the MST, update its key if the current edge is cheaper.
Step 6: Repeat until all vertices are included.
Step 7: The parent array gives the selected MST edges.

Why Prim's Algorithm Works

Prim's algorithm is justified by the cut property of minimum spanning trees. At any point, the vertices already selected form one side of a cut, and the remaining vertices form the other side.

The lightest edge crossing this cut is safe to add to some MST. Prim repeatedly chooses exactly such an edge, so each greedy choice keeps the result optimal.

The selected vertices form one connected component.
The next chosen edge always crosses from selected vertices to unselected vertices.
Choosing the lightest crossing edge is safe by the cut property.
Because every selected edge is safe, the final tree has minimum total weight.

Step-by-Step Example

Consider a graph with 5 vertices: A, B, C, D, and E.

Edge	Weight
A - B	2
A - D	6
B - C	3
B - D	8
B - E	5
C - E	7
D - E	9

Dry Run Starting from A

At each step, choose the smallest edge that connects the current MST to a new vertex.

Step	MST Vertices Before Choice	Candidate Minimum Edge	Decision	MST Weight
1	{A}	A - B (2)	Add B through A-B	2
2	{A, B}	B - C (3)	Add C through B-C	5
3	{A, B, C}	B - E (5)	Add E through B-E	10
4	{A, B, C, E}	A - D (6)	Add D through A-D	16

Final MST Result

The graph has 5 vertices, so the MST must contain V - 1 = 4 edges.

Selected edges: A-B, B-C, B-E, A-D.
Total MST weight: 2 + 3 + 5 + 6 = 16.
Edges B-D, C-E, and D-E are not selected because cheaper connections already include all vertices.
Starting from another vertex may choose edges in a different order, but the total MST weight remains minimum.

Prim with Priority Queue

A priority queue stores candidate edges or vertices ordered by smallest weight. This avoids scanning all edges manually at every step.

The Java program below stores graph edges in an adjacency list. Each priority queue item contains {weight, vertex, parent}.

inMST[v] tells whether vertex v is already included.
The priority queue always gives the cheapest available edge next.
If a vertex is already in the MST when popped, skip it.
The parent value records the actual MST edge.

Prim's MST Algorithm in Java

import java.util.*;

public class PrimMST {

    static class Edge {
        int to;
        int weight;

        Edge(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }

    static class Node {
        int weight;
        int vertex;
        int parent;

        Node(int weight, int vertex, int parent) {
            this.weight = weight;
            this.vertex = vertex;
            this.parent = parent;
        }
    }

    static int prim(List<Edge>[] graph, int start) {
        int vertices = graph.length;
        boolean[] inMST = new boolean[vertices];
        PriorityQueue<Node> pq =
            new PriorityQueue<>(Comparator.comparingInt(node -> node.weight));

        pq.offer(new Node(0, start, -1));
        int totalWeight = 0;
        int selectedEdges = 0;

        System.out.println("Edges in MST:");

        while (!pq.isEmpty() && selectedEdges < vertices) {
            Node current = pq.poll();
            int u = current.vertex;

            if (inMST[u]) {
                continue;
            }

            inMST[u] = true;
            totalWeight += current.weight;
            selectedEdges++;

            if (current.parent != -1) {
                System.out.println(current.parent + " - " + u + " : " + current.weight);
            }

            for (Edge edge : graph[u]) {
                if (!inMST[edge.to]) {
                    pq.offer(new Node(edge.weight, edge.to, u));
                }
            }
        }

        return totalWeight;
    }

    static void addEdge(List<Edge>[] graph, int u, int v, int weight) {
        graph[u].add(new Edge(v, weight));
        graph[v].add(new Edge(u, weight));
    }

    @SuppressWarnings("unchecked")
    public static void main(String[] args) {
        int vertices = 5;
        List<Edge>[] graph = new ArrayList[vertices];

        for (int i = 0; i < vertices; i++) {
            graph[i] = new ArrayList<>();
        }

        addEdge(graph, 0, 1, 2); // A-B
        addEdge(graph, 0, 3, 6); // A-D
        addEdge(graph, 1, 2, 3); // B-C
        addEdge(graph, 1, 3, 8); // B-D
        addEdge(graph, 1, 4, 5); // B-E
        addEdge(graph, 2, 4, 7); // C-E
        addEdge(graph, 3, 4, 9); // D-E

        int mstWeight = prim(graph, 0);
        System.out.println("Total MST Weight = " + mstWeight);
    }
}

Program Output

Edges in MST:
0 - 1 : 2
1 - 2 : 3
1 - 4 : 5
0 - 3 : 6
Total MST Weight = 16

Prim Using Key and Parent Arrays

Many textbooks explain Prim using three arrays: key, parent, and mstSet. This version is useful for understanding the logic even if the priority queue version is faster for large sparse graphs.

Array	Purpose
key[v]	Smallest known edge weight for connecting v to the MST
parent[v]	Vertex that connects v to the MST
mstSet[v]	Whether v is already included in the MST

Complexity Analysis

Let V be the number of vertices and E be the number of edges.

Implementation	Time Complexity	Space Complexity	Best Use
Adjacency matrix without heap	O(V^2)	O(V^2)	Dense graphs or classroom explanation
Adjacency list with binary heap	O((V + E) log V)	O(V + E)	Sparse graphs and practical code
Adjacency list with Fibonacci heap	O(E + V log V)	O(V + E)	Theoretical optimization

Prim vs Kruskal

Point	Prim	Kruskal
Strategy	Grow one connected tree	Pick globally lightest safe edges
Main input style	Adjacency list or matrix	Edge list
Main data structure	Priority queue or key array	Union-Find
Cycle handling	Avoids cycles by adding only outside vertices	Checks cycles using DSU
Often preferred for	Dense graphs	Sparse graphs

Common Mistakes

Confusing Prim with Dijkstra. Prim minimizes total tree weight; Dijkstra minimizes distance from a source.
Adding an edge to a vertex that is already inside the MST.
Forgetting that classical MST works on undirected graphs.
Stopping after V edges instead of V - 1 selected edges.
Not checking disconnected graphs. A disconnected graph cannot produce one MST.
Assuming the start vertex changes the minimum total cost. It may change order, but not the optimal MST weight.

Key Takeaways

Prim's algorithm is a greedy MST algorithm.
It starts from one vertex and expands the MST using the cheapest outgoing edge.
The priority queue implementation is efficient for adjacency-list graphs.
The final MST contains exactly V - 1 edges.
Prim is not used for shortest path; it is used for minimum total connection cost.

Key Takeaways

Can you explain how Prim grows one connected tree?
Can you dry-run Prim from a chosen start vertex?
Can you identify the selected MST edges and total weight?
Can you explain why priority queue improves the implementation?
Can you distinguish Prim from Dijkstra and Kruskal?

Common Mistakes to Avoid

WRONG Use Prim to find shortest paths from one source.

RIGHT Use Prim to find a minimum spanning tree.

Shortest path minimizes route distance; MST minimizes total network connection cost.

WRONG Choose the smallest edge in the whole graph at every step.

RIGHT Choose the smallest edge that connects the current MST to a new vertex.

Prim's candidate edges must cross from selected vertices to unselected vertices.

WRONG Allow a selected vertex to be added again from the priority queue.

RIGHT Skip vertices that are already marked inMST.

Priority queues may contain old candidate entries, so the visited check is important.

Practice Tasks

Draw a 6-vertex weighted undirected graph and find its MST using Prim starting from vertex A.
Run Prim from a different start vertex and compare the selected edge order.
Modify the Java program to print vertex labels A, B, C instead of numbers.
Write the adjacency matrix version of Prim and compare its complexity with the priority queue version.
Create a disconnected graph and explain why one MST cannot be formed.

Frequently Asked Questions

Is Prim's algorithm greedy?

Yes. At each step, it greedily chooses the cheapest edge that connects the current MST to a new vertex.

Can Prim start from any vertex?

Yes. Prim can start from any vertex in a connected graph. The order of selected edges may differ, but the total MST weight remains minimum.

Does Prim work with negative edge weights?

Yes. MST algorithms can handle negative edge weights because they compare edge weights directly and do not depend on path distance relaxation.

What is the difference between Prim and Dijkstra?

Prim chooses the cheapest edge to expand the MST. Dijkstra chooses the vertex with the smallest total distance from the source. Their priority queues look similar, but their goals are different.

What happens if the graph is disconnected?

A single MST cannot be formed. You can run Prim separately on each component to get a minimum spanning forest.

Previous Next

Prim's Minimum Spanning Tree Algorithm: Notes, Example, Code & Complexity