Chapter Three

Greedy Algorithms

What is Greedy Algorithm?

• A greedy algorithm always makes the choice that looks best at the moment.
• Greedy algorithms do not always yield optimal solutions, but for many problems they do.
• The greedy method is quite powerful and works well for a wide range of problems.
• Greedy algorithms build up a solution piece by piece, always choosing the next piece that
offers the most obvious and immediate benefit.
• Although such an approach can be disastrous for some computational tasks, there are
many for which it is optimal.

Greedy method

 Is one of the strategies we can use to solve problems.

 Like divide and conquer and other strategies we can use this approach to solve different
problems (it is a design we can adopt to solve similar problems like in other strategies).
 Is used for solving optimization problems.
 Optimization problems are problems which requires either a minimum result or
maximum result.

Example: -If you want to go from place A to place B (A->B). You can have different
solutions.

1. You can go by walking

2. You can use bicycle
3. You can use car
4. You can use plane
5. You can use train
6. etc…

1
  But there are constraints/conditions that you have to obey. Suppose you have to get to
place B with in 6 hrs.
 Suppose if you use walking, bicycle and car you will need more than 6 hrs. but, if you
use plane or train you can get there with in 6 hrs.
 So, using plane or train is a feasible solutions for this problem.
 What if I want to get to place B with minimum cost too. In this case, suppose using train
will cost less than using plane. Therefore, using train will be the optimal
solution.(minimization problem)

Disadvantages:

 They do not always work.

 Short term choices may be disastrous on the long term.
 Correctness is hard to prove

Advantages:

 When they work, they work fast

 Simple and easy to implement

General Characteristic of Greedy Algorithms In Computer Science, a Greedy Algorithm is a method

used to solve optimization problems by making the best possible choice at each step. The algorithm
always selects the locally optimal solution, hoping it will lead to the globally optimal solution.

Greedy algorithms are commonly used in problems such as minimum spanning trees, shortest paths,
and scheduling.

1. Greedy Choice Property

The Greedy Choice Property means that at every step the algorithm chooses the best available
option immediately, without considering the future consequences.

Once the choice is made, the algorithm does not reconsider it later.

Example

Consider selecting edges while building a Minimum Spanning Tree.

2
Suppose we have the following edges with weights:

Edge Weight
A–B 2
A–C 5
B–C 1

The greedy strategy is to select the smallest weight edge first.

Steps:

1. Choose B–C (weight = 1)

2. Choose A–B (weight = 2)

These choices produce the minimum spanning tree.

This principle is used in Kruskal's Algorithm and Prim's Algorithm.

2. Optimal Substructure

A problem has optimal substructure if the optimal solution to the problem can be constructed
from optimal solutions of its smaller subproblems.

This means that solving smaller parts of the problem optimally helps build the overall optimal
solution.

Example

In the shortest path problem, the shortest path from A to C through B consists of:

 The shortest path from A to B

 The shortest path from B to C

This concept is used in Dijkstra's Algorithm.

Example graph:

A ----5---- B ----3---- C

Shortest path from A to C:

A→B→C
Total cost = 5 + 3 = 8

The path A → B and B → C are optimal sub-solutions.

3. Local Optimal Choice

3
Greedy algorithms make a locally optimal choice at each step.
A locally optimal solution means the best choice available at that moment.

The algorithm assumes that these local choices will lead to the best global solution.

Example

Coin change problem:

Suppose we want to make 37 using coins 25, 10, 5, 1.

Steps:

1. Choose 25 (largest possible coin)

2. Remaining = 12
3. Choose 10
4. Remaining = 2
5. Choose 1 + 1

Result:

25 + 10 + 1 + 1 = 37

The algorithm always chooses the largest possible coin first.

4. Irreversible Decisions

In greedy algorithms, once a decision is made, it cannot be changed later.

There is no backtracking and the algorithm does not reconsider earlier choices.

This makes greedy algorithms faster compared to other methods such as Backtracking or Dynamic
Programming.

Example

In Kruskal's Algorithm, once an edge is added to the minimum spanning tree, it cannot be
removed later.

Steps:

1. Select smallest edge

2. Add it to the tree
3. Move to the next smallest edge

The algorithm never goes back to remove previously selected edges unless they form a cycle.

4
5. Efficiency

Greedy algorithms are generally:

 Simple to understand
 Easy to implement
 Fast in execution

They usually have lower time complexity compared to other algorithms.

Example

For building a Minimum Spanning Tree:

 Prim's Algorithm
 Kruskal's Algorithm

These algorithms efficiently solve the problem with time complexity around:

O(E log V)

