Log inSign up
mediumLeetCodeNot Started

Minimum Spanning Tree

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 with V vertices and E edges represented as an adjacency list or edge list where each edge has a source, destination, and weight.

Find the sum of weights of the edges of the Minimum Spanning Tree (MST). A spanning tree is a subset of the edges that connects all vertices together without any cycles, and the minimum spanning tree minimizes the total edge weight.

Constraints:

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

What You'll Learn

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

  • Master both Kruskal's and Prim's algorithms for finding the Minimum Spanning Tree.
  • Understand the Cut Property and Cycle Property underlying MST greediness.
  • Implement Disjoint Set Union (DSU) with Path Compression and Union by Rank.
  • Compare performance trade-offs between Kruskal's (O(E log E)) and Prim's (O(E log V)).

Pattern Recognition Trigger

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

Signals to Look For:

  • Whenever a problem asks for connecting all nodes in an undirected graph with minimum total edge cost and no cycles, apply MST algorithms. If given an edge list, Kruskal's with DSU is the cleanest. If given an adjacency list, Prim's with a Priority Queue is very natural and avoids separate edge struct allocations.

1. Generate All Spanning Trees (Combinatorial / DFS Cycle Check)

Intuition

A spanning tree is any subset of V - 1 edges from the E available edges that forms a connected tree without cycles. We could generate all \binom{E}{V-1} subsets of edges, test each subset for connectivity and acyclicity using DFS, and find the subset with minimum total weight. This demonstrates the combinatorial explosion that greedy algorithms avoid.

Algorithm

  1. Generate all combinations of V - 1 edges from the total E edges.
  2. For each combination of V - 1 edges:
  3. Construct an adjacency graph using only those edges.
  4. Run DFS/BFS from node 0 to verify all V vertices are reachable (connected and therefore acyclic since edge count is V - 1).
  5. If valid, calculate sum of edge weights and update global minimum MST weight.
  6. Return the minimum sum found.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <numeric>
4#include <climits>
5
6struct Edge {
7 int u, v, w;
8};
9
10void checkSubsets(int idx, int picked, int V, const std::vector<Edge>& edges,
11 std::vector<Edge>& current, int& minSum) {
12 if (picked == V - 1) {
13 // Check connectivity
14 std::vector<std::vector<int>> adj(V);
15 int sum = 0;
16 for (const auto& e : current) {
17 adj[e.u].push_back(e.v);
18 adj[e.v].push_back(e.u);
19 sum += e.w;
20 }
21 std::vector<bool> visited(V, false);
22 auto dfs = [&](auto& self, int u) -> void {
23 visited[u] = true;
24 for (int v : adj[u]) {
25 if (!visited[v]) self(self, v);
26 }
27 };
28 dfs(dfs, 0);
29 bool connected = true;
30 for (int i = 0; i < V; ++i) if (!visited[i]) connected = false;
31 if (connected) minSum = std::min(minSum, sum);
32 return;
33 }
34 if (idx >= edges.size()) return;
35
36 // Pick edge
37 current.push_back(edges[idx]);
38 checkSubsets(idx + 1, picked + 1, V, edges, current, minSum);
39 current.pop_back();
40
41 // Skip edge
42 checkSubsets(idx + 1, picked, V, edges, current, minSum);
43}
44
45int spanningTreeBrute(int V, const std::vector<Edge>& edges) {
46 int minSum = INT_MAX;
47 std::vector<Edge> current;
48 checkSubsets(0, 0, V, edges, current, minSum);
49 return minSum;
50}
51
52int main() {
53 int V = 3;
54 std::vector<Edge> edges = {{0, 1, 5}, {1, 2, 3}, {0, 2, 1}};
55 std::cout << "Brute Force MST: " << spanningTreeBrute(V, edges) << std::endl;
56 return 0;
57}

Time & Space Complexity

  • Time complexity: O(C(E, V-1) * (V + E)) which is exponential and completely impractical for E, V > 20.
  • Space complexity: O(V + E) to store edge subsets and adjacency representation for validation.

2. Prim's Algorithm (Priority Queue Cut Property)

Intuition

Start at vertex 0 and grow a single tree component. Maintain a min-heap containing pairs (weight, node). At each step, pop the lowest-weight edge that connects an unvisited node to the tree. Mark the node as visited, add the edge weight to total sum, and push all edges connecting to unvisited neighbors into the min-heap.

Algorithm

  1. Create an adjacency list where each vertex stores pairs (neighbor, weight).
  2. Initialize visited array of size V with false.
  3. Push (0, 0) (weight 0, vertex 0) into min-heap.
  4. Initialize mstSum = 0 and edgesCount = 0.
  5. While min-heap is not empty:
  6. Pop (weight, u).
  7. If visited[u] is true, continue.
  8. Mark visited[u] = true, mstSum += weight.
  9. For each neighbor (v, w) in adj[u]:
  10. If !visited[v], push (w, v) into min-heap.
  11. Return mstSum.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4
5int spanningTreePrims(int V, std::vector<std::vector<int>>& edges) {
6 std::vector<std::vector<std::pair<int, int>>> adj(V);
7 for (const auto& e : edges) {
8 adj[e[0]].push_back({e[1], e[2]});
9 adj[e[1]].push_back({e[0], e[2]});
10 }
11
12 std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> pq;
13 std::vector<bool> visited(V, false);
14 pq.push({0, 0}); // {weight, node}
15 int totalWeight = 0;
16
17 while (!pq.empty()) {
18 auto [wt, u] = pq.top();
19 pq.pop();
20
21 if (visited[u]) continue;
22 visited[u] = true;
23 totalWeight += wt;
24
25 for (const auto& [v, w] : adj[u]) {
26 if (!visited[v]) {
27 pq.push({w, v});
28 }
29 }
30 }
31 return totalWeight;
32}
33
34int main() {
35 int V = 3;
36 std::vector<std::vector<int>> edges = {{0, 1, 5}, {1, 2, 3}, {0, 2, 1}};
37 std::cout << "Prim's MST: " << spanningTreePrims(V, edges) << std::endl;
38 return 0;
39}

