ECE 250 Algorithms and Data Structures

Kruskal’s algorithm

Douglas Wilhelm Harder, M.Math. LEL

Department of Electrical and Computer Engineering
University of Waterloo
Waterloo, Ontario, Canada

ece.uwaterloo.ca
dwharder@alumni.uwaterloo.ca

© 2006-2013 by Douglas Wilhelm Harder. Some rights reserved.

 Kruskal’s algorithm
2

Outline

This topic covers Kruskal’s algorithm:

– Finding a minimum spanning tree
– The idea and the algorithm
– An example
– Using a disjoint set data structure
 Kruskal’s algorithm
3

Kruskal’s Algorithm

Kruskal’s algorithm sorts the edges by weight and goes through the
edges from least weight to greatest weight adding the edges to an
empty graph so long as the addition does not create a cycle

The halting point is:

– When |V| – 1 edges have been added
• In this case we have a minimum spanning tree
– We have gone through all edges, in which case, we have a forest of
minimum spanning trees on all connected sub-graphs
 Kruskal’s algorithm
4

Example

Consider the game of Risk from Parker Brothers

– A game of world domination
– The world is divided into 42 connected regions

http://thunderbird37.com/tag/parker-brothers/
 Kruskal’s algorithm
5

Example

Consider the game of Risk from Parker Brothers

– A game of world domination
– The world is divided into 42 connected regions
– The regions are vertices and edges indicate adjacent regions

http://thunderbird37.com/tag/parker-brothers/
 Kruskal’s algorithm
6

Example

Consider the game of Risk from Parker Brothers

– A game of world domination
– The world is divided into 42 connected regions
– The regions are vertices and edges indicate adjacent regions
– The graph is sufficient to describe the game
 Kruskal’s algorithm
7

Example

Consider the game of Risk from Parker Brothers

– Here is a more abstract representation of the game board
– Suddenly, it’s less interesting: “I’ve conquered the graph!”
 Kruskal’s algorithm
8

Example

We’ll focus on Asia

http://thunderbird37.com/tag/parker-brothers/
 Kruskal’s algorithm
9

Example

Here is our abstract representation

 Kruskal’s algorithm
10

Example

Let us give a weight to each of the edges

 Kruskal’s algorithm
11

Example {C, E}
{H, I}
{G, I}
{F, G}
First, we sort the edges based on weight
{B, E}
{E, H}
{B, C}
{H, K}
{H, L}
{D, E}
{G, H}
{I, K}
{B, D}
{D, F}
{E, G}
{K, L}
{J, K}
{J, I}
{J, G}
{A, B}
{A, D}
{E, F}
 Kruskal’s algorithm
12

Example {C, E}
{H, I}
{G, I}
{F, G}
We start by adding edge {C, E}
{B, E}
{E, H}
{B, C}
{H, K}
{H, L}
{D, E}
{G, H}
{I, K}
{B, D}
{D, F}
{E, G}
{K, L}
{J, K}
{J, I}
{J, G}
{A, B}
{A, D}
{E, F}
 Kruskal’s algorithm
13

Example {C, E}
{H, I}
{G, I}
{F, G}
We add edge {H, I}
{B, E}
{E, H}
{B, C}
{H, K}
{H, L}
{D, E}
{G, H}
{I, K}
{B, D}
{D, F}
{E, G}
{K, L}
{J, K}
{J, I}
{J, G}
{A, B}
{A, D}
{E, F}
 Kruskal’s algorithm
14

Example {C, E}
{H, I}
{G, I}
{F, G}
We add edge {G, I}
{B, E}
{E, H}
{B, C}
{H, K}
{H, L}
{D, E}
{G, H}
{I, K}
{B, D}
{D, F}
{E, G}
{K, L}
{J, K}
{J, I}
{J, G}
{A, B}
{A, D}
{E, F}
 Kruskal’s algorithm
15

