6 MST Prim
6 MST Prim
Algorithms
Central office
2
Wiring: Naïve Approach
Central office
Expensive!
3
Wiring: Better Approach
Central office
4
A Networking Problem
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)
7
Minimum Spanning Tree (MST)
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)
10
Notation
11
The Prim algorithm Main Idea
Select a vertex to be a tree-node
3
add the selected edge and its new vertex 8 15
to the tree d
} 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!!
20
Prim Algorithm (2)
MST-Prim(G,w,r)
01 Q V[G] // Q – vertices out of T
02 for each u Q
03 key[u]
04 key[r] 0 // r is the first tree node, let r=1
05 [r] NIL
06 while Q do
07 u ExtractMin(Q) // making u part of T
08 for each v Adj[u] do
09 if v Q and w(u,v) < key[v] then
10 [v] u
11 key[v] w(u,v)
21
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.
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 - - - - - - - -
-1 - - - - - - - -
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
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 -
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
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 -
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 0
Key 0 4 8 7 - 4 - 8 2
-1 a b c - c - a 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 0 0 0 1
Key 0 4 8 7 - 4 6 7 2
-1 a b c - c i 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 0 0 1
Key 0 4 8 7 10 4 2 7 2
-1 a b c f c f i 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 0 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 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
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 0 1 1 1 1
Key 0 4 8 7 9 4 2 1 2
-1 a b c d c f g c
31
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
32
Complexity: Prim Algorithm
MST-Prim(G,w,r)
01 Q V[G] // Q – vertices out of T
02 for each u Q
03 key[u] O(V)
04 key[r] 0
05 [r] NIL
06 while Q do O(V)
07 u ExtractMin(Q) // making u part of T Heap: O(lgV)
08 for each v Adj[u] do
Overall: O(E)
09 if v Q and w(u,v) < key[v] then
10 [v] u
11 key[v] w(u,v)
Decrease Key: O(lgV)
33