Chapter 5

Greedy Algorithms
Saurabh Mishra, PhD

Note : Slides summarize key points. Complete understanding will come from classroom discussion, worked examples, and textbook reading.
Content
• Introduction to greedy algorithms
• Fractional Knapsack problem
• Minimum Spanning Trees
• Prim’s algorithm
• Kruskal’s algorithm
• Single source shortest path algorithm
• Dijkstra’s algorithm
• Huffman coding.
Greedy Algorithm

A greedy algorithm always makes the choice that looks

best at the moment. That is, it makes a locally optimal
choice in the hope that this choice will lead to a
globally optimal solution.
Fractional Knapsack

“In fractional knapsack, we act like a smart investor, we

invest first where return per unit weight is highest.”
Fractional Knapsack Problem Example
Object Weight Profit
Wheat 7 21
Mazie 5 10
Barley 2 14
Rice 9 18
Chickpea 3 15
Fractional Knapsack Problem
• Step 1: Compute Profit/Weight Ratio
• Step 2: Sort by Ratio (Descending)
• Step 3: Fill the Knapsack
• Final Profit
Fractional Knapsack Problem
FractionalKnapsack(items, W): 4. For each item in sorted order
if item weight ≤ W
1. For each item take full item
compute ratio = profit / W = W - weight
weight totalProfit += profit
2. Sort items in descending else
order of ratio take fraction W / weight
totalProfit += profit * (W /
3. totalProfit = 0 weight)
break
5. return totalProfit
Fractional Knapsack Problem
• Time Complexity
• Sorting → O(n log n)
• Filling → O(n)
• Overall:
𝑂 𝑛 log 𝑛
Ask Yourself
• Greedy Algorithm Features
• Knapsack Problem
• 0/1 vs fractional knapsack
Solve Fractional Knapsack Problem
For the given set of items and the knapsack capacity of 33 kg, find the subset of
the items to be added in the knapsack such that the profit is maximum.

Object Weight Profit

P 18 99
Q 13 78
R 16 48
S 9 113.5
T 7 49
U 17 153
V 19 76
Graphs (review)
Definition. A directed graph (digraph) G = (V, E) is an ordered pair
consisting of
• a set V of vertices (singular: vertex),
• a set E ⊆ V × V of edges.

In an undirected graph G = (V, E), the edge set E consists of unordered

pairs of vertices. In either case, we have |E| = O(V 2). Moreover, if G is
connected, then |E| ≥ |V| – 1, which implies that lg |E| = Θ(lgV).
Adjacency-matrix representation
Adjacency-list representation
Minimum spanning trees
Input: A connected, undirected graph G = (V, E) with weight function
w : E → R.
• For simplicity, assume that all edge weights are distinct.

Output: A spanning tree T — a tree that connects all vertices of

minimum weight:
𝑊(𝑇) = ෍ 𝑊(𝑢, 𝑣)
(𝑢,𝑣)∈𝑇
Example of MST
Example of MST
 Optimal substructure
MST T: u
(Other edges of G
are not shown.) v
 Optimal substructure
MST T: u
(Other edges of G
are not shown.) v
Remove any edge (u, v) ∈ T.
 Optimal substructure
MST T: u
(Other edges of G T1
are not shown.) v
T2
Remove any edge (u, v) ∈ T. Then, T is partitioned into two
subtrees T1 and T2.
Theorem. The subtree T1 is an MST of G1 = (V1, E1), the subgraph of G
induced by the vertices of T1:
V1 = vertices of T1,
E1 = { (x, y) ∈ E : x, y ∈ V1 }.
Similarly for T2.
Proof of theorem
Properties of Minimum Spanning Trees
• Minimum spanning tree is not unique. If two or more edges
have same weight.

• MST will be unique, if all edges have different weights.

• MST has no cycles – see why:
• We can take out an edge of a cycle, and still have the vertices
connected while reducing the cost

• # of edges in a MST:
• |V| - 1 22
Prim Algorithm
Example of Prim’s algorithm
∈A ∞
6 12
∈V–A
∞ 5 ∞ 9 ∞
14 7
8

∞ ∞ 15 ∞
3 10
∞
Example of Prim’s algorithm
∈A ∞
6 12
∈V–A
∞ 5 ∞ 9 ∞
14 7
8

∞ 0 15 ∞
3 10
∞
Example of Prim’s algorithm
∈A ∞
6 12
∈V–A
∞ 5 7 9 ∞

14 7
8

∞ 0 15 15
3 10
10
Example of Prim’s algorithm
∈A ∞
6 12
∈V–A
∞ 5 7 9 ∞