Where:

 E = number of edges
 V = number of vertices

Summary

Characteristic Description
Greedy Choice Property Choose best option at each step
Optimal Substructure Optimal solution built from subproblems
Local Optimal Choice Best choice at the current step
Irreversible Decisions Decisions cannot be changed
Efficiency Simple, fast, easy to implement

5
3.1. Graph Minimum Spanning Tree (MST) - Kruskal’s and Prims’s Algorithms

What is Minimum Spanning Tree (MST)

A minimum spanning tree (MST) is defined as a spanning tree that has the minimum weight
among all the possible spanning trees

A spanning tree is defined as a tree-like subgraph of a connected, undirected graph that includes
all the vertices of the graph. Or, to say in Layman’s words, it is a subset of the edges of the graph
that forms a tree (acyclic) where every node of the graph is a part of the tree.

The minimum spanning tree has all the properties of a spanning tree with an added constraint of
having the minimum possible weights among all possible spanning trees. Like a spanning tree,
there can also be many possible MSTs for a graph.

Properties of a Spanning Tree:

The spanning tree holds the below-mentioned principles:

6
  The number of vertices (V) in the graph and the spanning tree is the same.
 There is a fixed number of edges in the spanning tree which is equal to one less than the
total number of vertices ( E = V-1 ).
 The spanning tree should not be disconnected, as in there should only be a single source
of component, not more than that.
 The spanning tree should be acyclic, which means there would not be any cycle in the
tree.
 The total cost (or weight) of the spanning tree is defined as the sum of the edge weights
of all the edges of the spanning tree.
 There can be many possible spanning trees for a graph.

A minimum spanning tree (MST) is defined as a spanning tree that has the minimum weight
among all the possible spanning trees.

The minimum spanning tree has all the properties of a spanning tree with an added constraint of
having the minimum possible weights among all possible spanning trees. Like a spanning tree,
there can also be many possible MSTs for a graph.

 Let’s look at the MST of the above example Graph,

7
Minimum Spanning Tree

Kruskal’s Minimum Spanning Tree (MST) Algorithm

A minimum spanning tree (MST) or minimum weight spanning tree for a weighted, connected,
undirected graph is a spanning tree with a weight less than or equal to the weight of every other
spanning tree.

Introduction to Kruskal’s Algorithm:

Here we will discuss Kruskal’s algorithm to find the MST of a given weighted graph.

In Kruskal’s algorithm, sort all edges of the given graph in increasing order. Then it keeps on
adding new edges and nodes in the MST if the newly added edge does not form a cycle. It picks
the minimum weighted edge at first at the maximum weighted edge at last. Thus we can say that
it makes a locally optimal choice in each step in order to find the optimal solution. Hence this is
a Greedy Algorithm.

How to find MST using Kruskal’s algorithm?

Below are the steps for finding MST using Kruskal’s algorithm:

1. Sort all the edges in non-decreasing order of their weight.

2. Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far. If
the cycle is not formed, include this edge. Else, discard it.
3. Repeat step#2 until there are (V-1) edges in the spanning tree.

Kruskal’s algorithm to find the minimum cost spanning tree uses the greedy approach. The
Greedy Choice is to pick the smallest weight edge that does not cause a cycle in the MST
constructed so far. Let us understand it with an example:

Below is the illustration of the above approach:

Input Graph:

8
The graph contains 9 vertices and 14 edges. So, the minimum spanning tree formed will be
having (9 – 1) = 8 edges.
After sorting:

Weight Source Destination

1 7 6
2 8 2
2 6 5
4 0 1
4 2 5
6 8 6
7 2 3
7 7 8
8 0 7
8 1 2
9 3 4
10 5 4
11 1 7
14 3 5

Now pick all edges one by one from the sorted list of edges

9
Step 1: Pick edge 7-6. No cycle is formed, include it.

Add edge 7-6 in the MST

Step 2: Pick edge 8-2. No cycle is formed, include it.

10
Add edge 8-2 in the MST

Step 3: Pick edge 6-5. No cycle is formed, include it.

Add edge 6-5 in the MST

Step 4: Pick edge 0-1. No cycle is formed, include it.

11
Add edge 0-1 in the MST

Step 5: Pick edge 2-5. No cycle is formed, include it.

Add edge 2-5 in the MST

Step 6: Pick edge 8-6. Since including this edge results in the cycle, discard it. Pick edge 2-3: No
cycle is formed, include it.

12
Add edge 2-3 in the MST

Step 7: Pick edge 7-8. Since including this edge results in the cycle, discard it. Pick edge 0-7. No
cycle is formed, include it.

Add edge 0-7 in MST

