10.3.2 Kruskal's Algorithm

Introduction to Kruskal's Algorithm

Kruskal's algorithm is a method to find a minimum spanning tree (MST) of a connected, weighted graph. The MST is a subset of edges that connects all vertices in the graph without forming cycles and has the minimum total weight.

Steps of Kruskal's Algorithm

Sort the Edges by Weight
Initialise the MST
Iterate Through the Edges
Check for Cycles

Sort the Edges by Weight: List all edges in ascending order of their weights.

Initialise the MST: Start with an empty set of edges for the MST.

Iterate Through the Edges:

Add the smallest edge to the MST, provided it does not form a cycle.
Repeat until $v-1$ edges are included, where $v$ is the number of vertices.

Check for Cycles: Use a cycle-checking method, such as disjoint sets (union-find), to ensure no cycles are formed.

infoNote

Worked Example

Problem:

Find the minimum spanning tree for the following graph:

Edge	ABAB	ACAC	ADAD	BCBC	BDBD	CDCD
Weight	5	7	6	9	8	7

Step 1: Sort the Edges by Weight

List edges in ascending order:

AB = 5, \, AD = 6, \, AC = 7, \, CD = 7, \, BD = 8, \, BC = 9

Step 2: Initialise the MST

Start with an empty MST.

Step 3: Iterate Through the Edges

Add $AB = 5$

No cycle.
MST = $\{ AB \}$ Add $AD = 6$
No cycle.
MST = $\{ AB, AD \}$ Add $AC = 7$
No cycle.
MST = $\{ AB, AD, AC \}$ Skip $CD = 7$
Adding $CD$ would form a cycle. Add $BD = 8$
No cycle.
MST = $\{ AB, AD, AC, BD \}$

Step 4: Check the MST

The MST includes $v-1 = 4-1 = 3$ edges.

Result:

The minimum spanning tree is:

\text{Edges: } \{ AB, AD, AC, BD \}

\text{Total Weight: } 5 + 6 + 8 = :highlight[19]

Algorithm Complexity

Time Complexity:

Sorting edges: $O(e \log e)$ , where $e$ is the number of edges.
Cycle checking: $O(e \log v)$ using union-find.
Overall: $O(e \log e + e \log v)$

Space Complexity:

Union-find structures require $O(v)$ space.

Note Summary

infoNote

Common Mistakes

Skipping Cycle Checks: Always ensure no cycles are formed when adding edges.
Incorrect Sorting: Sorting the edges incorrectly leads to errors in the MST.
Premature Stopping: Stop only after including $v-1$ edges.
Confusion Between Trees: MST is unique only if edge weights are distinct; otherwise, multiple MSTs may exist.
Misinterpreting Graph Connectivity: Kruskal's algorithm works only for connected graphs; otherwise, it gives a spanning forest.

infoNote

Key Formulas and Concepts

Minimum Spanning Tree: A subset of edges connecting all vertices with no cycles and minimum total weight.
Number of Edges in MST: For $v$ vertices: $v-1$ edges.
Cycle Checking: Use disjoint sets (union-find) to ensure no cycles are formed while adding edges.

Kruskal's Algorithm Simplified Revision Notes for A-Level Edexcel Further Maths Core Pure

10.3.2 Kruskal's Algorithm

Introduction to Kruskal's Algorithm

Steps of Kruskal's Algorithm

Worked Example

Algorithm Complexity

Time Complexity:

Space Complexity:

Note Summary

Common Mistakes

Key Formulas and Concepts

500K+ Students Use These Powerful Tools to Master Kruskal's Algorithm For their A-Level Exams.

Other Revision Notes related to Kruskal's Algorithm you should explore