COMP251: Minimum Spanning Trees
Jérôme Waldispühl School of Computer Science
McGill University
Based on (Cormen et al., 2002) Based on slides from D. Plaisted (UNC)
Minimum Spanning Tree (Example)
• A town has a set of houses and a set of roads.
• A road connects 2 and only 2 houses.
• A road connecting houses u and v has a repair cost w(u, v).
Goal: Repair enough (and no more) roads such that:
1. everyone stays connected: can reach every house from all
other houses, and
2. total repair cost is minimum.
Model as graph
b8d8g 7
a9e 59i 33
12 c 1 f 6 h 11
• Undirected graph G = (V, E).
• Weight w(u, v) on each edge (u, v) ∈ E.
• Find T ⊆ E such that:
1. T connects all vertices (T is a spanning tree),
2. w(T ) = ∑ w(u, v) is minimized. (u,v)∈T
10
2
Minimum Spanning Tree (MST)
b8d8g 7
a9e 59i 33
10
2
12
c1f6h
• Ithas|V|−1edges.
• It has no cycles.
• It might not be unique.
11
Generic Algorithm
• Initially, A has no edges.
• Add edges to A and maintain the loop invariant:
“A is a subset of some MST”.
• Initialization: The empty set trivially satisfies the loop invariant.
• Maintenance: We add only safe edges, A remains a subset of
some MST.
• Termination: All edges added to A are in an MST, so when we
AßÆ;
while A is not a spanning tree do
find a edge (u, v) that is safe for A;
AßA È {(u, v)} return A
stop, A is a spanning tree that is also an MST.
A cut respects A if and only if no edge in A crosses the cut.
Definitions
cut partitions vertices into disjoint sets, S and V – S.
b 8 d 8 g 7
10
S a 9 e
2
e 59iV-S 33
12 c 1 f 6 h 11
This edge crosses the cut. A light edge crossing (one endpoint is in S and
cut (may not be unique) the other is in V – S.)
What is a safe edge?
b8d8g 7
a9e 59i 33
S 12 c 1 f 6 h 11 V-S
Intuitively: Is (c,f) safe when A=Æ?
• Let S be any set of vertices including c but not f.
• There has to be one edge (at least) that connects S with V − S.
• Why not choosing the one with the minimum weight?
10
2
edge in A
x
(x, y) crosses the cut.
LetT ́ =T-{(x,y)}È{(u,v)}. Because (u, v) is light for cut,
w(u, v) £ w(x, y). Thus,
w(T ́) = w(T)-w(x, y)+w(u, v)£w(T). Hence, T ́ is also a MST.
So, (u, v) is safe for A.
Safe edge
Theorem 1: Let (S, V-S) be any cut that respects A, and let (u, v) be a light edge crossing (S, V-S). Then, (u, v) is safe for A.
Proof:
Let T be a MST that includes A. Case 1: (u, v) in T. We’re done.
Case 2: (u, v) not in T. We have the following:
u
We show edges in T
y
cut
v
Corollary
In general, A will consist of several connected components.
Corollary: If (u, v) is a light edge connecting one CC in (V, A) to another CC in (V, A), then (u, v) is safe for A.
Kruskal’s Algorithm
1. Starts with each vertex in its own component.
2. Repeatedly merges two components into one by choosing a light edge that connects them (i.e., a light edge crossing the cut between them).
3. Scans the set of edges in monotonically increasing order by weight.
4. Uses a disjoint-set data structure to determine whether an edge connects vertices in different components.
Example
b8d8g 7
a9e 59i 33
10
2
12
c1f6h
11
Example
b8d8g 7
a9e 59i 33
10
2
12
c1f6h
11
Example
b8d8g 7
a9e 59i 33
10
2
12
c1f6h
11
Example
b8d8g 7
a9e 59i 33
10
2
12
c1f6h
11
Example
b8d8g 7
a9e 59i 33
10
2
12
Reject!
c1f6h
11
Example
b8d8g 7
a9e 59i 33
10
2
12
c1f6h
11
Example
b8d8g 7
a9e 59i 33
10
2
12
c1f6h
11
Example
b8d8g 7
a9e 59i 33
10
2
12
c1f6h
11
Example
b8d8g 7
a9e 59i 33
10
2
12
c1f6h
11
Example
b8d8g 7
a9e 59i 33
10
2
12
c1f6h
11
Example
b8d8g 7
a9e 59i 33
10
2
12
c1f6h
11
Example
b8d8g 7
a9e 59i 33
10
2
12
c1f6h
11
Example
b8d8g 7
a9e 59i 33
10
2
12
c1f6h
11
Example
b8d8g 7
a9e 59i 33
10
2
12
c1f6h
11
Kruskal’s complexity
• Initialize A: O(1)
• First for loop: |V| MAKE-SETs
• Sort E: O(E lg E)
• Second for loop: O(E) FIND-SETs and UNIONs
Assuming union by rank and path compression, m find/union operations on a set with n objects is 𝑂(𝑚 ( 𝛼 𝑛 ):
⟹𝑂 𝐸(𝛼 𝑉 +𝑂(𝐸(log(𝐸))
Moreover,𝛼 𝑉 =𝑂(log𝑉)=𝑂(log𝐸);(𝐸 ≥ 𝑉 −1) ⟹ 𝑂(𝐸 ( log(𝐸))
Since, 𝐸 ≤ 𝑉!⟹log𝐸 =𝑂(2log𝑉)=𝑂(log𝑉) ⟹ 𝑂(𝐸 ( log 𝑉)
Prim’s Algorithm
1. Builds one tree, so A is always a tree.
2. Starts from an arbitrary “root” r .
3. At each step, adds a light edge crossing cut (VA, V – VA) to A.
– Where VA = vertices that A is incident on.
Intuition behind Prim’s Algorithm
• ConsiderthesetofverticesScurrentlypartofthetree, and its complement (V-S). We have a cut of the graph and the current set of tree edges A is respected by this cut.
• Which edge should we add next? Light edge!
UNC Chapel Hill Lin/Foskey/Manocha
Finding a light edge
1. Uses a priority queue Q to find a light edge quickly.
2. EachobjectinQisavertexinV-VA.
3. Key of v has minimum weight of any edge (u, v), where u Î VA.
4. Then the vertex returned by Extract-Min is v such that there
exists u Î VA and (u, v) is light edge crossing (VA, V – VA).
5. Keyofvis¥ifvisnotadjacenttoanyvertexinVA.
Basics of Prim ’s Algorithm
• It works by adding leaves on at a time to the current tree.
– Start with the root vertex r (it can be any vertex). At any time, the subset of edges A forms a single tree. S = vertices of A.
– At each step, a light edge connecting a vertex in S to a vertex in V- S is added to the tree.
– The tree grows until it spans all the vertices in V.
• Implementation Issues:
– How to update the cut efficiently?
– How to determine the light edge quickly?
UNC Chapel Hill Lin/Foskey/Manocha
Implementation: Priority Queue
• Priority queue implemented using heap can support the
following operations in O(lg n) time:
– Insert (Q, u, key): Insert u with the key value key in Q
– u = Extract_Min(Q): Extract the item with minimum key value in Q – Decrease_Key(Q, u, new_key): Decrease the value of u’s key value to
new_key
• All the vertices that are not in S (the vertices of the edges in A) reside in a priority queue Q based on a key field. When the algorithm terminates, Q is empty. A = {(v, p[v]): v Î V – {r}}
UNC Chapel Hill Lin/Foskey/Manocha
Prim’s Algorithm
Notes: (i) A = {(v, p[v]) : v Î v – {r} – Q}. (ii) r is the root.
Q := V[G];
for each u Î Q do
key[u] := ¥ p[u] := Nil; Insert(Q,u)
Decrease-Key(Q,r,0); while Q 1 Æ do
u := Extract-Min(Q); for each v Î Adj[u] do
if v Î Q Ù w(u, v) < key[v] : p[v] := u;
Decrease-Key(Q,v,w(u,v));
Complexity:
Using binary heaps: O(E lg V). Initialization: O(V).
Building initial queue: O(V). V Extract-Min: O(V lgV).
E Decrease-Key: O(E lg V).
Using Fibonacci heaps: O(E + V lg V).
Example of Prim’s Algorithm Not in tree
a/0 5 b/¥ 7 c/¥
1
d/¥ 0 e/¥ 2 f/¥
11
3
-3
Q=abcdef 0 ¥¥¥¥¥
Example of Prim’s Algorithm a/0 5 b/5 7 c/¥
1
d/11 0 e/¥ 2 f/¥
11
3
-3
Q=bdcef 5 11 ¥ ¥ ¥
Example of Prim’s Algorithm a/0 5 b/5 7 c/7
1
d/11 0 e/3 2 f/¥
11
3
-3
Q=ecdf 3 711¥
Example of Prim’s Algorithm a/0 5 b/5 7 c/1
1
d/0 0 e/3 2 f/2
11
3
-3
Q=dcf 012
Example of Prim’s Algorithm a/0 5 b/5 7 c/1
1
d/0 0 e/3 2 f/2
11
3
-3
Q=c f 12
Example of Prim’s Algorithm a/0 5 b/5 7 c/1
1
d/0 0 e/3 2 f/-3
11
3
-3
Q=f -3
Example of Prim’s Algorithm a/0 5 b/5 7 c/1
1
d/0 0 e/3 2 f/-3
11
3
-3
Q=Æ
Example of Prim’s Algorithm
a/0 5 b/5
3
d/0 0 e/3
1
c/1
-3
f/-3
Correctness of Prim’s
• Again,showthateveryedgeaddedisasafeedgeforA
• Assume (u, v) is next edge to be added to A.
• Consider the cut (A, V-A).
– This cut respects A
– and (u, v) is the light edge across the cut
• Thus,bytheTheorem1,(u,v)issafe.
UNC Chapel Hill Lin/Foskey/Manocha
Time Complexity of Prim’s
• Initialization: 𝑂(𝑉 + 𝐸)
• Extract the light edge from the queue: O(V log 𝑉)
• Relax the neighbour edges: O(𝐸 log 𝑉)
⟹ 𝑂(𝑉 log 𝑉 + 𝐸 log 𝑉) = 𝑂(𝐸 log 𝑉) // same as Kruskall Note: Using Fibonacci heaps, we can obtain 𝑂(𝐸 + log 𝑉).