UNIT – IV

Greedy method: General method, applications-Job sequencing with

deadlines, knapsack problem, Minimum cost spanning trees, Single
source shortest path problem. Basic Traversal and Search Techniques:
Techniques for Binary Trees, Techniques for Graphs, Connected
components, Biconnected components.

Greedy method
Most problems in greedy algorithms involve N inputs, and our objective is to
find a feasible (subset) solution that satisfies a given condition and optimizes
our goal. A solution that satisfies the condition given in the problem is called
a feasible solution.
General method
All greedy problems have n inputs. They work in stages by using a selection
procedure to arrange the inputs in a specific order and process them one at a
time. At each stage, a decision is made regarding whether a particular input
should be included in the optimal solution. If adding the next input to the
partially constructed optimal solution results in an infeasible solution, the
input is not added; otherwise, it is included.
Algorithm Greedy (a,n)
{
solution =0; //Initialise the solution.
for i=1 to n do
{
x=select(a);
if(feasible(solution,x))then
solution=union(solution,x);
}
return solution;
}
Feasible is a Boolean-valued function that determines whether X can be
included in the solution vector. The function Union combines X with the
solution and updates the objective function. A greedy algorithm will work
correctly once a particular problem is chosen and the functions Subset,
Feasible, and Union are properly implemented.
Applications-
Job sequencing with deadlines,
knapsack problem,
Minimum cost spanning trees,
Single source shortest path problem.
Knapsack problem

Algorithm for Knapsack Problem

Algorithm GreedyKnapsack( m , n )
{
for i = 1 to n do
x[i] = 0.0;
U = m;
for i = 1 to n do
{
if( w[i] > U ) then break
x[i] = 1.0;
U = U-w[i];
}
If(i <= n) then
x[i] = U/w[i];
}

Time complexity =O(nlogn)

The solution in row 3 gives the maximum profit and is therefore the optimal
solution.

SPANNING TREES:
A spanning tree of a graph G is a subgraph that includes all the vertices of
G with the minimum possible number of edges.
 A spanning tree has no cycles and cannot be disconnected.
 If a graph has n vertices, then each spanning tree will have n vertices
and n−1edges.
Minimum Spanning Tree : The spanning tree with smallest weight is called
minimum spanning tree.
 1. Kruskal’s Algorithm
 Kruskal’s Algorithm is a famous greedy algorithm.
 It is used to find the Minimum Spanning Tree (MST) of a given graph.
 To apply Kruskal’s algorithm, the graph must be weighted, connected,
and undirected.
Kruskal’s Algorithm Implementation
The implementation of Kruskal’s Algorithm is explained in the following steps:
1. Sort all the edges in increasing order of their weights (from low weight
to high weight).
2. Take the edge with the lowest weight and use it to connect the vertices
of the graph. If adding an edge creates a cycle, reject that edge and
move to the next edge with the least weight.
3. Continue adding edges until all the vertices are connected, and a
Minimum Spanning Tree (MST) is obtained.
4. If there are n vertices in the graph, the resulting spanning tree will have
n vertices and n−1 edges.

Time complexity: O(E logE) or O(V logV)

Example: Construct the minimum spanning tree (MST) for the given graph
using Kruskal’s Algorithm

Solution: This graph contains 7 vertices, so the resulting spanning tree will
have 6 edges.
Step1: Sort all the edges in increasing order of their weights (from low weight
to high weight).

Step 2: The first edge in the sorted list, i.e., (1, 6), which has the least cost,
is included in the spanning tree.
Then, the vertices 1 and 6 are merged into a single set.
Step 3: The next edge in the sorted list, i.e., (3, 4), which has the least cost,
is included in the spanning tree.
Then, the vertices 3 and 4 are merged into a single set.

Step 4: The next edge in the sorted list, i.e., (2, 7), which has the least cost,
is included in the spanning tree.
Then, the vertices 2 and 7 are merged into a single set.

Step 5: The next edge in the sorted list, i.e., (2, 3), which has the least cost,
is included in the spanning tree.
Then, the vertices 2 and 3 are merged into a single set.
Step 6: The next edge in the sorted list, i.e., (4, 7), which has the least cost,
is included in the spanning tree. However, adding this edge creates a cycle,
so it is rejected, and the next least weight edge is considered.

Step 7: The next edge in the sorted list, i.e., (4, 5), which has the least cost,
is included in the spanning tree.
Then, the vertices 4 and 5 are merged into a single set.

Step 8: The next edge in the sorted list, i.e., (5, 7), which has the least cost,
is included in the spanning tree. However, adding this edge creates a cycle,
so it is rejected, and the next least weight edge is considered.
Step 9: The next edge in the sorted list, i.e., (5, 6), which has the least cost,
is included in the spanning tree.
Then, the vertices 5 and 6 are merged into a single set.
 2. Prim’s Algorithm
 Prim’s Algorithm is a famous greedy algorithm.
 It is used to find the Minimum Spanning Tree (MST) of a given graph.
 To apply Prim’s Algorithm, the given graph must be weighted,
