DSA: Graphs, Minimum Spanning Tree
Learn spanning trees, MST algorithms (Kruskal and Prim), Union-Find with path compression, and their real-world applications.
Spanning Tree and MST
A spanning tree of a connected undirected graph is a subgraph that includes all V vertices and exactly V-1 edges with no cycles. A Minimum Spanning Tree (MST) is the spanning tree whose total edge weight is the smallest possible.
Key MST Properties
An MST always has exactly V-1 edges and connects all vertices with the minimum total weight.
- A graph can have multiple MSTs if edges have equal weights
- MST is unique when all edge weights are distinct
- Cut property: the minimum weight edge crossing any cut of the graph is always in the MST
- Applications: network design, clustering, approximation algorithms for NP-hard problems
| Algorithm | Approach | Time Complexity | Best For |
|---|---|---|---|
| Kruskal's | Edge-based, global sort | O(E log E) | Sparse graphs |
| Prim's | Vertex-based, greedy growth | O(E log V) with heap | Dense graphs |
Union-Find (Disjoint Set Union)
Union-Find tracks which elements belong to the same connected component. Two operations power it: find(x) returns the root representative of x's component, and unite(x, y) merges two components.
Union-Find Operations
Without optimisations, find() takes O(n). Path compression and union by rank together bring the amortised cost to nearly O(1) per operation.
- find(x): follow parent pointers to the root of x
- unite(x, y): attach the root of one component to the root of the other
- Path compression: make every visited node point directly to the root during find()
- Union by rank: attach the shorter tree under the taller tree to limit height
Union-Find with Path Compression and Union by Rank
C++Path compression flattens the tree on every find(). Union by rank prevents the tree from growing tall. Together they give near O(1) amortised operations.
Cycle Detection Using Union-Find
When processing each edge in an undirected graph, if both endpoints already belong to the same component, adding the edge would create a cycle. This is the exact check Kruskal's algorithm uses to stay cycle-free.
DSU Cycle Check
unite() returns false when both endpoints share the same root meaning they are already connected and a new edge between them forms a cycle.
- For each edge (u, v): if find(u) == find(v), a cycle would be formed
- Otherwise, call unite(u, v) to merge their components
- O(α(n)) per edge check, effectively O(1) amortised
- Simpler and faster than DFS-based cycle detection for this specific task
Cycle Detection with Union-Find
C++unite() failing (returning false) is the cycle signal. No DFS needed, just process edges one by one.
Kruskal's Algorithm
Kruskal's algorithm sorts all edges by weight, then greedily adds each edge to the MST as long as it does not form a cycle (checked with Union-Find). It stops when V-1 edges are included.
Kruskal's Steps
Sort once, then use Union-Find to make each cycle check near O(1). The algorithm naturally finds the globally cheapest set of V-1 edges that connect all vertices.
- Step 1: sort all edges by weight ascending, O(E log E)
- Step 2: iterate sorted edges; use unite() to add edge if it connects two different components
- Step 3: stop when V-1 edges are added (MST is complete)
- If fewer than V-1 edges are added, the graph is disconnected (no MST exists)
Kruskal's Algorithm
C++Sorting edges by weight and checking cycle membership with Union-Find gives the MST greedily without reconsidering past decisions.
Prim's Algorithm
Prim's algorithm grows the MST from a single starting vertex. At each step it picks the cheapest edge that connects the current tree to an unvisited vertex and adds that vertex to the tree.
Prim's Greedy Growth
A min-heap stores (weight, vertex) pairs for all edges crossing the cut between the tree and the rest of the graph. The heap top is always the cheapest crossing edge.
- Initialise with start vertex at cost 0; all others at infinity
- Pop the minimum-cost unvisited vertex from the heap, mark it in the MST
- Push all its unvisited neighbours with their edge weights
- Skip heap entries for already-visited vertices (stale entries)
Prim's Algorithm with Min-Heap
C++inMST[] guards against reprocessing vertices. Each vertex is finalised the first time it is popped, the heap guarantees it carries the minimum edge cost.
Check If a Graph Is a Tree
A graph is a tree if and only if it is connected and has exactly V-1 edges. Equivalently: it is connected and contains no cycle. Both conditions can be verified in one DFS or Union-Find pass.
Tree Conditions
A tree on V vertices has exactly V-1 edges, is connected, and is acyclic. Any two of these three properties imply the third.
- Condition 1: E == V - 1
- Condition 2: the graph is connected (single DFS/BFS visits all V vertices)
- With Union-Find: process all edges; if any unite() returns false, a cycle exists
- After processing, check that all vertices share one root (fully connected)
Is Graph a Tree?
C++Three checks in order: correct edge count, no cycle (unite returns true for all edges), and one connected component.
Minimum Cost to Connect All Cities
Given cities and the cost to build a road between each pair, find the minimum total cost to connect all cities. This is a direct application of MST: the MST gives the cheapest way to connect all nodes.
MST as Minimum Network Cost
Any spanning tree connects all cities. The MST is the one with the minimum total road construction cost.
- Model cities as vertices and road costs as weighted edges
- Run Kruskal or Prim to find the MST
- The MST weight = minimum total cost to connect all cities
- If the graph is disconnected (some city pairs have no road option), no full connection is possible
Minimum Cost to Connect All Cities (Kruskal)
C++Sorting edges by cost and using Union-Find to avoid cycles gives the MST, which is the cheapest connected network.
Operations to Make Network Connected
Given n computers and cables connecting some of them, find the minimum number of cable reconnections needed to connect all computers. You can remove a redundant cable (one in a cycle) and use it to bridge two disconnected components.
Redundant Cables and Extra Components
Count both the number of connected components C and the number of redundant cables R. If R is less than C-1, connection is impossible. Otherwise, C-1 reconnections are needed.
- Redundant cable: an edge whose both endpoints are already in the same component
- Each redundant cable can bridge one pair of disconnected components
- Minimum reconnections needed = number of components - 1
- Possible only if redundant cables >= components - 1
Make Network Connected
C++unite() returning false counts a redundant cable. components - 1 is the minimum number of cables to redistribute. If redundant < need, it is impossible.
Knowledge Check
1. A spanning tree of a graph with V vertices has exactly:
2. Kruskal's algorithm builds the MST by:
3. Prim's algorithm selects the next edge to add by:
4. Path compression in Union-Find makes future find() calls faster by:
5. Union by rank ensures the Union-Find tree height stays at:
6. In Kruskal's algorithm, how is it determined whether adding an edge would create a cycle?
7. The time complexity of Kruskal's algorithm with Union-Find is:
8. Prim's algorithm with a binary heap priority queue runs in: