CS 304
Design and Analysis of Algorithm
Minimum Spanning Tree
Problem: Laying Telephone Wire
Central office
2
Wiring: Naïve Approach
Central office
Expensive!
3
Wiring: Better Approach
Central office
Minimize the total length of wire connecting the customers
4
A Networking Problem
Problem: The vertices represent 8 regional data centers which
need to be connected with high-speed data lines. Feasibility
studies show that the links illustrated above are possible, and the
cost in millions of dollars is shown next to the link. Which links
should be constructed to enable full communication (with relays
allowed) and keep the total cost minimal.
5
Links Will Form a Spanning Tree
Cost (T) = 47 + 23 + 75 + 74 + 55 + 74 + 79
= 427
6
Minimum Spanning Trees
• Undirected, connected graph
G = (V,E)
• Weight function W: E → R
(assigning cost or length or
other values to edges)
■ Spanning tree: tree that connects all the vertices
■ Minimum spanning tree: tree that connects all
the vertices and minimizes
7
Minimum Spanning Tree (MST)
A minimum spanning tree is a subgraph of an
undirected weighted graph G, such that
• it is a tree (i.e., it is acyclic)
• it covers all the vertices V
– contains |V| - 1 edges
• the total cost associated with tree edges is the
minimum among all possible spanning trees
• not necessarily unique
8
How Can We Generate a MST?
9 b 9 b
a 2 6 a 2 6
d d
4 5 4 5
5 4 5 4
5 e 5 e
c c
9
Greedy Choice
We will show two ways to build a minimum
spanning tree.
• A MST can be grown from the current spanning
tree by adding the nearest vertex and the edge
connecting the nearest vertex to the MST.
(Prim's algorithm)
• A MST can be grown from a forest of spanning
trees by adding the smallest edge connecting
two spanning trees. (Kruskal's algorithm)
10
Notation
• Tree-vertices: in the tree constructed so far
• Non-tree vertices: rest of vertices
Prim’s Selection rule
• Select the minimum weight edge between a
tree-node and a non-tree node and add to the
tree
11
The Prim algorithm Main Idea
Select a vertex to be a tree-node
while (there are non-tree vertices) { a 4
6
if there is no edge connecting a tree node
with a non-tree node 5
b u
return “no spanning tree”
14 2
10
select an edge of minimum weight c v
between a tree node and a non-tree node
3
8 15
add the selected edge and its new vertex d
to the tree
f
}
return tree
12
Prim’s Algorithm
• Vertex based algorithm
• Grows one tree T, one vertex at a time
13
Prim – Step 1
14
Prim – Step 2
15
Prim – Step 3
16
Prim – Step 4
17
Prim – Step 5
18
Prim – Step 6
19
Prim – Step 7 Done!!
Weight (T) = 23 + 29 + 31 + 32 + 47 + 54 + 66 = 282
20
Prim Algorithm:Variables
• r:
– Grow the minimum spanning tree from the root vertex “r”.
• Q:
– is a priority queue, holding all vertices that are not in the tree
now.
• key[v]:
– is the minimum weight of any edge connecting v to a vertex
in the tree.
• π [v]:
– names the parent of v in the tree.
• T[v] –
– Vertex v is already included in MST if T[v]==1, otherwise, it
is not included yet.
21
The execution of Prim's algorithm(moderate
part)
8 7
the root b c d 9
vertex 4
2
a 11 14 e
i 4
7 6
10
8
h g f
1 2
V a b c d e f g h i
T 1 0 0 0 0 0 0 0 0
Key 0 - - - - - - - -
π -1 - - - - - - - -
22
The execution of Prim's algorithm(moderate
part)
8 7
the root b c d 9
vertex 4
2
a 11 14 e
i 4
7 6
10
8
h g f
1 2
V a b c d e f g h i
T 1 0 0 0 0 0 0 0 0
Key 0 4 - - - - - 8 -
π -1 a - - - - - a -
23
The execution of Prim's algorithm(moderate
part)
8 7
the root b c d 9
vertex 4
2
a 11 14 e
i 4
7 6
10
8
h g f
1 2
Important: Update Key[v] only if T[v]==0
V a b c d e f g h i
T 1 1 0 0 0 0 0 0 0
Key 0 4 8 - - - - 8 -
π -1 a b - - - - a -
24
The execution of Prim's algorithm(moderate
part)
8 7
the root b c d 9
vertex 4
2
a 11 14 e
i 4
7 6
10
8
h g f
1 2
V a b c d e f g h i
T 1 1 1 0 0 0 0 0 0
Key 0 4 8 7 - 4 - 8 2
π -1 a b c - c - a c
25
The execution of Prim's algorithm(moderate
part)
8 7
the root b c d 9
vertex 4
2
a 11 14 e
i 4
7 6
10
8
h g f
1 2
V a b c d e f g h i
T 1 1 1 0 0 0 0 0 1
Key 0 4 8 7 - 4 6 7 2
π -1 a b c - c i i c
26
The execution of Prim's algorithm(moderate
part)
8 7
the root b c d 9
vertex 4
2
a 11 14 e
i 4
7 6
10
8
h g f
1 2
V a b c d e f g h i
T 1 1 1 0 0 1 0 0 1
Key 0 4 8 7 10 4 2 7 2
π -1 a b c f c f i c
27
The execution of Prim's algorithm(moderate
part)
8 7
the root b c d 9
vertex 4
2
a 11 14 e
i 4
7 6
10
8
h g f
1 2
V a b c d e f g h i
T 1 1 1 0 0 1 1 0 1
Key 0 4 8 7 10 4 2 1 2
π -1 a b c f c f g c
28
The execution of Prim's algorithm(moderate
part)
8 7
the root b c d 9
vertex 4
2
a 11 14 e
i 4
7 6
10
8
h g f
1 2
V a b c d e f g h i
T 1 1 1 0 0 1 1 1 1
Key 0 4 8 7 10 4 2 1 2
π -1 a b c f c f g c
29
The execution of Prim's algorithm(moderate
part)
8 7
the root b c d 9
vertex 4
2
a 11 14 e
i 4
7 6
10
8
h g f
1 2
V a b c d e f g h i
T 1 1 1 1 0 1 1 1 1
Key 0 4 8 7 9 4 2 1 2
π -1 a b c d c f g c
30
The execution of Prim's algorithm(moderate
part)
8 7
the root b c d 9
vertex 4
2
a 11 14 e
i 4
7 6
10
8
h g f
1 2
V a b c d e f g h i
T 1 1 1 1 1 1 1 1 1
Key 0 4 8 7 9 4 2 1 2
π -1 a b c d c f g c
31