23.2 Kruskal Algorithm

Document last modified:

Review

FIND-SET ( x )
   if p[ x ] ≠ x then return FIND-SET( p[ x ] )
   return x

FIND-SET( 7 ) returns the set representative 5.

-- join two sets containing items x and y together
UNION (x, y)
   a ← FIND-SET (x)       -- a is x's representative
   b ← FIND-SET (y)       -- b is y's representative
   p[ a ] ← b                  -- now b is a's parent, and FIND (x) would return b

UNION( 7, 3)

a = { 5 10 12 7 }

b = { 2 13 3 }

⇒

Kruskal Algorithm

G = (V, E) is a connected, undirected, weighted graph. w : E → R.

Starts with each vertex being its own component, a singleton set.
Selects edges in nondecreasing order by weight, so always the minimum.
If the selected edge's vertices are in disjoint sets, i.e. respects the cut, then it is a light-edge between the sets (components).
Repeatedly merges two components into one by choosing the light edge that connects them (i.e., the light edge crossing the cut between them).

This light edge is always part of the MST by Corollary 23.2
A greedy algorithm, always selects the remaining edge with the lowest weight.

Set-Of-Edges MST-Kruskal (G, w)
-- pre: G is a connected graph -- post: result = MST of G
1	A ← \|
2	for each vertex v ∈ G.V	O(\|V\|)
3	Make-Set (v)	O(1)
4	Sort the edges of E, taken in nondecreasing order by weight w	O(E lg E)
	-- Perform MST algorithm
5	for each edge (u, v) ∈ G.E, taken in nondecreasing order by weight	O(E)
6	if Find-Set (u) ≠ Find-Set (v) -- disjoint sets, (u,v) light edge	O(E lg E)
7	A ← A U {(u, v)} -- and safe, A \| {(u, v)} ⊆ MST	lg E is for
8	Union (u, v) -- u and v in same set	FIND-SET path
9	return A	compression

Weight	edge	Find-Set (u) ≠ Find-Set (v)	A	Non-singleton Sets
1	(c, f )	safe	{(c,f)}	{c,f}
2	(g,i)	safe	{(c,f), (g,i)}	{c,f} {g,i}
3	(e,f)	safe	{(c,f), (g,i), (e,f)}	{c,e,f)} {g,i}
3	(c,e)	reject
5	(d,h)	safe	{(c,f), (g,i), (e,f), (d,h)}	{c,e,f} {g,i} {d,h}
6	(f,h)	safe	{(c,f), (g,i), (e,f), (d,h), (f,h)}	{c,d,e,f,h} {g,i}
7	(e,d)	reject
8	(b,d)	safe	{(c,f), (g,i), (e,f), (d,h), (f,h), (b,d)}	{b,c,d,e,f,h} {g,i}
8	(d,g)	safe	{(c,f),(g,i),(e,f),(d,h),(f,h),(b,d),(b,g)}	{b,c,d,e,f,h,g,i}
9	(b,c)	reject
9	(g,h)	reject
10	(a,b)	safe	{(c,f),(g,i),(e,f),(d,h),(f,h),(b,d),(b,g),(a,b)}	{a,b,c,d,e,f,h,g,i}

At this point, all vertices in one component (set), so all other edges will be rejected.

Since edges added in nondecreasing order by weight, A is a MST when for terminates.

Execution could be stopped when |V| − 1 edges have been added to A.

Question 23.1 - Complete the table for MST-Kruskal (G, w)

Set-Of-Edges MST-Kruskal (G, w)

1 A ← |

2 for each vertex v ∈ G.V

3    Make-Set (v)

4 Sort the edges of E, taken in nondecreasing order by weight w

5 for each edge (u, v) ∈ G.E, taken in nondecreasing order by weight

6    if Find-Set (u) ≠ Find-Set (v)

7     A ← A U {(u, v)}

8       Union (u, v)

9 return A

Weight edge Find-Set (u) ≠
Find-Set (v) A Non-Singleton
Sets

1 (g, h) safe {(g, h)} {g, h}

2 (c, i) safe {(g, h), (c, i)} {g, h} {c, i}

A = {}
V = {{a} {b} {c} {d} {e} {f} {g} {h} {i}}
E (sorted edge list) = <((g,h), 1) ((c,i), 2) ((f,g), 2) ((a,b), 4) ((c, f), 4)
((g,i), 6) ((c,d), 7) ((h,i), 7) ((a,h), 8) ((b,c), 8)
((d,e), 9) ((e,f), 10) ((b,h), 11) ((d,f), 14) >

Analysis - O(E lg E)

Line 6 - Find-Set is O(lg n) using path compression and union by rank

Line 8 - Union after running Find-Set using path compression on both vertices is O(1)

Set-Of-Edges MST-Kruskal (G, w)
-- pre: G is a connected graph -- post: result = MST of G
1	A ← \|
2	for each vertex v ∈ G.V	O(\|V\|)
3	Make-Set (v)	O(1)
4	Sort the edges of E, taken in nondecreasing order by weight w	O(E lg E)
	-- Perform MST algorithm
5	for each edge (u, v) ∈ G.E, taken in nondecreasing order by weight	O(E)
6	if Find-Set (u) ≠ Find-Set (v) -- disjoint sets	O(E lg V)
7	A ← A U {(u, v)}
8	Union (u, v) -- u and v in same set	O(E)
9	return A