14 7
8

∞ 0 15 15
3 10
10
Example of Prim’s algorithm
∈A 12
6 12
∈V–A
5 5 7 9 9

14 7
8

∞ 0 15 15
3 10
10
Example of Prim’s algorithm
∈A 12
6 12
∈V–A
5 5 7 9 9

14 7
8

∞ 0 15 15
3 10
10
Example of Prim’s algorithm
∈A 12
6 12
∈V–A
5 5 7 9 9

14 7
8

∞ 0 15 15
3 10
10
Example of Prim’s algorithm
∈A 6
6 12
∈V–A
5 5 7 9 9

14 7
8
14 0 15 15
3 10
8
Example of Prim’s algorithm
∈A 6
6 12
∈V–A
5 5 7 9 9

14 7
8
14 0 15 15
3 10
8
Example of Prim’s algorithm
∈A 6
6 12
∈V–A
5 5 7 9 9

14 7
8
14 0 15 15
3 10
8
Example of Prim’s algorithm
∈A 6
6 12
∈V–A
5 5 7 9 9

14 7
8
14 0 15 15
3 10
8
Example of Prim’s algorithm
∈A 6
6 12
∈V–A
5 5 7 9 9

14 7
8
3 0 15 15
3 10
8
Example of Prim’s algorithm
∈A 6
6 12
∈V–A
5 5 7 9 9

14 7
8
3 0 15 15
3 10
8
Example of Prim’s algorithm
∈A 6
6 12
∈V–A
5 5 7 9 9

14 7
8
3 0 15 15
3 10
8
Example of Prim’s algorithm
∈A 6
6 12
∈V–A
5 5 7 9 9

14 7
8
3 0 15 15
3 10
8
Example of Prim’s algorithm
∈A 6
6
∈V–A
5 5 7 9 9

7
8
3 0 15 15
3
8
Analysis of Prim Algorithm
Analysis of Prim Algorithm
Analysis of Prim Algorithm
Analysis of Prim Algorithm
Analysis of Prim Algorithm
Analysis of Prim Algorithm
Analysis of Prim Algorithm
Analysis of Prim Algorithm
Prim’s Algorithm
• Prim’s algorithm is a “greedy” algorithm
• Greedy algorithms find solutions based on a sequence of choices which
are “locally” optimal at each step.

• Nevertheless, Prim’s greedy strategy produces a globally

optimum solution!

50
Kruskal Algorithm
A different instance of the generic approach
S
(instance 1)

(instance 2)
u

v tree1
V-S

• A is a forest containing connected

components u
• Initially, each component is a single
vertex
v
• Any safe edge merges two of tree2
these components into one
• Each component is a tree 52
Kruskal’s Algorithm
• How is it different from Prim’s algorithm?

• Prim’s algorithm grows one tree all the time

• Kruskal’s algorithm grows multiple trees (i.e., a forest)

at the same time.
tree1

• Trees are merged together using safe edges

u
• Since an MST has exactly |V| - 1
edges, after |V| - 1 merges,
we would have only one component v
tree2
53
Kruskal’s Algorithm
• Start with each vertex being its own component
• Repeatedly merge two components into one by 8 7
choosing the light edge that connects them b c d
4 9
2
• Which components to consider at each iteration? a 11 i 14 e
4
• Scan the set of edges in monotonically increasing order 8
7 6
10
by weight h g f
1 2

We would add
edge (c, f)

54
Example
1. Add (h, g) {g, h}, {a}, {b}, {c}, {d}, {e}, {f}, {i}
8 7
b c d 2. Add (c, i) {g, h}, {c, i}, {a}, {b}, {d}, {e}, {f}
4 9
2 3. Add (g, f) {g, h, f}, {c, i}, {a}, {b}, {d}, {e}
a 11 i 4 14 e 4. Add (a, b) {g, h, f}, {c, i}, {a, b}, {d}, {e}
7 6 5. Add (c, f) {g, h, f, c, i}, {a, b}, {d}, {e}
8 10
h g f 6. Ignore (i, g) {g, h, f, c, i}, {a, b}, {d}, {e}
1 2
7. Add (c, d) {g, h, f, c, i, d}, {a, b}, {e}
1: (h, g) 8: (a, h), (b, c) 8. Ignore (i, h) {g, h, f, c, i, d}, {a, b}, {e}
2: (c, i), (g, f) 9: (d, e) 9. Add (a, h) {g, h, f, c, i, d, a, b}, {e}
4: (a, b), (c, f) 10: (e, f) 10. Ignore (b, c) {g, h, f, c, i, d, a, b}, {e}
6: (i, g) 11: (b, h) 11. Add (d, e) {g, h, f, c, i, d, a, b, e}
7: (c, d), (i, h) 14: (d, f) 12. Ignore (e, f) {g, h, f, c, i, d, a, b, e}