Example {C, E}
{H, I}
{G, I}
{F, G}
We add edge {F, G}
{B, E}
{E, H}
{B, C}
{H, K}
{H, L}
{D, E}
{G, H}
{I, K}
{B, D}
{D, F}
{E, G}
{K, L}
{J, K}
{J, I}
{J, G}
{A, B}
{A, D}
{E, F}
 Kruskal’s algorithm
16

Example {C, E}
{H, I}
{G, I}
{F, G}
We add edge {B, E}
{B, E}
{E, H}
{B, C}
{H, K}
{H, L}
{D, E}
{G, H}
{I, K}
{B, D}
{D, F}
{E, G}
{K, L}
{J, K}
{J, I}
{J, G}
{A, B}
{A, D}
{E, F}
 Kruskal’s algorithm
17

Example {C, E}
{H, I}
{G, I}
{F, G}
We add edge {E, H}
{B, E}
– This coalesces the two spanning sub-trees into one {E, H}
{B, C}
{H, K}
{H, L}
{D, E}
{G, H}
{I, K}
{B, D}
{D, F}
{E, G}
{K, L}
{J, K}
{J, I}
{J, G}
{A, B}
{A, D}
{E, F}
 Kruskal’s algorithm
18

Example {C, E}
{H, I}
{G, I}
{F, G}
We try adding {B, C}, but it creates a cycle
{B, E}
{E, H}
{B, C}
{H, K}
{H, L}
{D, E}
{G, H}
{I, K}
{B, D}
{D, F}
{E, G}
{K, L}
{J, K}
{J, I}
{J, G}
{A, B}
{A, D}
{E, F}
 Kruskal’s algorithm
19

Example {C, E}
{H, I}
{G, I}
{F, G}
We add edge {H, K}
{B, E}
{E, H}
{B, C}
{H, K}
{H, L}
{D, E}
{G, H}
{I, K}
{B, D}
{D, F}
{E, G}
{K, L}
{J, K}
{J, I}
{J, G}
{A, B}
{A, D}
{E, F}
 Kruskal’s algorithm
20

Example {C, E}
{H, I}
{G, I}
{F, G}
We add edge {H, L}
{B, E}
{E, H}
{B, C}
{H, K}
{H, L}
{D, E}
{G, H}
{I, K}
{B, D}
{D, F}
{E, G}
{K, L}
{J, K}
{J, I}
{J, G}
{A, B}
{A, D}
{E, F}
 Kruskal’s algorithm
21

Example {C, E}
{H, I}
{G, I}
{F, G}
We add edge {D, E}
{B, E}
{E, H}
{B, C}
{H, K}
{H, L}
{D, E}
{G, H}
{I, K}
{B, D}
{D, F}
{E, G}
{K, L}
{J, K}
{J, I}
{J, G}
{A, B}
{A, D}
{E, F}
 Kruskal’s algorithm
22

Example {C, E}
{H, I}
{G, I}
{F, G}
We try adding {G, H}, but it creates a cycle
{B, E}
{E, H}
{B, C}
{H, K}
{H, L}
{D, E}
{G, H}
{I, K}
{B, D}
{D, F}
{E, G}
{K, L}
{J, K}
{J, I}
{J, G}
{A, B}
{A, D}
{E, F}
 Kruskal’s algorithm
23

Example {C, E}
{H, I}
{G, I}
{F, G}
We try adding {I, K}, but it creates a cycle
{B, E}
{E, H}
{B, C}
{H, K}
{H, L}
{D, E}
{G, H}
{I, K}
{B, D}
{D, F}
{E, G}
{K, L}
{J, K}
{J, I}
{J, G}
{A, B}
{A, D}
{E, F}
 Kruskal’s algorithm
24

Example {C, E}
{H, I}
{G, I}
{F, G}
We try adding {B, D}, but it creates a cycle
{B, E}
{E, H}
{B, C}
{H, K}
{H, L}
{D, E}
{G, H}
{I, K}
{B, D}
{D, F}
{E, G}
{K, L}
{J, K}
{J, I}
{J, G}
{A, B}
{A, D}
{E, F}
 Kruskal’s algorithm
