Greedy Method- Applications

1. Minimum cost spanning trees(MST-Prim’s Algorithm)

 Prim’s Algorithm
• In prim’s algorithm the tree starts with an
arbitrary root vertex r grows until the tree
spans all the vertices in V[G].
• At each step a light edge is added to the tree A
that connects an isolated vertex of G.
• During execution of the algorithm all vertices
that are not in the tree reside in a Min-Priority
Queue Q based on a key field.
 Prim’s Algorithm
• For each vertex v, Key[v] is the minimum
weight of any edge connecting to v to a vertex
in the tree.
• The field π[v] names the parent of v in the tree.
 Prim’s Algorithm
• Algorithm MST_Prim (G, w, r)

1. for each vertex u ϵ V[G] 8. for each v ϵ ADJ[u]

2. key [u] ← ∞ 9. if (v ϵ Q and w(u, v) <
3. π[u] ← NIL key [v])
4. key [r] ← 0 10. then π[v] ← u
11. key [v] ← w(u, v)
5. Q ← V[G]
12. return key and π
6. while (Q ≠ NULL)
7. u ← Extract_Min(Q)
 Prim's Algorithm
The steps are:

1. The new graph is constructed - with one node from the old graph.
2. While new graph has fewer than n nodes i.e n-1 edges for n nodes,
1. Find the node from the old graph with the smallest connecting
edge to the new graph,
2. Add it to the new graph

Note: each time selecting the node whose connecting edge has the
smallest weight out of the available nodes’ connecting edges.

❖ Every step will have joined one node, so that at the end we will have
one graph with all the nodes and it will be a minimum spanning tree
of the original graph.
 Prim’s Algorithm Example
• Find out the minimum cost spanning tree for the
connected graph shown below using Prim’s
algorithm.
8 7
b c d
4 9
2
11 4 14
a e
i
7 6
8 10

h 1
g 2
f
 Prim’s Algorithm Example
• Solution
• For the given graph the vertex set V [G] = {a, b,
c, d, e, f, g, h, i}
• The Edge set E = {(a, b), (b, c), (b, h), (c, d), (c,
f), (c, i), (d, e), (d, f), (e, f), (f, g), (g, h), (g, i), (h,
i)}

• The arbitrary starting vertex is a.

• Therefore r = a
 Prim’s Algorithm Example
for each vertex u ϵ V[G]
key [u] ← ∞
π[u] ← NIL
key [a] ∞ π [a] NIL
key [b] ∞ π [b] NIL
key [c] ∞ π [c] NIL
key [d] ∞ π [d] NIL
key [e] ∞ π [e] NIL
key [f] ∞ π [f] NIL
key [g] ∞ π [g] NIL
key [h] ∞ π [h] NIL
key [i] ∞ π [i] NIL
 Prim’s Algorithm Example
key [r] ← 0 key [a] = 0
Q ← V[G] Q = {a, b, c, d, e, f, g, h, i}

Q = {a, b, c, d, e, f, g, h, i}
key [a] 0 π [a] NIL
key [b] ∞ π [b] NIL
key [c] ∞ π [c] NIL
key [d] ∞ π [d] NIL
key [e] ∞ π [e] NIL
key [f] ∞ π [f] NIL
key [g] ∞ π [g] NIL
key [h] ∞ π [h] NIL
key [i] ∞ π [i] NIL
 Prim’s Algorithm Example π [a]
π [b]
NIL
a
π [c] NIL
while (Q ≠ NULL) True
π [d] NIL
u ← Extract_Min(Q) u=a
π [e] NIL
for each v ϵ ADJ[u] {b, h} ← ADJ[a]
π [f] NIL
v=b
π [g] NIL
if (b ϵ Q and w(a, b) < key [b]) If (b ϵ Q and 4 < ∞ ) True
π [h] a
then π[b] ← u π[b] ← a
π [i] NIL
key [b] ← w(u, v) key [b] ← 4
key [a] 0
v=h
key [b] 4
if (h ϵ Q and w(a, h) < key [h]) If (h ϵ Q and 8 < ∞ ) True
key [c] ∞
then π[h] ← u π[h] ← a
key [d] ∞
key [h] ← w(u, v) key [h] ← 8
key [e] ∞

