Log inSign up
mediumLeetCodeNot Started

Prim's Algorithm

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Graph
Solve on LeetCode
Lesson

Problem Statement

Given a weighted, undirected, and connected graph of V vertices and E edges. Calculate the sum of weights of the edges of the Minimum Spanning Tree (MST) using Prim's Algorithm.

Additionally, return or output the sequence of edges that form the MST.

Constraints:

  • 2 <= V <= 105
  • V - 1 <= E <= min(105, V*(V-1)/2)
  • 0 <= u, v < V
  • 1 <= weight <= 104
  • Graph is guaranteed to be connected and undirected.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand the Cut Property in network design and spanning tree theory.
  • Implement Prim's Algorithm with a priority queue storing (weight, vertex, parent).
  • Trace and reconstruct the actual edges of the Minimum Spanning Tree.
  • Analyze time complexity trade-offs between binary heaps (O(E log V)) and dense flat arrays (O(V2)).

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Whenever an MST problem is given with an adjacency list, or the graph is dense (E ≈ V2), Prim's Algorithm is the ideal choice. It naturally expands outward from a source vertex without sorting all edges upfront.

1. Linear Cut Scan (Without Priority Queue)

Intuition

Maintain a set inMST of vertices already included in the tree, starting with inMST = {0}. In each of the V - 1 steps, iterate through every edge (u, v, w) in the graph. Find the edge with minimal weight such that exactly one endpoint is in inMST and the other is outside inMST. Add that edge and vertex to inMST.

Algorithm

  1. Initialize inMST boolean array of size V with false, set inMST[0] = true.
  2. Initialize mstWeight = 0 and mstEdges = [].
  3. Repeat V - 1 times:
  4. Set minW = infinity, bestU = -1, bestV = -1.
  5. Iterate through all edges (u, v, w) in the graph:
  6. If (inMST[u] && !inMST[v]) or (!inMST[u] && inMST[v]):
  7. If w < minW:
  8. minW = w, bestU = u, bestV = v.
  9. Add bestV (the outside node) to inMST, mstWeight += minW, record edge.
  10. Return mstWeight and mstEdges.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <climits>
4
5struct Edge {
6 int u, v, w;
7};
8
9int primsBrute(int V, const std::vector<Edge>& edges) {
10 std::vector<bool> inMST(V, false);
11 inMST[0] = true;
12 int totalWeight = 0;
13
14 for (int step = 0; step < V - 1; ++step) {
15 int minW = INT_MAX, bestU = -1, bestV = -1;
16 for (const auto& e : edges) {
17 if ((inMST[e.u] && !inMST[e.v]) || (!inMST[e.u] && inMST[e.v])) {
18 if (e.w < minW) {
19 minW = e.w;
20 bestU = inMST[e.u] ? e.u : e.v;
21 bestV = inMST[e.u] ? e.v : e.u;
22 }
23 }
24 }
25 inMST[bestV] = true;
26 totalWeight += minW;
27 }
28 return totalWeight;
29}
30
31int main() {
32 int V = 4;
33 std::vector<Edge> edges = {{0,1,1},{1,2,2},{2,3,3},{0,3,4},{0,2,5}};
34 std::cout << "Brute Force Prim's: " << primsBrute(V, edges) << std::endl;
35 return 0;
36}

Time & Space Complexity

  • Time complexity: O(V * E) because in each of the V - 1 iterations we scan all E edges.
  • Space complexity: O(V) for the inMST array and edge storage.

2. Dense Array-Based Prim's Algorithm

Intuition

Instead of scanning all E edges repeatedly, maintain an array minWeight[i] of the shortest edge from any node in the tree to unvisited node i. In each step, scan the V nodes to find the minimum minWeight, add it to the tree, and update the neighbors in O(V) time. This requires no heap and takes O(V2) time.

Algorithm

  1. Initialize minWeight array of size V with infinity, set minWeight[0] = 0.
  2. Initialize parent array of size V with -1.
  3. Initialize visited array of size V with false.
  4. Initialize totalWeight = 0.
  5. Loop V times:
  6. Find unvisited vertex u with minimum minWeight[u].
  7. Mark visited[u] = true, totalWeight += minWeight[u].
  8. For each neighbor v of u with weight w:
  9. If !visited[v] && w < minWeight[v]:
  10. minWeight[v] = w, parent[v] = u.
  11. Return totalWeight.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <climits>
4#include <algorithm>
5
6int primsDense(int V, const std::vector<std::vector<int>>& edges) {
7 std::vector<std::vector<int>> adj(V, std::vector<int>(V, INT_MAX));
8 for (const auto& e : edges) {
9 adj[e[0]][e[1]] = std::min(adj[e[0]][e[1]], e[2]);
10 adj[e[1]][e[0]] = std::min(adj[e[1]][e[0]], e[2]);
11 }
12
13 std::vector<int> minWeight(V, INT_MAX);
14 std::vector<bool> visited(V, false);
15 minWeight[0] = 0;
16 int totalWeight = 0;
17
18 for (int step = 0; step < V; ++step) {
19 int u = -1;
20 for (int i = 0; i < V; ++i) {
21 if (!visited[i] && (u == -1 || minWeight[i] < minWeight[u])) {
22 u = i;
23 }
24 }
25
26 visited[u] = true;
27 totalWeight += minWeight[u];
28
29 for (int v = 0; v < V; ++v) {
30 if (!visited[v] && adj[u][v] != INT_MAX) {
31 if (adj[u][v] < minWeight[v]) {
32 minWeight[v] = adj[u][v];
33 }
34 }
35 }
36 }
37 return totalWeight;
38}
39
40int main() {
41 int V = 4;
42 std::vector<std::vector<int>> edges = {{0,1,1},{1,2,2},{2,3,3},{0,3,4},{0,2,5}};
43 std::cout << "Dense Prim's: " << primsDense(V, edges) << std::endl;
44 return 0;
45}

