Minimum Spanning Trees:Kruskal’s Algorithm
Introduction
Let G = (V, E) be a connected graph, where V is the set of vertices (nodes) and E is the set of
edges (connections between vertices).
In many real-world problems, each edge has a cost such as distance, time, or financial expense.
To model this, a weight is assigned to each edge.
A weighted graph is defined as: G = (V, E, w), where w : E → R is a function that assigns a real
number (weight) to each edge e ∈ E.
Suppose we want to connect a set of computer centers using communication lines. Each possible
connection has a cost, and we want to connect all centers with the minimum total cost.
This problem can be modeled using a weighted graph where vertices represent computer centers,
edges represent possible connections, and weights represent connection costs.
Spanning Tree
A spanning tree of a connected graph G = (V, E) is a subgraph T = (V, ET) such that:
• It includes all vertices: V(T) = V
• It is connected
• It contains no cycles
For any spanning tree: |ET| = |V| − 1
Minimum Spanning Tree (MST)
A minimum spanning tree is a spanning tree whose total edge weight is minimum among all
spanning trees of the graph.
If T is a spanning tree, its total weight is:
W(T) = Σ w(e), for all e ∈ ET
A minimum spanning tree T* satisfies:
W(T*) ≤ W(T) for every spanning tree T of G.
Properties of Minimum Spanning Trees
Property 1: A minimum spanning tree always contains exactly |V| − 1 edges.
Property 2: The MST connects all vertices in the graph.
Property 3: A minimum spanning tree contains no cycles.
Property 4: Among all spanning trees, the MST has the smallest total weight.
Property 5: The minimum weight edge crossing a cut belongs to at least one MST (Cut Property).
Property 6: If all edge weights are distinct, the MST is unique.
Kruskal’s Algorithm
Historical Background
Joseph Bernard Kruskal (1928–2010) was an American mathematician who developed
Kruskal’s Algorithm for finding minimum spanning trees while he was a graduate student
at Princeton University in the 1950s. He received his Ph.D. in 1954 and later worked at
Bell Laboratories for many years.
Kruskal made important contributions to graph theory, statistics, and multidimensional
scaling. His algorithm became one of the most widely used methods for solving
minimum spanning tree problems in computer science and network design.
Kruskal’s algorithm is a greedy method used to construct a minimum spanning tree.
The algorithm works by:
• Sorting all edges in increasing order of weight
• Repeatedly adding the smallest edge
• Avoiding cycles during selection
• Stopping when the number of selected edges becomes |V| − 1
Full Worked Example
Consider the weighted graph:
V = {A, B, C, D, E}
E = {(A,B,4), (A,C,2), (A,D,5), (B,C,1), (B,D,3), (C,D,8), (C,E,10), (D,E,2)}
6.1 Sorted Edge Table
Edge Weight
B–C 1
A–C 2
D–E 2
B–D 3
A–B 4
A–D 5
C–D 8
C–E 10
6.2 Step-by-Step Selection
Step Edge Action Reason
1 B–C Accept No cycle
2 A–C Accept No cycle
3 D–E Accept No cycle
4 B–D Accept Connects components
5 A–B Reject Forms cycle
6 A–D Reject Forms cycle
7 C–D Reject Forms cycle
8 C–E Reject Forms cycle
6.3 Final Minimum Spanning Tree
T = {(B,C), (A,C), (D,E), (B,D)}
Total Weight: W(T) = 1 + 2 + 2 + 3 = 8
Real-Life Applications of Kruskal’s Algorithm
Example 1: Internet & Telecommunications Networks
Scenario: A telecom company wants to connect cities using fiber optic cables with minimum
installation cost.
Step 1: Sort Edges
Edge Weight
B-C 1
A-C 2
D-E 2
B-D 3
A-B 4
C-D 5
Step 2: Apply Kruskal’s Algorithm
Step Edge Decision Reason
1 B-C Accept No cycle
2 A-C Accept No cycle
3 D-E Accept No cycle
4 B-D Accept No cycle
5 A-B Reject Forms cycle
6 C-D Reject Forms cycle
Minimum Spanning Tree Total Cost = 8
Graph and Final MST
Example 2: Electrical Power Grid Design
Scenario: An engineer wants to connect substations with minimum power line cost.
Step 1: Sort Edges
Edge Weight
P-R 1
R-S 2
P-Q 3
S-T 4
Q-S 5
Q-R 7
Step 2: Apply Kruskal’s Algorithm
Step Edge Decision Reason
1 P-R Accept No cycle
2 R-S Accept No cycle
3 P-Q Accept No cycle
4 S-T Accept No cycle
5 Q-S Reject Forms cycle
6 Q-R Reject Forms cycle
Minimum Spanning Tree Total Cost = 10
Graph and Final MST
Example 3: Water Pipeline Systems
Scenario: A city wants to connect neighborhoods using the cheapest pipeline network.
Step 1: Sort Edges
Edge Weight
W-X 2
X-Y 3
Y-Z 4
X-Z 5
W-Y 6
Step 2: Apply Kruskal’s Algorithm
Step Edge Decision Reason
1 W-X Accept No cycle
2 X-Y Accept No cycle
3 Y-Z Accept No cycle
4 X-Z Reject Forms cycle
5 W-Y Reject Forms cycle
Minimum Spanning Tree Total Cost = 9
Graph and Final MST
Example 4: Computer Network Design (LAN/WAN)
Scenario: An IT company wants to connect office computers using minimum cable cost.
Step 1: Sort Edges
Edge Weight
M-N 1
N-O 2
O-P 3
M-O 4
N-P 5
Step 2: Apply Kruskal’s Algorithm
Step Edge Decision Reason
1 M-N Accept No cycle
2 N-O Accept No cycle
3 O-P Accept No cycle
4 M-O Reject Forms cycle
5 N-P Reject Forms cycle
Minimum Spanning Tree Total Cost = 6
Graph and Final MST
Example 5: Road & Transportation Planning
Scenario: A government wants to connect villages using minimum road construction cost.
Step 1: Sort Edges
Edge Weight
4-5 1
1-3 2
1-2 3
2-3 4
3-5 5
2-4 6
Step 2: Apply Kruskal’s Algorithm
Step Edge Decision Reason
1 4-5 Accept No cycle
2 1-3 Accept No cycle
3 1-2 Accept No cycle
4 2-3 Reject Forms cycle
5 3-5 Accept No cycle
6 2-4 Reject Forms cycle
Minimum Spanning Tree Total Cost = 11
Graph and Final MST
Applications of Kruskal’s Algorithm
Telecommunication network design
Electrical power distribution systems
Road and transportation planning
Water pipeline systems
Computer network design (LAN/WAN)
Conclusion
Kruskal’s Algorithm is a simple and efficient greedy algorithm used to construct minimum
spanning trees in connected weighted graphs. It guarantees a minimum-cost solution while
avoiding cycles and is widely ap in networking, engineering, and infrastructure design.
References
Kenneth H. Rosen, Discrete Mathematics and Its Applications, 7th Edition.
Thomas H. Cormen et al., Introduction to Algorithms.
Ralph P. Grimaldi, Discrete and Combinatorial Mathematics.
C. L. Liu, Elements of Discrete Mathematics.