Q = {b, c, d, e, f, g, h, i} key [f] ∞

key [g] ∞
key [h] ∞, 8
key [i] ∞
Prim’s Algorithm Example π [a]
π [b]
NIL
a
Q = {b, c, d, e, f, g, h, i} π [c] b
π [d] NIL
while (Q ≠ NULL) True
π [e] NIL
u ← Extract_Min(Q) u=b
π [f] NIL
for each v ϵ ADJ[u] {a, c, h} ← ADJ[b]
π [g] NIL
v=a
π [h] a
if (a ϵ Q and w(b,a) < key [a]) If (a ϵ Q and 4 < 0 ) False
π [i] NIL
v=c
key [a] 0
if (c ϵ Q and w(b,c) < key [c]) If (c ϵ Q and 8 < ∞ ) True
key [b] 4
then π[c] ← u π[c] ← b
key [c] ∞, 8
key [c] ← w(b, c) key [c] ← 8
key [d] ∞
v=h
key [e] ∞
if (h ϵ Q and w(b, h) < key [h]) If (h ϵ Q and 11 < 8 ) False
key [f] ∞
key [g] ∞

Q = {c, d, e, f, g, h, i} key [h] ∞, 8

key [i] ∞
Prim’s Algorithm Example π [a]
π [b]
NIL
a
Q = {c, d, e, f, g, h, i} π [c] b
π [d] c
while (Q ≠ NULL) True
π [e] NIL
u ← Extract_Min(Q) u=c
π [f] NIL
for each v ϵ ADJ[u] {b, d, i, f} ← ADJ[c]
π [g] NIL
v=b
π [h] a
if (b ϵ Q and w(c, b) < key [b]) If (b ϵ Q and 8 < 4 ) False
π [i] c
v=d
key [a] 0
if (d ϵ Q and w(c ,d) < key [d]) If (d ϵ Q and 7 < ∞ ) True
key [b] ∞, 4
then π[d] ← u π[d] ← c
key [c] ∞, 8
key [d] ← w(c, d) key [d] ← 7
key [d] ∞, 7
v=i
key [e] ∞
if (i ϵ Q and w(c, i) < key [i]) If (i ϵ Q and 2 < ∞ ) True
key [f] ∞
then π[i] ← u π[i] ← c
key [g] ∞
key [i] ← w(c, i) key [i] ← 2
key [h] ∞, 8
key [i] ∞, 2
Prim’s Algorithm Example π [a]
π [b]
NIL
a
Q = {c, d, e, f, g, h, i} π [c] b
π [d] c
v=f
π [e] NIL
if (f ϵ Q and w(c ,f) < key [f]) If (f ϵ Q and 4 < ∞ ) True
π [f] c
then π[f] ← u π[f] ← c
π [g] NIL
key [f] ← w(c, f) key [f] ← 4
π [h] a
π [i] c
key [a] 0
key [b] ∞, 4
key [c] ∞, 8
key [d] ∞, 7

Q = {d, e, f, g, h, i} key [e] ∞