25

Example {C, E}
{H, I}
{G, I}
{F, G}
We try adding {D, F}, but it creates a cycle
{B, E}
{E, H}
{B, C}
{H, K}
{H, L}
{D, E}
{G, H}
{I, K}
{B, D}
{D, F}
{E, G}
{K, L}
{J, K}
{J, I}
{J, G}
{A, B}
{A, D}
{E, F}
 Kruskal’s algorithm
26

Example {C, E}
{H, I}
{G, I}
{F, G}
We try adding {E, G}, but it creates a cycle
{B, E}
{E, H}
{B, C}
{H, K}
{H, L}
{D, E}
{G, H}
{I, K}
{B, D}
{D, F}
{E, G}
{K, L}
{J, K}
{J, I}
{J, G}
{A, B}
{A, D}
{E, F}
 Kruskal’s algorithm
27

Example {C, E}
{H, I}
{G, I}
{F, G}
By observation, we can still add edges {J, K} and {A, B}
{B, E}
{E, H}
{B, C}
{H, K}
{H, L}
{D, E}
{G, H}
{I, K}
{B, D}
{D, F}
{E, G}
{K, L}
{J, K}
{J, I}
{J, G}
{A, B}
{A, D}
{E, F}
 Kruskal’s algorithm
28

Example {C, E}
{H, I}
{G, I}
{F, G}
Having added {A, B}, we now have 11 edges
{B, E}
– We terminate the loop {E, H}
– We have our minimum spanning tree {B, C}
{H, K}
{H, L}
{D, E}
{G, H}
{I, K}
{B, D}
{D, F}
{E, G}
{K, L}
{J, K}
{J, I}
{J, G}
{A, B}
{A, D}
{E, F}
 Kruskal’s algorithm
29

Analysis

Implementation
– We would store the edges and their weights in an array
– We would sort the edges using either quicksort or some distribution sort
– To determine if a cycle is created, we could perform a traversal
• A run-time of O(|V|)
– Consequently, the run-time would be O(|E| ln(|E|) + |E|·|V|)
– However, |E| = O(|V|2), so ln(E) = O(ln(|V|2)) = O(2 ln(|V|)) = O(ln(|V|))
– Consequently, the run-time would be O(|E| ln(|V|) + |E||V|) = O(|E|·|V|)

The critical operation is determining if two vertices are connected

 Kruskal’s algorithm
30

Analysis

Instead, we could use disjoint sets

– Consider edges in the same connected sub-graph as forming a set

{B, C, E}, {F, G, H, I}

 Kruskal’s algorithm
31

Analysis

Instead, we could use disjoint sets

– Consider edges in the same connected sub-graph as forming a set
– If the vertices of the next edge are in different sets, take the union of the
two sets

Add edge (E, H)?

{B, C, E}, {F, G, H, I}
 Kruskal’s algorithm
32

Analysis

Instead, we could use disjoint sets

– Consider edges in the same connected sub-graph as forming a set
– If the vertices of the next edge are in different sets, take the union of the
two sets

Add edge (E, H)?

{B, C, E}, {F, G, H, I} {B, C, E, F, G, H, I}
 Kruskal’s algorithm
33

Analysis

Instead, we could use disjoint sets

– Consider edges in the same connected sub-graph as forming a set
– If the vertices of the next edge are in different sets, take the union of the
two sets
– Do not add an edge if both vertices are in the same set
Add edge (E, H)?
{B, C, E}, {F, G, H, I} {B, C, E, F, G, H, I}
 Kruskal’s algorithm
34

Analysis

The disjoint set data structure has the following average run-times:
– Checking if two vertices are in the same set is Q(a(|V|))
– Taking the union of two disjoint sets is Q(a(|V|))
– For all possible sizes of |V|, a(|V|) = Q(1)
 Kruskal’s algorithm