Step 8: Pick edge 1-2. Since including this edge results in the cycle, discard it. Pick edge 3-4. No
cycle is formed, include it.

13
Add edge 3-4 in the MST

Note: Since the number of edges included in the MST equals to (V – 1), so the algorithm stops
here

Prim’s Minimum Spanning Tree Algorithm:

This is also a greedy algorithm. This algorithm has the following workflow:

 It starts by selecting an arbitrary vertex and then adding it to the MST.

 Then, it repeatedly checks for the minimum edge weight that connects one vertex of MST
to another vertex that is not yet in the MST.
 This process is continued until all the vertices are included in the MST.

To efficiently select the minimum weight edge for each iteration, this algorithm uses
priority_queue to store the vertices sorted by their minimum edge weight currently. It also
simultaneously keeps track of the MST using an array or other data structure suitable considering
the data type it is storing.

This algorithm can be used in various scenarios such as image segmentation based on color,
texture, or other features. For Routing, as in finding the shortest path between two points for a
delivery truck to follow.
14
Follow the article on “Prim’s Minimum Spanning Tree Algorithm” for a better understanding
and implementation of this algorithm.

Prim’s Algorithm for Minimum Spanning Tree (MST)

Introduction to Prim’s algorithm:

We have discussed Kruskal’s algorithm for Minimum Spanning Tree. Like Kruskal’s algorithm,
Prim’s algorithm is also a Greedy algorithm. This algorithm always starts with a single node and
moves through several adjacent nodes, in order to explore all of the connected edges along the
way.

The algorithm starts with an empty spanning tree. The idea is to maintain two sets of vertices.
The first set contains the vertices already included in the MST, and the other set contains the
vertices not yet included. At every step, it considers all the edges that connect the two sets and
picks the minimum weight edge from these edges. After picking the edge, it moves the other
endpoint of the edge to the set containing MST.

A group of edges that connects two sets of vertices in a graph is called cut in graph theory. So, at
every step of Prim’s algorithm, find a cut, pick the minimum weight edge from the cut, and
include this vertex in MST Set (the set that contains already included vertices).

How does Prim’s Algorithm Work?

The working of Prim’s algorithm can be described by using the following steps:

Step 1: Determine an arbitrary vertex as the starting vertex of the MST.

Step 2: Follow steps 3 to 5 till there are vertices that are not included in the MST (known as
fringe vertex).
Step 3: Find edges connecting any tree vertex with the fringe vertices.
Step 4: Find the minimum among these edges.
Step 5: Add the chosen edge to the MST if it does not form any cycle.
Step 6: Return the MST and exit

15
Note: For determining a cycle, we can divide the vertices into two sets [one set contains the
vertices included in MST and the other contains the fringe vertices.]

Prim’s Algorithm:

Consider the following graph as an example for which we need to find the Minimum Spanning
Tree (MST).

Example of a graph

Step 1: Firstly, we select an arbitrary vertex that acts as the starting vertex of the Minimum
Spanning Tree. Here we have selected vertex 0 as the starting vertex.

16
0 is selected as starting vertex

Step 2: All the edges connecting the incomplete MST and other vertices are the edges {0, 1} and
{0, 7}. Between these two the edge with minimum weight is {0, 1}. So include the edge and
vertex 1 in the MST.

1 is added to the MST

Step 3: The edges connecting the incomplete MST to other vertices are {0, 7}, {1, 7} and {1,
2}. Among these edges the minimum weight is 8 which is of the edges {0, 7} and {1, 2}. Let us
here include the edge {0, 7} and the vertex 7 in the MST. [We could have also included edge {1,
2} and vertex 2 in the MST].

17
7 is added in the MST

Step 4: The edges that connect the incomplete MST with the fringe vertices are {1, 2}, {7, 6}
and {7, 8}. Add the edge {7, 6} and the vertex 6 in the MST as it has the least weight (i.e., 1).

6 is added in the MST

18
Step 5: The connecting edges now are {7, 8}, {1, 2}, {6, 8} and {6, 5}. Include edge {6, 5} and
vertex 5 in the MST as the edge has the minimum weight (i.e., 2) among them.

Include vertex 5 in the MST

Step 6: Among the current connecting edges, the edge {5, 2} has the minimum weight. So
include that edge and the vertex 2 in the MST.

19
Include vertex 2 in the MST

Step 7: The connecting edges between the incomplete MST and the other edges are {2, 8}, {2,
3}, {5, 3} and {5, 4}. The edge with minimum weight is edge {2, 8} which has weight 2. So
include this edge and the vertex 8 in the MST.

Add vertex 8 in the MST