key [f] ∞, 4
key [g] ∞
key [h] ∞, 8
key [i] ∞, 2
Prim’s Algorithm Example π [a]
π [b]
NIL
a
Q = {d, e, f, g, h, i} π [c] b
π [d] c
while (Q ≠ NULL) True
π [e] NIL
u ← Extract_Min(Q) u=i
π [f] c
for each v ϵ ADJ[i] {c, g, h} ← ADJ[i]
π [g] i
v=c
π [h] a, i
if (c ϵ Q and w(i ,c) < key [c]) If (c ϵ Q and 2 < 8 ) False
π [i] c
v=g
key [a] 0
if (g ϵ Q and w(i ,g) < key [g]) If (g ϵ Q and 6 < ∞ ) True
key [b] ∞, 4
then π[g] ← u π[g] ← i
key [c] ∞, 8
key [g] ← w(i, g) key [g] ← 6
key [d] ∞, 7
v=h
key [e] ∞
if (h ϵ Q and w(i ,h) < key [h]) If (h ϵ Q and 7 < 8 ) True
key [f] ∞, 4
then π[h] ← u π[h] ← i
key [g] ∞, 6
key [h] ← w(i, h) key [h] ← 7
key [h] ∞, 8, 7
Q = {d, e, f, g, h} key [i] ∞, 2
Prim’s Algorithm Example π [a]
π [b]
NIL
a
Q = {d, e, f, g, h} π [c] b
π [d] c
while (Q ≠ NULL) True
π [e] f
u ← Extract_Min(Q) u=f
π [f] c
for each v ϵ ADJ[f] {c, d, e, g} ← ADJ[f]
π [g] i
v=c
π [h] a, i
if (c ϵ Q and w(f ,c) < key [c]) If (c ϵ Q and 4 < 8 ) False
π [i] c
v=d
key [a] 0
if (d ϵ Q and w(f ,d) < key [d]) If (d ϵ Q and 14 < 7 ) False
key [b] ∞, 4
v=e
key [c] ∞, 8
if (e ϵ Q and w(f ,e) < key [e]) If (e ϵ Q and 10 < ∞ ) True
key [d] ∞, 7
then π[e] ← u π[e] ← f
key [e] ∞, 10
key [e] ← w(f, e) key [e] ← 10
key [f] ∞, 4
key [g] ∞, 6
key [h] ∞, 8, 7
key [i] ∞, 2
Prim’s Algorithm Example π [a]
π [b]
NIL
a
Q = {d, e, f, g, h} π [c] b
π [d] c
v=g
π [e] f
if (g ϵ Q and w(f ,g) < key [g]) If (g ϵ Q and 2 < 6 ) True
π [f] c
then π[g] ← u π[g] ← f
π [g] i, f
key [g] ← w(f, g) key [g] ← 2
π [h] a, i
π [i] c
key [a] 0
key [b] ∞, 4
key [c] ∞, 8
key [d] ∞, 7
key [e] ∞, 10
Q = {d, e, g, h} key [f] ∞, 4
key [g] ∞, 6, 2
key [h] ∞, 8, 7
key [i] ∞, 2
Prim’s Algorithm Example π [a]
π [b]
NIL
a
Q = {d, e, g, h} π [c] b
π [d] c
while (Q ≠ NULL) True
π [e] f
u ← Extract_Min(Q) u=g
π [f] c
for each v ϵ ADJ[g] {f, h, i} ← ADJ[g]
π [g] i, f
v=f
π [h] a, i, g
if (f ϵ Q and w(g ,f) < key [f]) If (f ϵ Q and 2 < 4 ) False
π [i] c
v=h
key [a] 0
if (h ϵ Q and w(g ,h) < key [h]) If (h ϵ Q and 1 < 7 ) True
key [b] ∞, 4
then π[h] ← u π[h] ← g
key [c] ∞, 8
key [h] ← w(g, h) key [h] ← 1
key [d] ∞, 7
v=i
key [e] ∞, 10
if (i ϵ Q and w(g ,i) < key [i]) If (i ϵ Q and 6 < 2 ) False
key [f] ∞, 4
key [g] ∞, 6, 2
Q = {d, e, h}
key [h] ∞, 8, 7, 1
key [i] ∞, 2
Prim’s Algorithm Example π [a]
π [b]
NIL
a
Q = {d, e, h} π [c] b
π [d] c
while (Q ≠ NULL) True
π [e] f
u ← Extract_Min(Q) u=h
π [f] c
for each v ϵ ADJ[h] {a, b, i, g} ← ADJ[h]
π [g] i, f
v=a
π [h] a, i, g
if (a ϵ Q and w(h ,a) < key [a]) If (a ϵ Q and 8 < 0 ) False
π [i] c
v=b
key [a] 0
if (b ϵ Q and w(h ,b) < key [b]) If (b ϵ Q and 11 < 4 ) False
key [b] ∞, 4
v=i
key [c] ∞, 8
if (i ϵ Q and w(h ,i) < key [i]) If (i ϵ Q and 7 < 2 ) False
key [d] ∞, 7
v=g
key [e] ∞, 10
if (g ϵ Q and w(h ,g) < key [g]) If (g ϵ Q and 1 < 2 ) False
key [f] ∞, 4
key [g] ∞, 6, 2
Q = {d, e}
key [h] ∞, 8, 7, 1
key [i] ∞, 2
Prim’s Algorithm Example π [a]
π [b]
NIL
a
Q = {d, e} π [c] b
π [d] c
while (Q ≠ NULL) True
π [e] f, d
u ← Extract_Min(Q) u=d
π [f] c
for each v ϵ ADJ[h] {c, e, f} ← ADJ[d]
π [g] i, f
v=c
π [h] a, i, g
if (c ϵ Q and w(d ,c) < key [c]) If (c ϵ Q and 7 < 8 ) False
π [i] c
v=e
key [a] 0
if (e ϵ Q and w(d ,e) < key [e]) If (e ϵ Q and 9 < 10 ) True
key [b] ∞, 4
then π[e] ← u π[e] ← d
key [c] ∞, 8
key [e] ← w(d, e) key [e] ← 9
key [d] ∞, 7
v=f
key [e] ∞, 10, 9
if (f ϵ Q and w(d ,f) < key [f]) If (f ϵ Q and 14 < 4 ) False
key [f] ∞, 4
key [g] ∞, 6, 2
Q = {e}
key [h] ∞, 8, 7, 1
key [i] ∞, 2
Prim’s Algorithm Example π [a]
π [b]
NIL
a
Q = {e} π [c] b
π [d] c
while (Q ≠ NULL) True
π [e] f, d
u ← Extract_Min(Q) u=e
π [f] c
for each v ϵ ADJ[h] {d, f} ← ADJ[e]
π [g] i, f
v=d
π [h] a, i, g
if (d ϵ Q and w(e ,d) < key [d]) If (d ϵ Q and 9 < 7 ) False
π [i] c
v=f
key [a] 0
if (f ϵ Q and w(e ,f) < key [f]) If (f ϵ Q and 10 < 4 ) False
key [b] ∞, 4
key [c] ∞, 8
Q={} key [d] ∞, 7
key [e] ∞, 10, 9
while (Q ≠ NULL) False key [f] ∞, 4
return key and π key [g] ∞, 6, 2
key [h] ∞, 8, 7, 1
key [i] ∞, 2
Prim’s Algorithm Example π [a]
π [b]
NIL
a
π [c] b
Q={} π [d] c
The minimum cost spanning tree A will π [e] f, d
contain the edges such that π [f] c
A = { (v, π [v]) : v ϵ V[G] – {r} – Q } π [g] i, f
A = { (b, a), (c, b), (d, c), (e, d), (f, c), (g, f), π [h] a, i, g
(h, g), (i, c) } π [i] c
key [a] 0
key [b] ∞, 4
key [c] ∞, 8
key [d] ∞, 7
key [e] ∞, 10, 9
key [f] ∞, 4
key [g] ∞, 6, 2
key [h] ∞, 8, 7, 1
key [i] ∞, 2
Prim’s Algorithm Example π [a]
π [b]
NIL
a
π [c] b
A = { (b, a), (c, b), (d, c), (e, d), (f, c), (g, f),
π [d] c
(h, g), (i, c) }
π [e] f, d
π [f] c
8 7
b c d π [g] i, f
4 9 π [h] a, i, g
2
π [i] c
4
a e key [a] 0
i key [b] ∞, 4
key [c] ∞, 8
h g key [d] ∞, 7
1 2 f
key [e] ∞, 10, 9
Total cost of the spanning tree =∑ Weight of the key [f] ∞, 4
edges in A key [g] ∞, 6, 2
=4+8+7+9+2+4+2+1 key [h] ∞, 8, 7, 1
= 37 key [i] ∞, 2
 Weighted Graph