Time & Space Complexity

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

3. Kruskal's Algorithm with Disjoint Set Union (DSU)

Intuition

Sort all edges by weight in ascending order. Iterate through the sorted edges and connect edge endpoints (u, v) if and only if they belong to different connected components (checked via find(u) != find(v)). Once unioned, add edge weight to total and stop when V - 1 edges have been added. Path compression and rank heuristic keep DSU operations near O(1) amortized time.

Algorithm

  1. Sort all edges in ascending order of their weights: edges.sort(by weight).
  2. Initialize DSU with parent array parent[i] = i and rank array rank[i] = 0 for all 0 <= i < V.
  3. Initialize mstWeight = 0 and edgesSelected = 0.
  4. For each edge (u, v, w) in sorted list:
  5. rootU = find(u), rootV = find(v)
  6. If rootU != rootV:
  7. union(rootU, rootV)
  8. mstWeight += w
  9. edgesSelected++
  10. If edgesSelected == V - 1, break.
  11. Return mstWeight.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4#include <numeric>
5
6class DSU {
7 std::vector<int> parent, rank;
8public:
9 DSU(int n) : parent(n), rank(n, 0) {
10 std::iota(parent.begin(), parent.end(), 0);
11 }
12 int find(int i) {
13 if (parent[i] == i) return i;
14 return parent[i] = find(parent[i]);
15 }
16 bool unite(int i, int j) {
17 int rootI = find(i);
18 int rootJ = find(j);
19 if (rootI != rootJ) {
20 if (rank[rootI] < rank[rootJ]) {
21 parent[rootI] = rootJ;
22 } else if (rank[rootI] > rank[rootJ]) {
23 parent[rootJ] = rootI;
24 } else {
25 parent[rootJ] = rootI;
26 rank[rootI]++;
27 }
28 return true;
29 }
30 return false;
31 }
32};
33
34int spanningTreeKruskal(int V, std::vector<std::vector<int>>& edges) {
35 // edges: {u, v, weight}
36 std::sort(edges.begin(), edges.end(), [](const auto& a, const auto& b) {
37 return a[2] < b[2];
38 });
39
40 DSU dsu(V);
41 int mstWeight = 0;
42 int edgesCount = 0;
43
44 for (const auto& e : edges) {
45 if (dsu.unite(e[0], e[1])) {
46 mstWeight += e[2];
47 if (++edgesCount == V - 1) break;
48 }
49 }
50 return mstWeight;
51}
52
53int main() {
54 int V = 3;
55 std::vector<std::vector<int>> edges = {{0, 1, 5}, {1, 2, 3}, {0, 2, 1}};
56 std::cout << "Kruskal's MST: " << spanningTreeKruskal(V, edges) << std::endl;
57 return 0;
58}

Time & Space Complexity

  • Time complexity: O(E log E) to sort the edges. DSU find and union operations take O(E * alpha(V)) which is practically linear.
  • Space complexity: O(V) auxiliary memory for DSU parent and rank arrays.

Approach Comparison Matrix

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

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Combinatorial Subset SearchO(C(E, V-1) * (V+E))O(V + E)Pure theoretical brute-force enumeration.Exponential time; fails for graphs with more than a few edges.
2.Prim's with Min-HeapO(E log V)O(V + E)Ideal when the graph is already stored as an adjacency list; vertex-centric tree expansion.Requires priority queue overhead and visited set bookkeeping.
3.Kruskal's with DSUOptimalO(E log E)O(V)Ideal for edge lists; very simple DSU data structure with near O(1) union-find.Requires sorting all edges upfront.

Common Pitfalls & Crucial Edge Cases

Using standard 0-indexed DSU when vertices are 1-indexed in problem descriptions.

Initialize DSU size as V + 1 to safely accommodate both 0-indexed and 1-indexed vertices.

Forgetting to break early after selecting V - 1 edges in Kruskal's.

Once edgesCount reaches V - 1, all nodes are connected; stopping immediately saves unnecessary DSU lookups.

Re-inserting edges into DSU without checking find(u) != find(v).

Connecting two nodes already in the same component forms a cycle, invalidating the spanning tree property.

Crucial Edge Cases to Validate:

  • Graph is already a tree (E = V - 1) — Kruskal's will select all edges without discarding any; total weight is simply the sum of all edge weights.
  • All edges have identical weights — Any valid spanning tree of V - 1 edges has the same minimum weight (V - 1) * w.
  • Dense complete graph (E = V(V-1)/2) — Sorting takes O(V2 log V). Prim's with adjacency matrix can execute in O(V2) without a heap.

Interview Tips & Best Practices

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

  1. State the Cut Property: for any cut in the graph, the minimum weight edge crossing the cut belongs to at least one MST. Prim's repeatedly exploits this.
  2. State the Cycle Property: for any cycle in the graph, the heaviest edge in the cycle cannot be part of any unique MST. Kruskal's implicitly rejects such edges.
  3. If asked: 'What if edge weights are all distinct?' -> The MST is guaranteed to be unique!

Quick Comprehension Check

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

1.How many edges are present in any valid Minimum Spanning Tree of a connected graph with V vertices?

2.Can an undirected graph have multiple distinct Minimum Spanning Trees?

3.What is the time complexity of the Union-Find operations with path compression and rank?

Back to DSA Sheet