Prim’s Algorithm

71.6k
0

Given a connected, undirected, weighted graph with V vertices and E edges, find the total weight of a minimum spanning tree using Prim's algorithm.

A minimum spanning tree connects every vertex, contains exactly V - 1 edges, contains no cycle, and has the smallest possible total edge weight. Every edge is represented as [source, destination, weight].

Example 1

Input: V = 5, edges = [[0,1,2],[0,3,6],[1,2,3],[1,3,8],[1,4,5],[2,4,7],[3,4,9]]

Output: 16

Explanation: Edges (0,1), (1,2), (1,4), and (0,3) connect all vertices with total weight 2 + 3 + 5 + 6 = 16.

Example 2

Input: V = 4, edges = [[0,1,1],[0,2,2],[1,2,2],[1,3,3],[2,3,3]]

Output: 6

Explanation: One valid MST uses edges (0,1), (0,2), and (1,3) with total weight 1 + 2 + 3 = 6.

Brute Force Approach

Prim's greedy rule grows one connected tree from an arbitrary starting vertex. A key array stores the cheapest known edge connecting every unselected vertex to the current tree. A linear scan finds the smallest key during each iteration.

An adjacency matrix makes every edge lookup immediate and keeps the implementation direct. The cut property guarantees safety for the minimum crossing edge selected during each iteration. Prerequisite concepts include weighted graphs, spanning trees, greedy selection, and the cut property.

Algorithm

  • Build an undirected adjacency matrix so the weight between any two vertices can be accessed directly.

  • Initialize every vertex key as infinity and mark all vertices as unselected, while the starting vertex gets key 0.

  • Select the unselected vertex with the smallest key because it represents the cheapest edge that can extend the current spanning tree.

  • Add the selected vertex's key to the MST weight and mark it as selected.

  • Check every possible neighbor of the selected vertex to find edges that can connect unselected vertices more cheaply.

  • Update a neighbor's key whenever the selected vertex provides a lighter connecting edge.

  • Repeat the selection and key-update process until every vertex belongs to the spanning tree.

  • Return the accumulated MST weight as the minimum spanning tree cost.

Dry Run

prims

prims

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Function to compute MST weight using linear
// minimum selection.
int spanningTree(int vertices, vector<vector<int>>& edges) {
const int INF = 1e9;
// Build an adjacency matrix and preserve the lightest
// parallel edge.
vector<vector<int>> weight(vertices, vector<int>(vertices, INF));
for (const auto& edge : edges) {
int source = edge[0];
int destination = edge[1];
int edgeWeight = edge[2];
weight[source][destination] = min(weight[source][destination], edgeWeight);
weight[destination][source] = min(weight[destination][source], edgeWeight);
}
// Store the cheapest connection and MST membership
// for every vertex.
vector<int> key(vertices, INF);
vector<bool> inMst(vertices, false);
key[0] = 0;
int totalWeight = 0;
// Add exactly one minimum-key vertex during every iteration.
for (int count = 0; count < vertices; count++) {
int node = -1;
// Find the cheapest vertex outside the growing tree.
for (int candidate = 0; candidate < vertices; candidate++) {
if (!inMst[candidate] &&
(node == -1 || key[candidate] < key[node])) {
node = candidate;
}
}
// Stop when no remaining vertex can be reached.
if (node == -1 || key[node] == INF) break;
// Add the selected connection to the MST weight.
inMst[node] = true;
totalWeight += key[node];
// Relax every edge leaving the selected vertex.
for (int neighbor = 0; neighbor < vertices; neighbor++) {
if (!inMst[neighbor] && weight[node][neighbor] < key[neighbor]) {
key[neighbor] = weight[node][neighbor];
}
}
}
// Return the total MST weight.
return totalWeight;
}
};
// Driver function with a hard-coded graph.
int main() {
int vertices = 5;
vector<vector<int>> edges = {
{0, 1, 2}, {0, 3, 6}, {1, 2, 3}, {1, 3, 8},
{1, 4, 5}, {2, 4, 7}, {3, 4, 9}
};
Solution solution;
cout << solution.spanningTree(vertices, edges) << "\n";
return 0;
}

Note: These implementations assume the graph is connected. For a disconnected graph, they return only the reachable component's spanning-forest weight unless Prim is started from every unvisited vertex.

Complexity Analysis

Time Complexity: Let V be the number of vertices and E be the number of edges. Building the adjacency list takes O(E), and selecting the next vertex by scanning all vertices for up to V selections takes O(V²), so the total time is O(V² + E).

Space Complexity: The adjacency list stores O(V + E) data, and the key and visited arrays store O(V) data, so the total auxiliary space is O(V + E).