B 4 C
4
2 1

A 4 E
1 F

D 2 3
10
G 5

5 6 3

4
I
H

2 3
J
 Old Graph New Graph
Choose {A} to start

B 4 C
4 B 4 C
2 1 4
2 1
A 4 E
1 F A 4 E F
1
D 2 3
10 D 2 3
G 5 10
G 5
5 6 3
5 6 3
4
I 4
H I
3 H
2 J
2 3
J
 Old Graph New Graph
{A,D}

B 4 C
4 B 4 C
2 1 4
2 1
A 4 E
1 F A 4 E F
1
D 2 3
10 D 2 3
G 5 10
G 5
5 6 3
5 6 3
4
I 4
H I
3 H
2 J
2 3
J
 Old Graph New Graph
{A,B,D}

B 4 C
4 B 4 C
2 1 4
2 1
A 4 E
1 F A 4 E F
1
D 2 3
10 D 2 3
G 5 10
G 5
5 6 3
5 6 3
4
I 4
H I
3 H
2 J
2 3
J
 Old Graph New Graph
{A,B,C,D}

B 4 C
4 B 4 C
2 1 4
2 1
A 4 E
1 F A 4 E F
1
D 2 3
10 D 2 3
G 5 10
G 5
5 6 3
5 6 3
4
I 4
H I
3 H
2 J
2 3
J
 Old Graph New Graph
{A,B,C,D,F}