connected, and undirected.
Prim’s Algorithm Implementation
The implementation of Prim’s Algorithm is explained in the following steps:
1. Randomly choose any vertex. The vertex connecting to the edge with the
least weight is usually selected.
2. Find the smallest edge connecting the tree to a new vertex. If it forms a
cycle, reject it and try the next smallest edge.
3. Keep repeating step 2 until all the vertices are included and the
Minimum Spanning Tree (MST) is obtained.
4. If there are n vertices in the graph, each spanning tree will have n
vertices and n−1 edges.

Time complexity=O((n+ |E|) logn)

Solution: This graph contains 7 vertices, so the resulting spanning tree will
have 6 edges.
Step 1: The starting node is 6. The possible edges from node 6 that can be
added to the minimum spanning tree 'S' are (6, 1) and (6, 5). The costs of
these edges are 10 and 25, respectively. Since the edge (6, 1) has the lowest
cost among the possible edges, it is included in the tree 'S'.

Step 2: The nodes included in the tree S are 6 and 1. The possible edges from
these nodes that can be added to the minimum spanning tree 'S' are (1, 2)
and (6, 5). The costs of these edges are 28 and 25, respectively. Since the edge
(6, 5) has the lowest cost among the possible edges, it is included in the tree
'S'.

Step 3: The nodes included in tree S are 1, 6, and 5. The possible edges from
these nodes that can be added to the minimum spanning tree 'S' are (1, 2),
(5, 4), and (5, 7). The costs of these edges are 28, 22, and 24, respectively.
Since the edge (5, 4) has the lowest cost among the possible edges, it is
included in the tree 'S'.
Step 4: The nodes included in tree S are 1, 6, 5, and 4. The possible edges
from these nodes that can be added to the minimum spanning tree 'S' are (1,
2), (5, 7), (4, 3), and (4, 7). The costs of these edges are 28, 24, 12, and 18,
respectively. Since the edge (4, 3) has the lowest cost among the possible
edges, it is included in the tree 'S'.

Step 5: The nodes included in tree S are 1, 6, 5, 4, and 3. The possible edges
from these nodes that can be added to the minimum spanning tree 'S' are (1,
2), (5, 7), (4, 7), and (3, 2). The costs of these edges are 28, 24, 18, and 16,
respectively. Since the edge (3, 2) has the lowest cost among the possible
edges, it is included in the tree 'S'.

Step 6: The nodes included in tree S are 1, 6, 5, 4, 3, and 2. The possible

edges from these nodes that can be added to the minimum spanning tree 'S'
are (1, 2), (5, 7), (4, 7), and (2, 7). The costs of these edges are 28, 24, 18, and
14, respectively. Since the edge (2, 7) has the lowest cost among the possible
edges, it is included in the tree 'S'.
 Single source shortest path problem.
It is used to find the shortest path from source node to destination
node in graph.
1.Set the source vertex distance to zero and all others to infinity.
2.Make the source node the current node and add all other nodes
to the unvisited list.
3.For each neighbor of the current node, calculate the tentative
distance and update it if it’s smaller than the current value.
4.Once all neighbors are checked, mark the current node as visited
and remove it from the unvisited list. Select the unvisited node
with the smallest distance and repeat.
5.Stop when the destination is reached or the unvisited list is
empty.
Time complexity: O((n+ |E|) logn)
 Job Sequencing with Deadlines
The sequencing of jobs on a single processor with deadline
constraints is called as Job Sequencing with Deadlines.
Here-
You are given a set of jobs.
Each job has a specific deadline and an associated profit.
The profit from a job is earned only if the job is completed within
its deadline.
Only one processor is available to process all the jobs.
The processor takes exactly one unit of time to complete a job.
Our goal is to complete all or few jobs with max profit.
Algorithm steps:
S1: Arrange all the jobs in decreasing order based on their profit.
S2: Select the first job and execute it by assigning a slot.
S3: If a job deadline is r, then execute a job by assigning a slot
(r,r-1)

Applications:
Job scheduling to a processor
Flight landing or takeoff at an airport
Car repair at a workshop

The maximum deadline is 2. A maximum of two jobs will form a feasible

solution. Therefore, draw a Gantt chart with a maximum time of 2 units, as
shown.
S.No. ASSIGNED JOB ACTION PROFIT
SLOT SELECTED

1 None J1 [1,2] 100

2 [1,2] J4 [0,1] 100 =27=127

3 [0,1], [1,2] J3 REJECT 127

4 [0,1], [1,2] J2 REJECT 127