Optimal Approach

Prim's greedy rule remains unchanged, but a binary min-heap replaces the repeated linear minimum scan. The heap stores candidate edges crossing from the current tree into unselected vertices, while an adjacency list exposes only real graph edges.

Multiple heap entries can target the same vertex, so an MST marker discards stale entries after the first selection. The first accepted entry for a vertex is the cheapest available crossing edge, as guaranteed by the cut property. Prerequisite concepts include adjacency lists, priority queues, greedy algorithms, and the cut property.

Algorithm

  • Build an undirected adjacency list so each vertex can directly access its connected edges.

  • Initialize a min-heap with the starting vertex and connection weight 0 because the MST can begin from any vertex.

  • Remove the minimum-weight entry from the heap because Prim's algorithm always chooses the cheapest available edge.

  • Skip the entry if the destination vertex is already included in the MST, since a second heap entry for the same vertex is no longer needed.

  • Mark the selected vertex as included, add its connection weight to the MST weight, and increase the included-vertex count.

  • Push every edge from the selected vertex to an unselected neighbor into the heap because these edges are now candidates for extending the MST.

  • Continue until all V vertices are included in the MST.

  • Return the accumulated MST weight.

Dry Run

prims-minheap-inmst-complete-dry-run

prims-minheap-inmst-complete-dry-run

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Function to compute MST weight using a binary min-heap.
int spanningTree(int vertices, vector<vector<int>>& edges) {
// Build an undirected adjacency list.
vector<vector<pair<int, int>>> adjacency(vertices);
for (const auto& edge : edges) {
adjacency[edge[0]].push_back({edge[1], edge[2]});
adjacency[edge[1]].push_back({edge[0], edge[2]});
}
// Store pairs as {connection weight, destination vertex}.
priority_queue<pair<int, int>,
vector<pair<int, int>>,
greater<pair<int, int>>> minHeap;
vector<bool> inMst(vertices, false);
minHeap.push({0, 0});
int totalWeight = 0;
int includedVertices = 0;
// Grow one tree until every vertex becomes part of the MST.
while (!minHeap.empty() && includedVertices < vertices) {
auto [weight, node] = minHeap.top();
minHeap.pop();
// Ignore stale entries for vertices already selected.
if (inMst[node]) continue;
// Accept the cheapest edge crossing the current cut.
inMst[node] = true;
totalWeight += weight;
includedVertices++;
// Add candidate edges leading outside the growing tree.
for (const auto& [neighbor, edgeWeight] : adjacency[node]) {
if (!inMst[neighbor]) {
minHeap.push({edgeWeight, neighbor});
}
}
}
// Return the total MST weight.
return totalWeight;
}
};
// Driver function with a hard-coded graph.
int main() {
int vertices = 5;
vector<vector<int>> edges = {
{0, 1, 2}, {0, 3, 6}, {1, 2, 3}, {1, 3, 8},
{1, 4, 5}, {2, 4, 7}, {3, 4, 9}
};
Solution solution;
cout << solution.spanningTree(vertices, edges) << "\n";
return 0;
}

Note: These implementations assume the graph is connected. For a disconnected graph, they return only the reachable component's spanning-forest weight unless Prim is started from every unvisited vertex.

Complexity Analysis

Time Complexity: Let V be the number of vertices and E be the number of edges. Building the adjacency list takes O(E), and the lazy heap can receive O(E) entries with heap operations costing O(log E), so the precise time complexity is O(E log E); for a simple graph, this is commonly simplified to O(E log V).

Space Complexity: The adjacency list uses O(V + E) space, the visited array uses O(V) space, and the lazy heap can hold O(E) entries, so the total auxiliary space is O(V + E).

Interview follow-up Questions

Yes. Greedy selection depends on relative edge order, so negative, zero, and positive weights remain valid.

Graph

Read Similar Blogs

Graph

Find the City with the Smallest Number of Neighbors at a Threshold Distance

Given N cities numbered from 0 to N-1 , an array of bidirectional weighted roads [first, second, weight] , and a positive distanceThreshold , count the other cities reachable from every city with s...

105.7k
Graph

Dijkstra’s Algorithm

Given an undirected weighted graph with V vertices numbered from 0 to V - 1 , an edge list, and a source vertex, find the shortest distance from source to every vertex. Every edge appears as [u, v,...

93k
Graph

Print Shortest Path

Given a weighted undirected graph with n vertices numbered from 1 to n and m edges, find a shortest path from vertex 1 to vertex n . Each edge appears as [u, v, weight] and every weight is positive...

96.1k
Comments0