B 4 C
4 B 4 C
2 1 4
2 1
A 4 E
1 F A 4 E F
1
D 2 3
10 D 2 3
G 5 10
G 5
5 6 3
5 6 3
4
I 4
H I
3 H
2 J
2 3
J
 Old Graph New Graph
{A,B,C,D,E,F}

B 4 C
4 B 4 C
2 1 4
2 1
A 4 E
1 F A 4 E F
1
D 2 3
10 D 2 3
G 5 10
G 5
5 6 3
5 6 3
4
I 4
H I
3 H
2 J
2 3
J
 Old Graph New Graph
{A,B,C,D,E,F,G}

B 4 C
4 B 4 C
2 1 4
2 1
A 4 E
1 F A 4 E F
1
D 2 3
10 D 2 3
G 5 10
G 5
5 6 3
5 6 3
4
I 4
H I
3 H
2 J
2 3
J
 Old Graph New Graph
{A,B,C,D,E,F,G,I}

B 4 C
4 B 4 C
2 1 4
2 1
A 4 E
1 F A 4 E F
1
D 2 3
10 D 2 3
G 5 10
G 5
5 6 3
5 6 3
4
I 4
H I
3 H
2 J
2 3
J
 Old Graph New Graph
{A,B,C,D,E,F,G,I,J}

B 4 C
4 B 4 C
2 1 4
2 1
A 4 E
1 F A 4 E F
1
D 2 3
10 D 2 3
G 5 10
G 5
5 6 3
5 6 3
4
I 4
H I
3 H
2 J
2 3
J
 Old Graph New Graph
{A,B,C,D,E,F,G,H,I,J}

B 4 C
4 B 4 C
2 1 4
2 1
A 4 E
1 F A 4 E F
1
D 2 3
10 D 2 3
G 5 10
G 5
5 6 3
5 6 3
4
I 4
H I
3 H
2 J
2 3
J
 Complete Graph Minimum Spanning Tree
Cost=1+4+4+2+1+2+3+3+2=22

B 4 C
4 B 4 C
2 1 4
2 1
A 4 E
1 F A E F
1
D 2 3
10 D 2
G 5
G
5 6 3
3
4
I
H I
3 H
2 J
2 3
J
 Prim’s Algorithm
 Uses a priority queue Q to find a light edge quickly.
 Each object in Q is a vertex in V - VA.

Min-heap as a binary
tree. 1 11

2 14 3 13

4 18 5 17 6 19 7 20

8 18 9 24 26 10
 Analysis of Prim's Algorithm

Running Time = O(m + n log n) (m = edges, n = nodes)

If a heap is not used, the run time will be O(n^2) instead of

O(m + n log n). However, using a heap complicates the code since
you’re complicating the data structure. A Fibonacci heap is the best kind
of heap to use, but again, it complicates the code.

Unlike Kruskal’s, it doesn’t need to see all of the graph at once. It can
deal with it one piece at a time. It also doesn’t need to worry if adding
an edge will create a cycle since this algorithm deals primarily with the
nodes, and not the edges.
 Prim’s Algorithm Text Book Example
Construct the minimum spanning tree (MST) for the given graph using
Prim’s Algorithm
 Prim’s Algorithm Text Book Example
Step-01: Step-04:

Step-02: Cost of Minimum Spanning Tree

= Sum of all edge weights
Step-05: = 10 + 25 + 22 + 12 + 16 + 14
= 99 units

Step-03:
Step-06: