Minimum Spanning Tree Concepts
Description
Given a weighted, undirected, and connected graph with V vertices (numbered 0 to V-1) and E edges, find the sum of the weights of the edges in the Minimum Spanning Tree (MST) of the graph.
A spanning tree of a connected graph is a subgraph that includes every vertex, forms a tree (contains no cycles), and uses exactly V-1 edges. Among all possible spanning trees, the one with the smallest total edge weight is called the Minimum Spanning Tree.
The graph is provided as a list of edges, where each edge is represented as [u, v, w], indicating an undirected edge between vertex u and vertex v with weight w.
Examples
Example 1
Input: V = 3, E = 3, edges = [[0, 1, 5], [1, 2, 3], [0, 2, 1]]
Output: 4
Explanation: The graph has 3 vertices and 3 edges. A spanning tree needs exactly V-1 = 2 edges. The possible spanning trees are:
- Edges {0-1 (w=5), 1-2 (w=3)} → total weight = 8
- Edges {0-1 (w=5), 0-2 (w=1)} → total weight = 6
- Edges {1-2 (w=3), 0-2 (w=1)} → total weight = 4
The minimum weight spanning tree uses edges 1-2 (weight 3) and 0-2 (weight 1), giving a total weight of 4.
Example 2
Input: V = 2, E = 1, edges = [[0, 1, 5]]
Output: 5
Explanation: With only 2 vertices and 1 edge, the only possible spanning tree is the single edge 0-1 with weight 5. This is also the minimum spanning tree.
Example 3
Input: V = 5, E = 7, edges = [[0,1,2], [1,2,3], [0,2,4], [1,4,5], [0,3,6], [2,4,7], [1,3,8]]
Output: 16
Explanation: The MST connects all 5 vertices using 4 edges: 0-1 (weight 2), 1-2 (weight 3), 1-4 (weight 5), and 0-3 (weight 6). The total weight is 2 + 3 + 5 + 6 = 16. Note that edge 0-2 (weight 4) is not included because it would create a cycle with the already-connected path 0→1→2.
Constraints
- 2 ≤ V ≤ 1000
- V-1 ≤ E ≤ V × (V-1) / 2
- 1 ≤ w ≤ 1000
- The graph is connected
- No self-loops or multiple edges between the same pair of vertices
Editorial
Brute Force
Intuition
The most straightforward way to find the minimum spanning tree is to consider every possible spanning tree of the graph and pick the one with the smallest total weight.
A spanning tree of a graph with V vertices always has exactly V-1 edges. So we can look at all possible ways to choose V-1 edges from the E available edges. For each selection, we check two things: does this set of edges connect all vertices (forming a spanning tree), and if so, what is its total weight? After examining every valid spanning tree, we return the one with the minimum weight.
Think of it like choosing a road network to connect several cities. You have a map with many roads (edges) of different lengths (weights). You want to pick the fewest roads that still let you travel between any two cities, and you want the total road length to be as small as possible. The brute force approach would be to write down every possible selection of roads, cross out the ones that leave a city disconnected or create a loop, and then compare the total lengths of what remains.
Step-by-Step Explanation
Let's trace through with V = 3, E = 3, edges = [[0,1,5], [1,2,3], [0,2,1]]:
We need V-1 = 2 edges for a spanning tree. We must examine all C(3,2) = 3 combinations of 2 edges from the 3 available.
Step 1: Generate Combination 1 — edges {(0,1,5), (1,2,3)}
- Selected edges: 0—1 and 1—2
- Build adjacency list: 0→[1], 1→[0,2], 2→[1]
- Run BFS from vertex 0: visit 0 → visit 1 → visit 2
- Vertices reached: 3 out of 3 → connected ✓
- Total weight = 5 + 3 = 8
- current_minimum = 8
Step 2: Generate Combination 2 — edges {(0,1,5), (0,2,1)}
- Selected edges: 0—1 and 0—2
- Build adjacency list: 0→[1,2], 1→[0], 2→[0]
- Run BFS from vertex 0: visit 0 → visit 1, 2
- Vertices reached: 3 out of 3 → connected ✓
- Total weight = 5 + 1 = 6
- current_minimum = min(8, 6) = 6
Step 3: Generate Combination 3 — edges {(1,2,3), (0,2,1)}
- Selected edges: 1—2 and 0—2
- Build adjacency list: 0→[2], 1→[2], 2→[1,0]
- Run BFS from vertex 0: visit 0 → visit 2 → visit 1
- Vertices reached: 3 out of 3 → connected ✓
- Total weight = 3 + 1 = 4
- current_minimum = min(6, 4) = 4
Step 4: All combinations exhausted
- We checked all 3 possible subsets of 2 edges
- The minimum weight spanning tree has weight 4
- It uses edges 1-2 (weight 3) and 0-2 (weight 1)
Result: Return 4.
Algorithm
- Generate all combinations of V-1 edges from the E available edges
- For each combination:
a. Build an adjacency list using only the selected edges
b. Run BFS or DFS from vertex 0 to check if all V vertices are reachable
c. If all vertices are reachable (the edges form a spanning tree), compute the total weight
d. Track the minimum weight found so far - Return the minimum weight
Code
#include <vector>
#include <climits>
#include <queue>
using namespace std;
class Solution {
public:
bool isConnected(int V, vector<vector<int>>& edges,
vector<int>& selected) {
vector<vector<int>> adj(V);
for (int idx : selected) {
int u = edges[idx][0], v = edges[idx][1];
adj[u].push_back(v);
adj[v].push_back(u);
}
vector<bool> visited(V, false);
queue<int> q;
q.push(0);
visited[0] = true;
int count = 1;
while (!q.empty()) {
int node = q.front();
q.pop();
for (int nb : adj[node]) {
if (!visited[nb]) {
visited[nb] = true;
count++;
q.push(nb);
}
}
}
return count == V;
}
void generate(int V, vector<vector<int>>& edges,
vector<int>& sel, int start, int& minW) {
if ((int)sel.size() == V - 1) {
if (isConnected(V, edges, sel)) {
int w = 0;
for (int idx : sel) w += edges[idx][2];
minW = min(minW, w);
}
return;
}
for (int i = start; i < (int)edges.size(); i++) {
sel.push_back(i);
generate(V, edges, sel, i + 1, minW);
sel.pop_back();
}
}
int spanningTree(int V, int E,
vector<vector<int>>& edges) {
int minW = INT_MAX;
vector<int> sel;
generate(V, edges, sel, 0, minW);
return minW;
}
};from itertools import combinations
from collections import deque
class Solution:
def spanningTree(self, V, E, edges):
min_weight = float('inf')
for combo in combinations(range(E), V - 1):
# Build adjacency list for selected edges
adj = [[] for _ in range(V)]
weight = 0
for idx in combo:
u, v, w = edges[idx]
adj[u].append(v)
adj[v].append(u)
weight += w
# BFS to check if all vertices are connected
visited = [False] * V
visited[0] = True
queue = deque([0])
count = 1
while queue:
node = queue.popleft()
for neighbor in adj[node]:
if not visited[neighbor]:
visited[neighbor] = True
count += 1
queue.append(neighbor)
if count == V:
min_weight = min(min_weight, weight)
return min_weightimport java.util.*;
class Solution {
int minWeight = Integer.MAX_VALUE;
boolean isConnected(int V, int[][] edges,
List<Integer> sel) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < V; i++)
adj.add(new ArrayList<>());
for (int idx : sel) {
adj.get(edges[idx][0]).add(edges[idx][1]);
adj.get(edges[idx][1]).add(edges[idx][0]);
}
boolean[] visited = new boolean[V];
Queue<Integer> queue = new LinkedList<>();
queue.add(0);
visited[0] = true;
int count = 1;
while (!queue.isEmpty()) {
int node = queue.poll();
for (int nb : adj.get(node)) {
if (!visited[nb]) {
visited[nb] = true;
count++;
queue.add(nb);
}
}
}
return count == V;
}
void generate(int V, int[][] edges,
List<Integer> sel, int start) {
if (sel.size() == V - 1) {
if (isConnected(V, edges, sel)) {
int w = 0;
for (int idx : sel) w += edges[idx][2];
minWeight = Math.min(minWeight, w);
}
return;
}
for (int i = start; i < edges.length; i++) {
sel.add(i);
generate(V, edges, sel, i + 1);
sel.remove(sel.size() - 1);
}
}
int spanningTree(int V, int E,
int[][] edges) {
minWeight = Integer.MAX_VALUE;
generate(V, edges, new ArrayList<>(), 0);
return minWeight;
}
}Complexity Analysis
Time Complexity: O(C(E, V-1) × (V + E))
We generate all combinations of V-1 edges from E edges. The number of such combinations is C(E, V-1), which is the binomial coefficient "E choose V-1". For each combination, we run BFS/DFS taking O(V + E) time to check connectivity and compute the weight. This is exponential in the worst case — for instance, with V = 20 and E = 50, we'd check C(50, 19) ≈ 1.2 × 10^14 combinations.
Space Complexity: O(V + E)
We need O(V) for the BFS visited array and queue, O(V) for the adjacency list per combination check, and O(V) for the recursion stack to generate combinations. The total is O(V + E) additional space.
Why This Approach Is Not Efficient
The brute force checks every possible subset of V-1 edges, and the number of such subsets grows combinatorially. With the constraint V ≤ 1000 and E up to V×(V-1)/2 ≈ 500,000, we would need to check C(500000, 999) subsets — a number so large it dwarfs the number of atoms in the observable universe.
Even for a tiny graph with V = 20 and E = 50, the count C(50, 19) ≈ 1.2 × 10^14 is far beyond the roughly 10^8 operations a computer can handle in one second.
The core problem is that we are blindly generating candidates and then validating them. We have no strategy for which edges to pick — we just try everything.
The key insight that unlocks a far better approach is the cut property of minimum spanning trees: if you split the vertices into two groups, the cheapest edge crossing that split must be part of some MST. This means we can build the MST greedily — always picking the cheapest available edge that does not create a cycle — and the result is guaranteed to be optimal. This eliminates the need to try all combinations.
Optimal Approach - Kruskal's Algorithm with Union-Find
Intuition
Instead of trying every possible combination of edges, what if we built the spanning tree one edge at a time, always picking the cheapest edge that does not create a cycle?
Imagine you are a city planner connecting towns with roads. You lay out all the possible road segments in front of you, sorted from cheapest to most expensive. You start picking roads from the cheapest end. Before you build each road, you ask one question: "Are the two towns this road connects already reachable from each other through roads I have already built?" If yes, this road would create a redundant loop, so you skip it. If no, you build it. You keep going until every town is connected.
This is Kruskal's algorithm — a greedy approach that sorts all edges by weight and then adds them one by one, skipping any edge that would create a cycle. The mathematical guarantee behind this strategy is the cut property: for any partition of the vertices into two groups, the lightest edge crossing the partition is always part of some MST.
The remaining question is: how do we quickly check whether two vertices are already connected? A brute-force BFS/DFS for each edge would cost O(V) per check. Instead, we use a clever data structure called Union-Find (Disjoint Set Union) that answers this question in nearly O(1) time by tracking which "component" each vertex belongs to. When we add an edge, we merge the two components. When we check for a cycle, we simply compare the component roots of the two endpoints.
Step-by-Step Explanation
Let's trace through with V = 5, E = 7, edges = [[0,1,2], [1,2,3], [0,2,4], [1,4,5], [0,3,6], [2,4,7], [1,3,8]]:
Step 1: Sort all edges by weight
Sorted order: (0-1, w=2), (1-2, w=3), (0-2, w=4), (1-4, w=5), (0-3, w=6), (2-4, w=7), (1-3, w=8)
Step 2: Initialize Union-Find
Each vertex is its own component.
parent = [0, 1, 2, 3, 4], rank = [0, 0, 0, 0, 0]
Components: {0}, {1}, {2}, {3}, {4}
Step 3: Process edge 0-1 (weight 2)
find(0) = 0, find(1) = 1 → different components
No cycle → add edge to MST
Union(0, 1): set parent[1] = 0
MST weight = 2, edges in MST = 1
Components: {0,1}, {2}, {3}, {4}
Step 4: Process edge 1-2 (weight 3)
find(1) = 0, find(2) = 2 → different components
No cycle → add edge to MST
Union(0, 2): set parent[2] = 0
MST weight = 2 + 3 = 5, edges in MST = 2
Components: {0,1,2}, {3}, {4}
Step 5: Process edge 0-2 (weight 4) — CYCLE DETECTED
find(0) = 0, find(2) = 0 → SAME component!
Vertices 0 and 2 are already connected via path 0→1→2
Adding this edge would create the cycle 0-1-2-0
Skip this edge ✗
Step 6: Process edge 1-4 (weight 5)
find(1) = 0, find(4) = 4 → different components
No cycle → add edge to MST
Union(0, 4): set parent[4] = 0
MST weight = 5 + 5 = 10, edges in MST = 3
Components: {0,1,2,4}, {3}
Step 7: Process edge 0-3 (weight 6)
find(0) = 0, find(3) = 3 → different components
No cycle → add edge to MST
Union(0, 3): set parent[3] = 0
MST weight = 10 + 6 = 16, edges in MST = 4 = V-1 ✓
All vertices connected!
Result: MST weight = 16. We processed only 5 of the 7 edges before completing the MST.
Kruskal's Algorithm — Building the MST Greedily — Watch how Kruskal's algorithm processes edges in sorted order, using Union-Find to skip edges that would create cycles, until all vertices are connected.
Algorithm
- Sort all E edges by weight in ascending order
- Initialize a Union-Find structure with V vertices (each vertex is its own component)
- Initialize MST weight = 0 and edge count = 0
- For each edge (u, v, w) in sorted order:
a. Call find(u) and find(v) to get their component roots
b. If the roots are different (no cycle):- Add this edge to the MST: MST weight += w, edge count += 1
- Union the two components
c. If the roots are the same, skip this edge (it would create a cycle)
d. If edge count == V-1, the MST is complete — stop early
- Return MST weight
Code
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
vector<int> parent, rnk;
int find(int x) {
if (parent[x] != x)
parent[x] = find(parent[x]);
return parent[x];
}
bool unite(int x, int y) {
int px = find(x), py = find(y);
if (px == py) return false;
if (rnk[px] < rnk[py]) swap(px, py);
parent[py] = px;
if (rnk[px] == rnk[py]) rnk[px]++;
return true;
}
public:
int spanningTree(int V, int E,
vector<vector<int>>& edges) {
sort(edges.begin(), edges.end(),
[](const vector<int>& a,
const vector<int>& b) {
return a[2] < b[2];
});
parent.resize(V);
rnk.resize(V, 0);
for (int i = 0; i < V; i++)
parent[i] = i;
int mstWeight = 0, edgesAdded = 0;
for (auto& e : edges) {
if (unite(e[0], e[1])) {
mstWeight += e[2];
if (++edgesAdded == V - 1)
break;
}
}
return mstWeight;
}
};class Solution:
def spanningTree(self, V, E, edges):
edges.sort(key=lambda x: x[2])
parent = list(range(V))
rank = [0] * V
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def unite(x, y):
px, py = find(x), find(y)
if px == py:
return False
if rank[px] < rank[py]:
px, py = py, px
parent[py] = px
if rank[px] == rank[py]:
rank[px] += 1
return True
mst_weight = 0
edges_added = 0
for u, v, w in edges:
if unite(u, v):
mst_weight += w
edges_added += 1
if edges_added == V - 1:
break
return mst_weightimport java.util.*;
class Solution {
int[] parent, rank;
int find(int x) {
if (parent[x] != x)
parent[x] = find(parent[x]);
return parent[x];
}
boolean unite(int x, int y) {
int px = find(x), py = find(y);
if (px == py) return false;
if (rank[px] < rank[py]) {
int t = px; px = py; py = t;
}
parent[py] = px;
if (rank[px] == rank[py]) rank[px]++;
return true;
}
int spanningTree(int V, int E,
int[][] edges) {
Arrays.sort(edges,
(a, b) -> a[2] - b[2]);
parent = new int[V];
rank = new int[V];
for (int i = 0; i < V; i++)
parent[i] = i;
int mstWeight = 0, edgesAdded = 0;
for (int[] e : edges) {
if (unite(e[0], e[1])) {
mstWeight += e[2];
if (++edgesAdded == V - 1)
break;
}
}
return mstWeight;
}
}Complexity Analysis
Time Complexity: O(E log E)
The dominant cost is sorting all E edges by weight, which takes O(E log E) time. After sorting, we iterate through the edges and perform at most E union-find operations. With path compression and union by rank, each find and union operation takes amortized O(α(V)) time, where α is the inverse Ackermann function — a value so slowly growing that it is effectively constant (≤ 4 for all practical input sizes). So the total time for all union-find operations is O(E × α(V)) ≈ O(E). The overall complexity is dominated by the sort: O(E log E). Since E ≤ V², we have log E ≤ 2 log V, so this is also O(E log V).
Space Complexity: O(V + E)
We need O(V) space for the parent and rank arrays of the Union-Find structure, and O(E) for storing the edges (or sorting in-place). The total auxiliary space is O(V).