13. Ignore (b, h) {g, h, f, c, i, d, a, b, e}

{a}, {b}, {c}, {d}, {e}, {f}, {g}, {h}, {i}
14. Ignore (d, f) {g, h, f, c, i, d, a, b, e}
Example
1. Add (h, g) {g, h}, {a}, {b}, {c}, {d}, {e}, {f}, {i}
8 7
b c d 2. Add (c, i) {g, h}, {c, i}, {a}, {b}, {d}, {e}, {f}
4 9
2 3. Add (g, f) {g, h, f}, {c, i}, {a}, {b}, {d}, {e}
a 11 i 4 14 e 4. Add (a, b) {g, h, f}, {c, i}, {a, b}, {d}, {e}
7 6 5. Add (c, f) {g, h, f, c, i}, {a, b}, {d}, {e}
8 10
h g f 6. Ignore (i, g) {g, h, f, c, i}, {a, b}, {d}, {e}
1 2
7. Add (c, d) {g, h, f, c, i, d}, {a, b}, {e}
1: (h, g) 8: (a, h), (b, c) 8. Ignore (i, h) {g, h, f, c, i, d}, {a, b}, {e}
2: (c, i), (g, f) 9: (d, e) 9. Add (a, h) {g, h, f, c, i, d, a, b}, {e}
4: (a, b), (c, f) 10: (e, f) 10. Ignore (b, c) {g, h, f, c, i, d, a, b}, {e}
6: (i, g) 11: (b, h) 11. Add (d, e) {g, h, f, c, i, d, a, b, e}
7: (c, d), (i, h) 14: (d, f) 12. Ignore (e, f) {g, h, f, c, i, d, a, b, e}

13. Ignore (b, h) {g, h, f, c, i, d, a, b, e}

{a}, {b}, {c}, {d}, {e}, {f}, {g}, {h}, {i}
14. Ignore (d, f) {g, h, f, c, i, d, a, b, e}
Kruskal’s Algorithm

• Kruskal’s algorithm is a “greedy” algorithm

• Kruskal’s greedy strategy produces a globally optimum solution

• Proof for generic approach applies to Kruskal’s S

x
algorithm too
u y

v
V-S
57
Implementation of Kruskal’s Algorithm

8 7
• Uses a disjoint-set data
b c d
4 9
2
structure to determine a 11 i 4 14 e
7 6
whether an edge connects 8
h g f
10

1 2
vertices in different We would add
components edge (c, f)

58
Operations on Disjoint Data Sets
• MAKE-SET(u) – creates a new set whose only member is u
• FIND-SET(u) – returns a representative element from the set that
contains u
• Any of the elements of the set that has a particular property
• E.g.: Su = {r, s, t, u}, the property is that the element be the first one
alphabetically
FIND-SET(u) = r FIND-SET(s) = r
• FIND-SET has to return the same value for a given set

59
Operations on Disjoint Data Sets
• UNION(u, v) – unites the dynamic sets that contain u and v, say Su
and Sv
• E.g.: Su = {r, s, t, u}, Sv = {v, x, y}

UNION (u, v) = {r, s, t, u, v, x, y}

• Running time for FIND-SET and UNION depends on

implementation.

• Can be shown to be α(n)=O(lgn) where α() is a very slowly growing

function 60
Krushkal Algorithm
1. A← 
2. for each vertex v  V
3. do MAKE-SET(v)
4. sort E into non-decreasing order by w
5. for each (u, v) taken from the sorted list
6. do if FIND-SET(u)  FIND-SET(v)
7. then A ← A  {(u, v)}
8. UNION(u, v)
9. return A
61
KRUSKAL(V, E, w)
1. A← 
2. for each vertex v  V
O(V)
3. do MAKE-SET(v)
4. sort E into non-decreasing order by w O(ElgE)
5. for each (u, v) taken from the sorted list O(E)
6. do if FIND-SET(u)  FIND-SET(v)
7. then A ← A  {(u, v)}
8. UNION(u, v)
9. return A