The optimal solution is J={1,4} with a profit of 127

Basic Traversal and Search Techniques:

Techniques for Binary Trees:

A binary tree is a hierarchical data structure where each node has at most
two children, called the left child and right child. It starts with a root node
and branches into left and right subtrees. Nodes with no children are called
leaf nodes. Common types include full, complete, perfect, and skewed binary
trees. It is widely used in searching, sorting, and hierarchical data
representation.
We have three traversal techniques for a binary tree:
  In-order
 Post-order
 Pre-order
In-order Traversal (Left → Root → Right)
 Visit the left subtree first.
 Visit the root node.
 Visit the right subtree.
 Example: For a tree with root A and left child B, right child C, the
traversal order is B, A, C.
 Use Case: Retrieves nodes in sorted order for binary search trees.

Pre-order Traversal (Root → Left → Right)

 Visit the root node first.
 Visit the left subtree.
 Visit the right subtree.
 Example: For the same tree, the traversal order is A, B, C.
 Use Case: Used to create a copy of the tree or evaluate prefix
expressions.
Post-order Traversal (Left → Right → Root)
 Visit the left subtree first.
 Visit the right subtree.
 Visit the root node.
 Example: For the same tree, the traversal order is B, C, A.
 Use Case: Useful for deleting a tree or evaluating postfix expressions.
Graph: A graph represents a sequence of edges that connect two vertices.
A graph is defined as a pair (V, E), where:
 V: A set of nodes, called vertices.
 E: A collection (which may include duplicates) of pairs of vertices,
called edges.
Vertices and edges are data structures that can store additional elements.
Types of Graphs: Graphs are generally categorized into three main types:
1. Undirected Graphs: Edges have no direction.
2. Directed Graphs (Digraphs): Edges have a direction from one vertex
to another.
3. Weighted Graphs: Edges have weights (numeric values) associated
with them.
 Techniques for Graphs:
The process of traversing all the nodes or vertices in a graph is called graph
traversal.”
We have two traversal techniques for graphs:
 DFS (Depth First Search)
 BFS (Breadth First Search)
Depth First Search (DFS)
DFS explores each possible path to its conclusion before trying another path.
In other words, it goes as far as possible along a branch (if no unvisited nodes
are left, it backtracks) and then tries another branch. This process is often
referred to as backtracking.
Steps for DFS:
1. Select an unvisited node v, visit it, and treat it as the current node.
 2. Find an unvisited neighbor of the current node, visit it, and make it the
new current node.
3. If the current node has no unvisited neighbors, backtrack to its parent
and make the parent the new current node.
4. Repeat steps 2 and 3 until no more nodes can be visited.
5. Repeat step 1 for any remaining unvisited nodes.

Implementation of DFS
Example 2:
 Breadth First Search
Breadth First Search (BFS) is one of the simplest algorithms for searching or
visiting each vertex in a graph. In this method, each node at the same level is
checked before the search proceeds to the next level. BFS uses a queue to
store visited vertices, expanding the path from the earliest visited vertices.
Steps for BFS:
1. Mark all the vertices as unvisited.
2. Choose any vertex, say ‘v’. Mark it as visited and add it to the end of the
queue.
3. For each vertex in the queue, examine all vertices adjacent to ‘v’ in the
same order.
4. Mark all unvisited vertices adjacent to ‘v’ as visited and add them to the
rear of the queue.
5. Remove the vertex at the front of the queue and repeat this procedure.
6. Continue this process until the queue is empty.
Example 2:
 Connected components
If G is a connected, undirected graph, then all vertices of the graph can be
visited in the first call to BFS. The subgraph obtained after traversing the
graph using BFS represents the connected component of the graph.

Thus, BFS can be used to determine whether G is connected. All the newly
visited vertices during a call to BFS represent the vertices in the connected
component of graph G. The subgraph formed by these vertices constitutes the
connected component.
 Biconnected components
A graph G is biconnected, iff (if and only if) it contains no articulation point
(joint or junction). A vertex v in a connected graph G is an articulation point,
if and only if (iff) the deletion of vertex v together with all edges incident to v
disconnects the graph into two or more none empty components.

The presence of articulation points in a connected graph can be an

undesirable (un wanted) feature in many cases.
Key Concepts:
1. Articulation Points:
o Vertices whose removal increases the number of connected
components.
o Found using DFS and tracking discovery times and low values.
2. Bridges:
o Edges whose removal increases the number of connected
components.
Algorithm (Using DFS):
1. Perform a DFS on the graph.
2. For each vertex v, compute:
o Discovery Time (disc[v]): Time when v is first visited.
o Low Value (low[v]): The lowest discovery time reachable from v.

Applications:
 Network reliability analysis.
 Fault-tolerant systems.
 Identifying critical infrastructure points.