Time & Space Complexity

  • Time complexity: O(V^2) where V is the number of vertices. Independent of edge count E.
  • Space complexity: O(V) for minWeight, parent, and visited arrays.

3. Prim's with Min-Heap (Sparse Optimal)

Intuition

Store elements as (weight, u, parent) in a min-heap. Pop the lowest-cost edge crossing into an unvisited vertex. If the vertex is already in the tree, discard it. Otherwise, mark it visited, accumulate the edge weight, record the edge (parent, u) in the MST edge list, and push all edges to unvisited neighbors into the min-heap.

Algorithm

  1. Construct adjacency list adj where adj[u] contains (v, weight).
  2. Initialize visited array of size V with false.
  3. Initialize pq (min-heap), push (weight = 0, node = 0, parent = -1).
  4. Initialize mstSum = 0 and mstEdges = [].
  5. While pq is not empty:
  6. Pop (w, u, parent).
  7. If visited[u] is true, continue.
  8. Mark visited[u] = true, mstSum += w.
  9. If parent != -1, append (parent, u) to mstEdges.
  10. For each neighbor (v, weight) in adj[u]:
  11. If !visited[v], push (weight, v, u) to pq.
  12. Return mstSum and mstEdges.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4#include <tuple>
5
6int primsMST(int V, const std::vector<std::vector<int>>& edges, std::vector<std::pair<int, int>>& mstEdges) {
7 std::vector<std::vector<std::pair<int, int>>> adj(V);
8 for (const auto& e : edges) {
9 adj[e[0]].push_back({e[1], e[2]});
10 adj[e[1]].push_back({e[0], e[2]});
11 }
12
13 std::vector<bool> visited(V, false);
14 // tuple: (weight, node, parent)
15 std::priority_queue<std::tuple<int, int, int>, std::vector<std::tuple<int, int, int>>, std::greater<>> pq;
16 pq.push({0, 0, -1});
17
18 int totalWeight = 0;
19
20 while (!pq.empty()) {
21 auto [w, u, parent] = pq.top();
22 pq.pop();
23
24 if (visited[u]) continue;
25 visited[u] = true;
26 totalWeight += w;
27
28 if (parent != -1) {
29 mstEdges.push_back({parent, u});
30 }
31
32 for (const auto& [v, weight] : adj[u]) {
33 if (!visited[v]) {
34 pq.push({weight, v, u});
35 }
36 }
37 }
38
39 return totalWeight;
40}
41
42int main() {
43 int V = 4;
44 std::vector<std::vector<int>> edges = {{0,1,1},{1,2,2},{2,3,3},{0,3,4},{0,2,5}};
45 std::vector<std::pair<int, int>> mstEdges;
46 int total = primsMST(V, edges, mstEdges);
47 std::cout << "Prim's Total Weight: " << total << std::endl;
48 std::cout << "MST Edges: ";
49 for (auto& p : mstEdges) std::cout << "(" << p.first << "-" << p.second << ") ";
50 std::cout << std::endl;
51 return 0;
52}

Time & Space Complexity

  • Time complexity: O(E log V) because each edge is pushed into the priority queue at most once.
  • Space complexity: O(V + E) for the adjacency list and priority queue storage.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Linear Cut ScanO(V * E)O(V)Simple conceptual proof of the Cut Property.Scans all edges every round; extremely slow for large graphs.
2.Dense Prim's (Flat Array)O(V^2)O(V)Optimal for dense graphs (E ~ V2); zero priority queue overhead.Suboptimal for sparse graphs where E << V2.
3.Min-Heap Prim'sOptimalO(E log V)O(V + E)Asymptotically optimal for sparse graphs; standard industry implementation.Min-heap incurs logarithmic push/pop overhead.

Common Pitfalls & Crucial Edge Cases

Adding the edge weight to total sum when pushing to the priority queue instead of when popping.

Multiple edges can reach the same vertex; an edge is only officially accepted into the MST when popped from the min-heap.

Not skipping already visited nodes upon heap extraction.

A vertex may have multiple redundant heap entries; if visited[u] is true, continue immediately.

Crucial Edge Cases to Validate:

  • V = 1 — MST requires 0 edges; loop terminates immediately with cost 0.
  • Multiple edges with identical weights — Prim's arbitrarily picks any of the valid minimum edges; total MST weight remains identical.
  • Disconnected graph — Not all vertices will be visited; mstEdges count will be < V - 1.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Clearly explain the difference between Kruskal's (edge-centric, DSU) and Prim's (vertex-centric, cut property).
  2. Show how easy it is to reconstruct the actual edges by storing the parent pointer in the min-heap tuple.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the Cut Property in Minimum Spanning Tree theory?

2.When should you prefer array-based Prim's O(V2) over min-heap Prim's O(E log V)?

3.Can Prim's algorithm handle graphs with negative edge weights?

Back to DSA Sheet