62
KRUSKAL(V, E, w)
1. A← 
2. for each vertex v  V
O(V)
3. do MAKE-SET(v)
4. sort E into non-decreasing order by w O(ElgE)
5. for each (u, v) taken from the sorted list O(E)
6. do if FIND-SET(u)  FIND-SET(v)
7. then A ← A  {(u, v)}
O(lgV)
8. UNION(u, v)
9. return A
Running time: O(V+ElgE+ElgV)=O(ElgE) – dependent on the
implementation of the disjoint-set data structure
63
Kruskal's Minimum Spanning Tree Algorithm

2 23 3
9
1
18
14
2 6
6
30 4 19
11
14 5
5
6
20 16

7 8
44
64
Kruskal's Minimum Spanning Tree Algorithm
PQ = ( 2, 5, 6, 6, 9, 11, 14, 14, 16, 18, 19, 20, 23, 30, 44 )

2 23 3
9
1
18
14
2 6
6
30 4 19
11
14 5
5
6
20 16

7 8
44
65
Kruskal's Minimum Spanning Tree Algorithm
PQ = ( 2, 5, 6, 6, 9, 11, 14, 14, 16, 18, 19, 20, 23, 30, 44 )

2 23 3
9 PQdelmin()
1
18
14
2 6
6
30 4 19
11
5
14 5
6
20 16

7 8
44
66
Kruskal's Minimum Spanning Tree Algorithm
PQ = ( 5, 6, 6, 9, 11, 14, 14, 16, 18, 19, 20, 23, 30, 44 )

2 23 3
9
1
18
14
2 6
6
30 4 19
11
14 5
5
6
20 16

7 8
44
67
Kruskal's Minimum Spanning Tree Algorithm
PQ = ( 5, 6, 6, 9, 11, 14, 14, 16, 18, 19, 20, 23, 30, 44 )

2 23 3
9
1
18
14
2 6
6
PQdelmin() 30 4 19
11
5
14 5
6
20 16

7 8
44
68
Kruskal's Minimum Spanning Tree Algorithm
PQ = (6, 6, 9, 11, 14, 14, 16, 18, 19, 20, 23, 30, 44 )

2 23 3
9
1
18
14
2 6
6
30 4 19
11
14 5
5
6
20 16

7 8
44
69
Kruskal's Minimum Spanning Tree Algorithm
PQ = ( 6, 6, 9, 11, 14, 14, 16, 18, 19, 20, 23, 30, 44 )

2 23 3
9
1
18
14
2 6
6
30 4 19
11 PQdelmin()
14 5
5
6
20 16

7 8
44
70
Kruskal's Minimum Spanning Tree Algorithm
PQ = (6, 9, 11, 14, 14, 16, 18, 19, 20, 23, 30, 44 )

2 23 3
9
1
18
14
2 6
6
30 4 19
11
5
14 5
6
20 16

7 8
44
71
Kruskal's Minimum Spanning Tree Algorithm
PQ = ( 6, 9, 11, 14, 14, 16, 18, 19, 20, 23, 30, 44 )

2 23 3
9
1
18
14
2 6
6
30 4 19
11
5
14 5
6
20 16
PQdelmin() 8
7 44
72
Kruskal's Minimum Spanning Tree Algorithm
PQ = (9, 11, 14, 14, 16, 18, 19, 20, 23, 30, 44 )

2 23 3
9
1
18
14
2 6
6
30 4 19
11
14 5
5
6
20 16

7 8
44
73
Kruskal's Minimum Spanning Tree Algorithm
PQ = (9, 11, 14, 14, 16, 18, 19, 20, 23, 30, 44 )
PQdelmin()

2 23 3
9
1
18
14
2 6
6
30 4 19
11
14 5
5
6
20 16

7 8
44
74
Kruskal's Minimum Spanning Tree Algorithm
PQ = (11, 14, 14, 16, 18, 19, 20, 23, 30, 44 )

2 23 3
9
1
18
14
2 6
6
30 4 19
11
5
14 5
6
20 16

7 8
44
75
Kruskal's Minimum Spanning Tree Algorithm
PQ = (11, 14, 14, 16, 18, 19, 20, 23, 30, 44 )

2 23 3
9
1
18
14
2 6
6
30 4 19
11
5
14 5
6
20 PQdelmin() 16

7 8
44
76
Kruskal's Minimum Spanning Tree Algorithm
PQ = (14, 14, 16, 18, 19, 20, 23, 30, 44 )

2 23 3
9
1
18
14
2 6
6
30 4 19
11
14 5
5
6
20 16

7 8
44
77
Kruskal's Minimum Spanning Tree Algorithm
PQ = (14, 14, 16, 18, 19, 20, 23, 30, 44 )