Step 8: See here that the edges {7, 8} and {2, 3} both have same weight which are minimum.
But 7 is already part of MST. So we will consider the edge {2, 3} and include that edge and
vertex 3 in the MST.

20
Include vertex 3 in MST

Step 9: Only the vertex 4 remains to be included. The minimum weighted edge from the
incomplete MST to 4 is {3, 4}.

Include vertex 4 in the MST

The final structure of the MST is as follows and the weight of the edges of the MST is (4 + 8 + 1
+ 2 + 4 + 2 + 7 + 9) = 37.

21
The structure of the MST formed using the above method

Note: If we had selected the edge {1, 2} in the third step then the MST would look like the
following.

Structure of the alternate MST if we had selected edge {1, 2} in the MST

22
 How to implement Prim’s Algorithm?

Follow the given steps to utilize the Prim’s Algorithm mentioned above for finding MST of a
graph:

 Create a set mstSet that keeps track of vertices already included in MST.
 Assign a key value to all vertices in the input graph. Initialize all key values as
INFINITE. Assign the key value as 0 for the first vertex so that it is picked first.
 While mstSet doesn’t include all vertices
o Pick a vertex u that is not there in mstSet and has a minimum key value.
o Include u in the mstSet.
o Update the key value of all adjacent vertices of u. To update the key values,
iterate through all adjacent vertices.
 For every adjacent vertex v, if the weight of edge u-v is less than the
previous key value of v, update the key value as the weight of u-v.

The idea of using key values is to pick the minimum weight edge from the cut. The key values
are used only for vertices that are not yet included in MST, the key value for these vertices
indicates the minimum weight edges connecting them to the set of vertices included in MST.

3.3 Shortest Paths

In Computer Science, the Shortest Path Problem is the problem of finding the minimum distance
between two vertices in a graph.

It is widely used in network routing, maps, transportation systems, and communication networks.

A common greedy algorithm used to solve this problem is Dijkstra's Algorithm.

3.4 Scheduling

Scheduling problems involve allocating tasks to resources or time slots [Link] Computer
Science, greedy algorithms are often used for Job Scheduling with Deadlines. The objective is to
maximize profit while completing jobs before their deadlines.

Job Scheduling Problem

Each job has:

23
  Deadline → latest time by which job must be completed
 Profit → reward obtained after completing the job

Goal:
Select jobs such that maximum profit is earned and no deadline is violated.

Greedy Strategy

1. Sort all jobs in decreasing order of profit.

2. Select the job with highest profit first.
3. Assign it to the latest available time slot before its deadline.
4. Continue until all jobs are scheduled or slots are full.

Example
Job Deadline Profit
J1 2 100
J2 1 19
J3 2 27
J4 1 25
J5 3 15

Step 1: Sort jobs by profit

Job Deadline Profit
J1 2 100
J3 2 27
J4 1 25
J2 1 19
J5 3 15

Step 2: Assign jobs to slots

Available slots: 1, 2, 3

 Place J1 in slot 2
 Place J3 in slot 1
 Place J5 in slot 3

Final schedule:

Time Slot Job

1 J3
2 J1
3 J5

24
Total Profit
27 + 100 + 15 = 142
Topic Algorithm
Shortest Path Dijkstra’s Algorithm
Scheduling Job Scheduling with Deadlines
Both problems use the greedy strategy of making the best choice at each step to achieve an
optimal result.

Greedy Strategy

Choose the activity that finishes earliest.

Algorithm Steps

1. Sort all activities according to their finish time.

2. Select the first activity.
3. For the remaining activities:
o If the start time ≥ finish time of last selected activity, select it.
4. Repeat until all activities are checked.

Example

Activity Start Finish

A1 1 4
A2 3 5
A3 0 6
A4 5 7
A5 8 9

After sorting by finish time:

A1(1,4), A2(3,5), A3(0,6), A4(5,7), A5(8,9)

Selected activities:

A1 → A4 → A5

These activities do not overlap and give the maximum number of activities.

Time Complexity

O(n log n) (because of sorting)

2. Job Sequencing with Deadlines

Definition

25
In this problem, each job has:

 Deadline
 Profit

Each job takes 1 unit of time to complete.

Goal: Schedule jobs to maximize total profit while completing jobs before their deadlines.

Example

Job Deadline Profit

J1 2 100
J2 1 19
J3 2 27
J4 1 25
J5 3 15

Sorted by profit:

J1(100), J3(27), J4(25), J2(19), J5(15)

Schedule:

Time Slot Job

1 J3
2 J1
3 J5

Total Profit = 100 + 27 + 15 = 142

26