35

Analysis

Thus, checking and building the minimum spanning tree is now O(|E|)

The dominant time is now the time required to sort the edges:
– Using quicksort, the run-time is O(|E| ln(|E|)) = O(|E| ln(|V|))
– If there is an efficient Q(|E|) sorting algorithm, the run-time is then Q(|E|)
 Kruskal’s algorithm
36

Example

Going through the example again with disjoint sets

 Kruskal’s algorithm
37

Example {C, E}
{H, I}
{G, I}
{F, G}
We start with twelve singletons
{B, E}
{A}, {B}, {C}, {D}, {E}, {F}, {G}, {H}, {I}, {J}, {K}, {L} {E, H}
{B, C}
{H, K}
{H, L}
{D, E}
{G, H}
{I, K}
{B, D}
{D, F}
{E, G}
{K, L}
{J, K}
{J, I}
{J, G}
{A, B}
{A, D}
{E, F}
 Kruskal’s algorithm
38

Example {C, E}
{H, I}
{G, I}
{F, G}
We start by adding edge {C, E}
{B, E}
{A}, {B}, {C, E}, {D}, {F}, {G}, {H}, {I}, {J}, {K}, {L} {E, H}
{B, C}
{H, K}
{H, L}
{D, E}
{G, H}
{I, K}
{B, D}
{D, F}
{E, G}
{K, L}
{J, K}
{J, I}
{J, G}
{A, B}
{A, D}
{E, F}
 Kruskal’s algorithm
39

Example {C, E}
{H, I}
{G, I}
{F, G}
We add edge {H, I}
{B, E}
{A}, {B}, {C, E}, {D}, {F}, {G}, {H, I}, {J}, {K}, {L} {E, H}
{B, C}
{H, K}
{H, L}
{D, E}
{G, H}
{I, K}
{B, D}
{D, F}
{E, G}
{K, L}
{J, K}
{J, I}
{J, G}
{A, B}
{A, D}
{E, F}
 Kruskal’s algorithm
40

Example {C, E}
{H, I}
{G, I}
{F, G}
Similarly, we add {G, I}, {F, G}, {B, E}
{B, E}
{A}, {B, C, E}, {D}, {F, G, H, I}, {J}, {K}, {L} {E, H}
{B, C}
{H, K}
{H, L}
{D, E}
{G, H}
{I, K}
{B, D}
{D, F}
{E, G}
{K, L}
{J, K}
{J, I}
{J, G}
{A, B}
{A, D}
{E, F}
 Kruskal’s algorithm
41

Example {C, E}
{H, I}
{G, I}
{F, G}
The vertices of {E, H} are in different sets
{B, E}
{A}, {B, C, E}, {D}, {F, G, H, I}, {J}, {K}, {L} {E, H}
{B, C}
{H, K}
{H, L}
{D, E}
{G, H}
{I, K}
{B, D}
{D, F}
{E, G}
{K, L}
{J, K}
{J, I}
{J, G}
{A, B}
{A, D}
{E, F}
 Kruskal’s algorithm
42

Example {C, E}
{H, I}
{G, I}
{F, G}
Adding edge {E, H} creates a larger union
{B, E}
{A}, {B, C, E, F, G, H, I}, {D}, {J}, {K}, {L} {E, H}
{B, C}
{H, K}
{H, L}
{D, E}
{G, H}
{I, K}
{B, D}
{D, F}
{E, G}
{K, L}
{J, K}
{J, I}
{J, G}
{A, B}
{A, D}
{E, F}
 Kruskal’s algorithm
43

Example {C, E}
{H, I}
{G, I}
{F, G}
We try adding {B, C}, but it creates a cycle
{B, E}
{A}, {B, C, E, F, G, H, I}, {D}, {J}, {K}, {L} {E, H}
{B, C}
{H, K}
{H, L}
{D, E}
{G, H}
{I, K}
{B, D}
{D, F}
{E, G}
{K, L}
{J, K}
{J, I}
{J, G}
{A, B}
{A, D}
{E, F}
 Kruskal’s algorithm