2 23 3
9
1
18
14
2 6
6
30 4 19
11
14 5
5
6
20 16

7 8
44
78
Kruskal's Minimum Spanning Tree Algorithm
PQ = (14, 14, 16, 18, 19, 20, 23, 30, 44 )

2 23 3
9 PQdelmin()
1
18
14
2 6
6
30 4 19
11
14 5
5
6
20 16

7 8
44
79
Kruskal's Minimum Spanning Tree Algorithm
PQ = (14, 16, 18, 19, 20, 23, 30, 44 )

2 23 3
9
1
18
14
2 6
6
30 4 19
11
14 5
5
6
20 16

7 8
44
80
Kruskal's Minimum Spanning Tree Algorithm
PQ = (14, 16, 18, 19, 20, 23, 30, 44 )

2 23 3
9
1
18
14
2 6
6
30 4 19
11
5
14 5
6
20 16
PQdelmin()

7 8
44
81
Kruskal's Minimum Spanning Tree Algorithm
PQ = (16, 18, 19, 20, 23, 30, 44 )

2 23 3
9
1
18
14
2 6
6
30 4 19
11
14 5
5
6
20 16

7 8
44
82
Kruskal's Minimum Spanning Tree Algorithm
PQ = (16, 18, 19, 20, 23, 30, 44 )

2 23 3
9
1
18
14
2 6
6
30 4 19
11
5
14 5
6
20 16

7 8
44
83
Kruskal's Minimum Spanning Tree Algorithm
PQ = (16, 18, 19, 20, 23, 30, 44 )

2 23 3
9
1
18
14
2 6
6
30 4 19
11
14 5
5
6
20 16

7 8
44 PQdelmin()
84
Kruskal's Minimum Spanning Tree Algorithm
PQ = (18, 19, 20, 23, 30, 44 )

2 23 3
9
1
18
14
2 6
6
30 4 19
11
14 5
5
6
20 16

7 8
44
85
Kruskal's Minimum Spanning Tree Algorithm
PQ = (18, 19, 20, 23, 30, 44 )

2 23 3
9
1
18
14
2 6
6
30 4 19
11
14 5
5
6
20 16

7 8
44
86
Kruskal's Minimum Spanning Tree Algorithm
PQ = (18, 19, 20, 23, 30, 44 )

2 PQdelmin() 23 3
9
1
18
14
2 6
6
30 4 19
11
5
14 5
6
20 16

7 8
44
87
Kruskal's Minimum Spanning Tree Algorithm
PQ = (19, 20, 23, 30, 44 )

2 23 3
9
1
18
14
2 6
6
30 4 19
11
14 5
5
6
20 16

7 8
44
88
Kruskal's Minimum Spanning Tree Algorithm
PQ = (19, 20, 23, 30, 44 )

2 23 3
9
1
18
14
2 6
6
30 4 19
11
14 5
5
6
20 16

7 8
44
89
Kruskal's Minimum Spanning Tree Algorithm
PQ = (19, 20, 23, 30, 44 )

2 3
9
1
18
14
2 6
6
4
5
5
6

7 8
90
Ask Yourself
• Calculate Adjacency matrix and adjacency matrix for the given
weighted graph.
Ask Yourself
• What is minimum spanning tree?
• Is minimum tree unique for a given graph?
• Does minimum spanning tree provide minimum distance from one
node to any other node?
• Does minimum spanning tree provide minimum distance from one
node to all other node?
• Does minimum spanning tree provide minimum distance from root
node to any other node?
• Does minimum spanning tree provide minimum distance from any
node to all its neighboring nodes?
• Does Prim and Kruskal algorithm result into same minimum
spanning tree?
 Find Minimum Spanning Tree for the following Graph
Using Prim and Kruskal Algorithm
2
10
1 2
2 7
2
1 8
4
5 9 9
3 8
2 6
10 11
4
7 9
2
13 8
6

2 2
4 8
7
93
 Find Minimum Spanning Tree for the following
Graph Using Prim and Kruskal
10
Algorithm
2 2
12
1
5 22
1 2
6 18
4
8 1 1

5 9
10
3 16 8
4 11
2
7 6 19
18 12
2 9
13
2

2 13 27 7
14 8
17 7

94 7 6
2
Find Minimum Spanning Tree for the following
Graph Using Prim and Kruskal Algorithm
3 19
2 23 3

4
6 16
14
18 6
22
8
1 29 9
6 4
11 13
3
6 8
14
15 5
9
8
16

7 8
14
95
Next Class
• Single source shortest path algorithm
• Dijkstra’s algorithm
• Huffman coding.