44

Example {C, E}
{H, I}
{G, I}
{F, G}
We add edge {H, K}, {H, L} and {D, E}
{B, E}
{A}, {B, C, D, E, F, G, H, I, K, L}, {J} {E, H}
{B, C}
{H, K}
{H, L}
{D, E}
{G, H}
{I, K}
{B, D}
{D, F}
{E, G}
{K, L}
{J, K}
{J, I}
{J, G}
{A, B}
{A, D}
{E, F}
 Kruskal’s algorithm
45

Example {C, E}
{H, I}
{G, I}
{F, G}
Both G and H are in the same set
{B, E}
{A}, {B, C, D, E, F, G, H, I, K, L}, {J} {E, H}
{B, C}
{H, K}
{H, L}
{D, E}
{G, H}
{I, K}
{B, D}
{D, F}
{E, G}
{K, L}
{J, K}
{J, I}
{J, G}
{A, B}
{A, D}
{E, F}
 Kruskal’s algorithm
46

Example {C, E}
{H, I}
{G, I}
{F, G}
Both {I, K} are in the same set
{B, E}
{A}, {B, C, D, E, F, G, H, I, K, L}, {J} {E, H}
{B, C}
{H, K}
{H, L}
{D, E}
{G, H}
{I, K}
{B, D}
{D, F}
{E, G}
{K, L}
{J, K}
{J, I}
{J, G}
{A, B}
{A, D}
{E, F}
 Kruskal’s algorithm
47

Example {C, E}
{H, I}
{G, I}
{F, G}
Both {B, D} are in the same set
{B, E}
{A}, {B, C, D, E, F, G, H, I, K, L}, {J} {E, H}
{B, C}
{H, K}
{H, L}
{D, E}
{G, H}
{I, K}
{B, D}
{D, F}
{E, G}
{K, L}
{J, K}
{J, I}
{J, G}
{A, B}
{A, D}
{E, F}
 Kruskal’s algorithm
48

Example {C, E}
{H, I}
{G, I}
{F, G}
Both {D, F} are in the same set
{B, E}
{A}, {B, C, D, E, F, G, H, I, K, L}, {J} {E, H}
{B, C}
{H, K}
{H, L}
{D, E}
{G, H}
{I, K}
{B, D}
{D, F}
{E, G}
{K, L}
{J, K}
{J, I}
{J, G}
{A, B}
{A, D}
{E, F}
 Kruskal’s algorithm
49

Example {C, E}
{H, I}
{G, I}
{F, G}
We end when there is only one set, having added (A, B)
{B, E}
{A, B, C, D, E, F, G, H, I, K, L, J} {E, H}
{B, C}
{H, K}
{H, L}
{D, E}
{G, H}
{I, K}
{B, D}
{D, F}
{E, G}
{K, L}
{J, K}
{J, I}
{J, G}
{A, B}
{A, D}
{E, F}
 Kruskal’s algorithm
50

Summary

This topic has covered Kruskal’s algorithm

– Sort the edges by weight
– Create a disjoint set of the vertices
– Begin adding the edges one-by-one checking to ensure no cycles are
introduced
– The result is a minimum spanning tree
– The run time is O(|E| ln(|V|)
 Kruskal’s algorithm
51

References

Wikipedia, http://en.wikipedia.org/wiki/Minimum_spanning_tree
Wikipedia, http://en.wikipedia.org/wiki/Kruskal’s_algorithm

These slides are provided for the ECE 250 Algorithms and Data Structures course. The
material in it reflects Douglas W. Harder’s best judgment in light of the information available to
him at the time of preparation. Any reliance on these course slides by any party for any other
purpose are the responsibility of such parties. Douglas W. Harder accepts no responsibility for
damages, if any, suffered by any party as a result of decisions made or actions based on these
course slides for any other purpose than that for which it was intended.