UNIT – II

Greedy Programming: General Method, Knapsack problem, Job Sequencing with Dead Lines,
Minimum-cost Spanning Tree - Prim's and Kruskal's algorithms, Single-Source Shortest Paths-
Dijkstra's Algorithm.
Basic Traversal & Search Techniques: Techniques for Binary Trees, Techniques for Graphs,
Connected Components and Spanning Trees, Bi-Connected Components and DFS.

Greedy Programming
General Method:
Most of the problems in Greedy method have n inputs and require us to obtain a subset that
satisfy some constraints. Any subset that satisfies these constraints is called a feasible solution.
A feasible solution that either maximizes or minimizes a given objective function is called an
optimal solution. If the problem requires that only a subset of n inputs need to be selected
for its solution, then that type of problem can be solved by using greedy method “subset
paradigm”. If the problem requires that all of n inputs need to be selected for its solution but the
order of input is important, then that type of problems can be solved by using Greedy technique
“ordering paradigm”.
Characteristics of Greedy technique:
• Solution is built in stages at each stage. One of the input will be selected and will test for
feasibility, If that selected input is feasible then it will be included in the solution.
• The solution returned by the Greedy algorithms may not be an optimal solution.
• The decision that are made in the earlier stages are fixed and can’t be changed in next
stage.
Control abstraction of subset paradigm for Greedy method:
Algorithm Greedy(a, n)
{
//a[1:n] contains n inputs
solution:=ɸ
for i:=1 to n do
{
x:=select(a);
If (Feasible (solution, x)) then
solution:=Union(solution,x);
}
return solution;
}

Knapsack Problem:
Given n objects and a knapsack or bag, object ‘i’ has a weight wi and profit pi. The knapsack has
a capacity ‘m’. If a fraction x is 0 ≤ xi ≤ 1 of object ‘i’ is placed in knapsack, then profit pi xi is
obtained.
The objective is to obtain a filling of the knapsack that maximizes the total profit earned.
i.e. Maximize ∑1≤𝑖≤𝑛 𝑝𝑖𝑥𝑖→ (1)
Subject to ∑1≤𝑖≤𝑛 𝑤𝑖𝑥𝑖 ≤ 𝑚→ (2), where 0 ≤ x i≤ 1, 1 ≤ i≤ n → (3)
A feasible solution is any set (x1, x2… xn) satisfying the above constraints (2) and (3). An
optimal solution is a feasible solution that maximizes (1)
Problem:
1. Consider the following instance of the knapsack problem n=3, m=20, (p1, p2, p3)=(25, 24,
15) and (w1, w2, w3)=(18,15,10).
Sol: Some possible Solution sets:
1. Select according to ascending order of weights.
(0, 10/15, 1) 25*0+24*(2/3)+15*1=31
2. Select according to descending order of profit.
(1, 2/15, 0) 25*1+24*(2/15)+15*0=28.2
3. Randomly selected objects.
(1/2, 1/3, 6/10) 25*(1/2)+(1/3)*24+15*(6/10)=29.5
4. Select objects in decreasing order of profit/weight ratio.
(0, 1, 5/10) 25*0+24*1+15*(1/2)=31.5

2. Consider the following instance of the knapsack problem n=7,m=15, (p1,p2…p7) = (10, 5,
15, 7, 6, 18, 3) and (w1, w2…w7)=(2,3,5,7,1,4,1).
Sol: arrange the object in decreasing order of profit/weight ratio.
𝑝/𝑤 = (10/2, 5/3,15/5,7/7,6/1,18/4,3/1)=(5, 1.67, 3, 1, 6, 4.5, 3)
Solution set x[ ]= (1, 2/3, 1, 0, 1, 1, 1)
Total Profit obtained = 1*10+(2/3)*5+15*1+7*0+6*1+18*1+3*1
= 10+(10/3)+15+0+6+18+3
= 55.3

Algorithm:
Algorithm knapsack(m, n)
{
//p[1:n] are profits and w[1:n] are weights of n objects
//the objects are given in decreasing order of pro
//x[1:n] is the solution set
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];
}

Implementation:
#include<stdio.h>
int main(){
int n, m, i, j, t;
int p[100],w[100];
printf("Enter size: ");
scanf("%d",&n);
printf("Enter maximum capacity: ");
scanf("%d",&m);
printf("Enter the profits: ");
for(i=0;i<n;i++)
scanf("%d",&p[i]);
printf("Enter the weights: ");
for(i=0;i<n;i++)
scanf("%d",&w[i]);
for(i=0;i<n;i++) {
for(j=0;j<n-i-1;j++) {
float t1 = (float) p[j]/w[j];
float t2 = (float) p[j+1]/w[j+1];
if(t1<t2) {
t=w[j];
w[j]=w[j+1];
w[j+1]=t;
t=p[j];
p[j]=p[j+1];
p[j+1]=t;
}
}
}
float result[100];
for(i=0;i<n;i++)
result[i]=0;
float profit = 0;
for (i = 0; i < n; i++) {
if (w[i] > m)
break;
result[i] = 1;
m = m - w[i];
profit += p[i];
}
if (i <= n) {
result[i] = (float) m / w[i];

profit += p[i] * result[i];

}
printf("\nTotal profit = %.2f",profit);
}
Time complexity: by assuming that the objects are available in the decreasing order of their
profit per unit weight, the time complexity for the greedy knapsack problem is O(n)

Job Sequencing with Deadlines:

Given n jobs where each job i is associated with tuple (pi, di). Here pi is the profit of job i, di is
the deadline of job i. Profit pi will obtained only if the job i is completed by its deadline. The
objective of this problem is to find an optimal sequence of jobs such that the total profit is as
maximum as possible and all the jobs in the sequence selected are executed by their deadlines.
The assumptions of JSD are:
1. Every job requires one unit of time for its completion
2. Only one machine is available to execute the set of jobs.
Problems:
1. Find the optimal sequence of jobs to be executed on a machine for the following
instance of job sequencing with deadlines: n=4, (p1, p2, p3, p4)=(100, 10, 15, 20) and (d1, d2,
d3, d4)=(2, 1, 2, 1).
Sol:
Feasible solution Processing sequence profit
1, 2 2, 1 110
1,3 1, 3 or 3, 1 115
1, 4 4, 1 120
2, 3 2, 3 25
2, 4 Not possible --
3, 4 4, 3 35
We get optimal solution by arranging the jobs in non-increasing order of profits.

2. Find the optimal sequence of jobs to be executed on a machine from the following instance of
job sequencing with deadlines n=5, (p1, p2, p3, p4, p5)=(20, 15, 10, 5, 1) and (d1, d2, d3, d4,
d5)=(2, 2, 1, 3, 3).
Sol: Method of solving JSD is as follows

J Assigned slots Job consideration action profit

____ 1 Assigning to [1,2] 0

{1} [1, 2] 2 Assigning to [0,1] 20

{1, 2} [0, 1] [1, 2] 3 Cannot fit 35

{1, 2} [0, 1] [1, 2] 4 Assigning to [2,3] 35

{1, 2, 4} [0, 1] [1, 2] [2, 3] 5 Cannot fit 40

The optimal solution is getting maximum profit of 40 by doing the jobs {1, 2, 4} in the sequence
2, 1, 4.

3. Find the optimal sequence of jobs to be executed on a machine from the following instance of
job sequencing with deadlines n=4, (p1, p2…p7)=(3,5,20,18,1,6,30) and (d1, d2,... d7)=(1, 3, 4,
3, 2, 1, 2).
Sol: Arrange the objects in non-increasing order of profits
(p7, p3, p4, p6, p2, p1, p5)= (30, 20, 18, 6, 5, 3, 1)
(d7, d3, d4, d6, d2, d1, d5)= (2, 4, 3, 1, 3, 1, 2)
 J Assigned slots Job action profit
consideration
____ 7 Assign to [1, 2] 0

{7} [1, 2] 3 Assign to [3, 4] 30

{7, 3} [1, 2] [3, 4] 4 Assign to [2, 3] 50

{7, 3, 4} [1, 2] [2, 3] [3, 4] 6 Assign to [0, 1] 68

[0, 1] [1, 2] [2, 3] [3,
{7, 3, 4, 6} 4] 2 Cannot fit 68+6=74
[0, 1] [1, 2] [2, 3] [3,
{7, 3, 4, 6} 4] 1 Cannot fit 74
[0, 1] [1, 2] [2, 3] [3,
{7, 3, 4, 6} 4] 5 Cannot fit 74

Algorithm:
Algorithm JSD(d, j, n)
{
//deadlines d[i] ≥1; 1≤i≤n
//profits are arranged in non-increasing order
//p[1] ≥ p[2]….. ≥p[n]
//J[ ] is the array of jobs selected
d[0]:=J[0]:=0;
J[1]:=1;
k:=1; //k is number of jobs
for i:=2 to n do //i is job number
{
r:=k;
//look at position for job i and insert
//if feasible
while (d[J[r]]>d[i] and d[J[r]]≠r) do
r:=r-1;
if(d[J[r]) ≤d[i] and d[i]> r) then
{
for q:=k to r+1 step-1 do
J[q+1]:=J[q];
J[r+1]:=i;
k:=k+1;
}
}
return k;
}

Implementation:
#include <stdio.h>
int maxi(int a[],int n){
int i,m=a[0];
for(i=0;i<n;i++)
if(a[i]>m)
m=a[i];
return m;
}
int main()
{
int i,j,n;
printf("Enter the value of n: ");
scanf("%d",&n);
int profits[n],dead[n];
printf("Enter the profits: ");
for(i=0;i<n;i++)
scanf("%d",&profits[i]);
printf("Enter the dead lines: ");
for(i=0;i<n;i++)
scanf("%d",&dead[i]);
for(i=0;i<n;i++){
for(j=i+1;j<n;j++){
if(profits[i]<profits[j]){
int temp=profits[i];
profits[i]=profits[j];
profits[j]=temp;
temp=dead[i];
dead[i]=dead[j];
dead[j]=temp;
}
}
}
int max=maxi(dead,n);
int profit=0,w;
int visited[max];
for(i=0;i<max;i++)

visited[i]=0;
for(i=0;i<n;i++){
w=dead[i];
for(j=w-1;j>=0;j--){
if(visited[j]==0){
visited[j]=1;
profit+=profits[i];
break;
}
}
}
printf("Total Profit = %d",profit);
return 0;
}

Time complexity: O(n2)

Minimum Cost Spanning Tree:
Let G = (V,E) be an undirected connected graph. A subgraph t = (V, Eˡ) of G is a spanning tree iff
t is a tree and │Eˡ│ = │V│-1

The cost of spanning tree is the sum of costs (or) weights of the edges in tree. The minimum cost
spanning tree(MCSP) is the spanning tree whose sum of costs (or) weights of the edges in tree is
minimum for the given undirected connected graph.
There are two basic algorithms for finding minimum-cost spanning trees, and both are greedy
algorithms
• Prim‟s Algorithm
• Kruskal‟s Algorithm

Prim’s Algorithm:
i) Select an edge with minimum cost and include in to the spanning tree.
ii) Among all the edges which are adjacent with the selected edge, select the one with minimum
cost.
iii) Repeat step 2 until „n‟ vertices and (n-1) edges are been included. And the sub graph
obtained does not contain any cycles.
Example:
Algorithm:
Algorithm Prim (E, cost, n, t)
{
Let (k, l) be an edge of minimum cost in E;
mincost := cost [k, l];
t [1, 1] := k; t [1, 2] := l;
for i :=1 to n do // Initialize near
if (cost [i, l] < cost [i, k]) then near [i] := l;
else near [i] := k;
near [k] :=near [l] := 0;
for i:=2 to n - 1 do // Find n - 2 additional edges for t.
{
Let j be an index such that near [j] <> 0 and cost [j, near [j]] is minimum;
t [i, 1] := j; t [i, 2] := near [j];
mincost := mincost + cost [j, near [j]];
near [j] := 0
for k:= 1 to n do // Update near[].
if ((near[k] <> 0) and (cost [k, near [k]] > cost [k, j]))
then near [k] := j;
}
return mincost;
}

Implementation:
#include<stdio.h>
#define INF 9999999
int main() {
int no_edge,V,cost=0,i,j;
int selected[V];
printf("Enter number of edges: ");
scanf("%d",&V);
int G[V][V];
printf("Enter the adjacency matrix:\n");
for(i=0;i<V;i++)
for(j=0;j<V;j++)
scanf("%d",&G[i][j]);
for(i=0;i<V;i++)
selected[i]=0;
no_edge = 0;
selected[0] = 1;
int x;
int y;
printf("Edge : Weight\n");
while (no_edge < V - 1) {
int min = INF;
x = 0;
y = 0;
for (int i = 0; i < V; i++) {
if (selected[i]) {
for (int j = 0; j < V; j++) {
if (!selected[j] && G[i][j]){
if (min > G[i][j]) {
min = G[i][j];
x = i;
y = j;
}
}
}
}
}
printf("%d - %d : %d\n", x, y, G[x][y]);

cost+=G[x][y];
selected[y] = 1;
no_edge++;
}
printf("Minimum Cost = %d",cost);
return 0;
}

Kruskal’s Algorithm:
The algorithm also uses greedy method to get the minimum spanning tree.
Initially all the edges are arranged in the non-decreasing order, based on the cost of the edges. At
each stage an edge with the minimum cost is selected following the constraint that selection of
this edge does not result in a cycle(or)loop.
Procedure:
Step 1: Initially arrange the edges of a graph in the non-decreasing order of their cost .
Step 2: Select the minimum cost edge and it is going to be first edge in the spanning tree.
Step 3: Now select the minimum cost edge from the remaining edges following the constraint
that the selection of that edge does not result in cycle or loop
Step 4: If more than one edge has the same minimum cost then arbitrarily select any one of them
Step 5: repeat step3 until there are n-1 edges in the spanning tree.

Example:
Algorithm:
Algorithm krushkal(E,cost,n,t)
{
//E is the set of edges in G of 'n' vertices
//cost [ , ] is cost adjacency matrix
//t is set of edges in the minimum cost
//spanning tree.
Construct a heap out of edge costs using heapify;
for i:=1 to n do parent[i]:= -1;
i:=0;
mincost:=0;
while (i<n-1 and (heap is not empty))
{
Delete a mininum cost edge (u,v) from the heap and
heapify using adjust;
j:=find(u);
k:=find(v);
if (j≠k) then
{
i:=i+1;
t[i,1]:=u;
t[i,2]:=v;
mincost:=mincost+cost[u,v];
union(j,k);
}
}
if (i<n-1) then
Write ("No spanning tree");
else
return mincost;
}

Algorithm find(i) Algorithm union(i,j)

{{
while(parent[i]≠-1) parent[i]:=j;
{
i:=parent[i]; }
}
return i;
}
Implementation:
#include<stdio.h>
int i,j,k,a,b,u,v,n,ne=1;
int min,mincost=0,cost[9][9],parent[9];
int find(int i){
while(parent[i])
i=parent[i];
return i;
}
int uni(int i,int j){
if(i!=j){
parent[j]=i;
return 1;
}
return 0;
}
int main(){
printf("\nEnter the no. of vertices: ");
scanf("%d",&n);
printf("\nEnter the cost adjacency matrix:\n");
for(i=0;i<n;i++)
for(j=0;j<n;j++){
scanf("%d",&cost[i][j]);
if(cost[i][j]==0)
cost[i][j]=999;

}
printf("Edge : Cost\n");
while(ne<n){
for(i=0,min=999;i<n;i++){
for(j=0;j<n;j++){
if(cost[i][j]<min){
min=cost[i][j];
a=u=i;
b=v=j;
}
}
}
u=find(u);
v=find(v);
if(uni(u,v)){
printf("%d - %d : %d\n", a, b, min);
mincost +=min;
}
ne++;
cost[a][b]=cost[b][a]=999;
}
printf("Minimum cost = %d",mincost);
return 0;
}
Performance:
To build min-heap with edges : O(|E|)
Iterate through edges for cycle detection and deleteMin to get next edge : O(|E| log |E|)
We can do Union in constant time.
We can get Find with worst case O(log (|V|)

Kruskal's and Prim’s Algorithm Time Complexity

Single Source Shortest Path(Dijkstra’s Algorithm):

Definition: Given a weighted directed graph G=(V,E,cost) and source vertex 'v', the objective of
this problem is to find the shortest path from the given source vertex to every other vertex in the
graph.
Example:

Path length

1-2 10

1-5-4-3 26

1-5-4 20

1-5 5

Procedure:
• Let 'v' be the source vertex and cost[ ] be the 2-dimentional array of edge cost,
distance[i] is the distance of each vertex i from source vertex 'v'.
• Select the vertex which has the minimum distance value among unvisited vertices and
declare it as visited. Let that vertex be 'u'.
• Update the distance[i] values of adjacent unvisited vertices of vertex u by using the
following condition:
 • Let 'w' be an adjacent vertex of 'u',
• if (distance[w] > distance[u]+cost[u,w]) distance [w]= distance[u]+cost[u,w])
• Repeat steps 2,3 until all the vertices are declared as visited.

Problems:
1. Find the shortest paths from source vertex 'A' to each vertex in the graph

Sol:

Iteration S(already selected set) Selected vertex dist[……….]

A B C D E F G

initial − A 0 1 2 ∞ ∞ ∞ 3
1 A B 0 1 2 5 ∞ ∞ 3
2 {A,B} C 0 1 2 5 5 3 3
3 {A,B,C} F 0 1 2 5 5 3 3
4 {A,B,C,F} G 0 1 2 5 5 3 3
5 {A,B,C,F,G} E 0 1 2 5 5 3 3
6 {A,B,C,E,F,G} D 0 1 2 5 5 3 3

2. Solve shortest path problem

Given source vertex is 'E'.

 Sol:

Iteration S(already selected Selecte d dist[……]

set) vertex A B C D E F G H

Initial − E ∞ ∞ ∞ 15 0 2 ∞ ∞
1 {E} F ∞ ∞ ∞ 12 0 2 11 16
2 {E,F} G ∞ ∞ ∞ 12 0 2 11 16
3 {E,F,G} D ∞ ∞ 24 12 0 2 11 16
4 {D,E,F,G} H 33 ∞ 24 12 0 2 11 16
5 { D,E,F,G,H} C 33 32 24 12 0 2 11 16
6 {C, D,E,F,G,H } B 33 32 24 12 0 2 11 16
7 {B,C, D,E,F,G,H} A 33 32 24 12 0 2 11 16

Algorithm:
Algorithm shortestpath (v,cost,dist,n)
{
//dist[j],1≤j≤n is set to the length of
//shortest path from source vertex v to vertex j
//in a digraph G with 'n' vertices. G is represented
//by cost adjacency matrix C[1:n,1:n] for i:=1 to n do
{
S[i]:=false; dist[i]:=cost[v,i];
}
S[v]:=true;
dist[v]:=0.0;
for num:= 2 to n-1 do
{
Choose u from among the vertices not in S, such that dist[u] is minimum;
S[u]:=true;
for (each w adjacent to u with S[w]=false) do
{
if(dist[w]>dist[u]+cost[u,w]) then dist[w]:=dist[u]+cost[u,w];
}
}
}

Implementation:
#include<stdio.h>
#include<string.h>
#define INF 9999999
int minCost(int cost[],int visited[],int v){
int min=INF;
 int mi=0;
for(int i=0;i<v;i++){
if(cost[i]<min && !visited[i]){
min=cost[i];
mi=i;
}
}
return mi;
}
int main() {
int no_edge,V,i,j;
printf("Enter number of edges: ");
scanf("%d",&V);
int visited[V];
memset(visited,0,V*sizeof(int));
int G[V][V];
int cost[V];
memset(cost,INF,V*sizeof(int));
printf("Enter the adjacency matrix:\n");
for(i=0;i<V;i++)
for(j=0;j<V;j++)
scanf("%d",&G[i][j]);
no_edge = 0;
cost[0] = 0;
while (no_edge < V - 1){
int u=minCost(cost,visited,V);
visited[u]=1;
for (i = 0; i < V; i++)
if (G[u][i] && cost[u]+G[u][i]<cost[i] && !visited[i])
cost[i]=cost[u]+G[u][i];
no_edge++;
}
printf("Vertex Cost\n");
for(i=0;i<V;i++)
printf("%d %d\n",i+1,cost[i]);
return 0;
}

Time Complexity: O(n2 ), n = |V|

Basic Traversal & Search Techniques

Techniques for Binary Trees:

• Examining every node in the given data object instance is referred to as traversal
methods. these techniques are applicable to binary trees.
• In case of graphs, search methods may not examine all vertices. These techniques are
applicable to graphs.
• During traversal or search the fields of a node may be used several times.
• Visiting a node may involve printing out its data field, evaluating the operation specified
by the node, setting a mark bit to one or zero, and so on.
Tree Traversals:
• A traversal produces a linear order for the information in a tree.
• When traversing a binary tree, we want to treat each node and its subtrees in the same
fashion. If we let L, D, and R stand for moving left, printing the data, and moving right
when at a node.
• The tree traversal techniques are in-order (LDR), post-order(LRD), pre-order(DLR)

Example:

In-order Traversal: F D H G I B E A C
• Pre-order Traversal: A B D F G H I E C
• Post-order Traversal: F H I G D E B C A
• The total time taken to the above
three algorithms are 𝑂(𝑛)
Tree Construction
• Inorder sequence: D B E A F C
• Preorder sequence: A B D E C F
• Inorder sequence: D B E A F C
• Postorder sequence: D E B F C A
Note:
• In-order and post-order sequences of a binary tree uniquely define the binary tree.
• In-order and pre-order sequences of a binary tree uniquely define the binary tree.
• Post-order and pre-order sequences of a binary tree do not uniquely define the binary
tree.

Techniques for Graphs:

• A fundamental problem concerning graphs is the reachability problem. In its simplest
form it requires us to determine whether there exists a path in the given graph G=(V, E)
such that this path starts at vertex v and ends at vertex u.
• Starting at vertex v and systematically searching the graph G for vertices that can be
reached from v. We describe two search methods for this
• Breadth First Search (BFS)
• Depth Frist Search (DFS)
Breadth First Search (BFS)
• Start at vertex v and mark it as visited.
• The vertex v is at this time said to be unexplored. A vertex is said to have been explored by an
algorithm when the algorithm has visited all vertices adjacent from it.
• All unvisited vertices adjacent from v are visited next. These are new unexplored vertices.
Vertex v has now been explored.
• The newly visited vertices haven’t been explored and are put onto the end of a list of
unexplored vertices. The first vertex on this list is the next to be explored.
• Exploration continues until no unexplored vertex is left. The list of unexplored vertices
operates as a queue and can be represented using any of the standard queue representation.
• BFS uses Queue data structure.
Complexity Analysis
• If adjacency lists are used, then all vertices adjacent from u can be determined in time d(u),
where d(u) is the degree of u if G is undirected and d(u) is the out-degree of u if G is directed.
The time for line 11 is O(d(u)). The total time of line 9 is O(∑𝑑(𝑢)) = 𝑂(𝑒). Therefore, the total
time taken is O(n+e).
• If adjacency matrices are used the total needed is O(n2).
• If BFS is used on a connected undirected graph G, then all vertices in G get visited and the
graph is traversed. However, if G is not connected, then at least one vertex of G is not visited.
Depth First Search (DFS)
• A depth first search of a graph differs from a breadth first search in that the exploration of a
vertex 𝑣 is suspended as soon as a new vertex is reached.
• At this time the exploration of the new vertex 𝑢 begins. When this new vertex has been
explored, the exploration of 𝑣 continues.
• The search terminates when all reached vertices have been fully explored.
• DFS uses Stack data structure.
Complexity Analysis
• If adjacency lists are used, then all vertices adjacent from u can be determined in time d(u),
where d(u) is the degree of u if G is undirected and d(u) is the out-degree of u if G is directed.
The time for line 11 is O(d(u)). The total time of line 9 is O(∑𝑑(𝑢)) = 𝑂(𝑒). Therefore, the total
time taken is O(n+e).
• If adjacency matrices are used the total needed is O(n2).
• If BFS is used on a connected undirected graph G, then all vertices in G get visited and the
graph is traversed. However, if G is not connected, then at least one vertex of G is not visited
Example:

Implementation of BFS & DFS:

#include <stdio.h>
#define MAX 4
void breadth_first_search(int adj[][MAX],int visited[],int start){
int queue[MAX],rear = -1,front = -1, i;
queue[++rear] = start;
visited[start] = 1;
while(rear != front){
start = queue[++front];
if(start == 4)
printf("-E- ");
else
printf("-%c-",start + 65);
for(i = 0; i < MAX; i++){
if(adj[start][i] == 1 && visited[i] == 0){
queue[++rear] = i;
visited[i] = 1;
}
}
}
}
void depth_first_search(int adj[][MAX],int visited[],int start){
int stack[MAX];
int top = -1, i;
printf("--%c-",start + 65);
visited[start] = 1;
stack[++top] = start;
while(top != -1){
start = stack[top];
for(i = 0; i < MAX; i++){
if(adj[start][i] == 1 && visited[i] == 0){
stack[++top] = i;
printf("-%c–", i + 65);
visited[i] = 1;
break;
}
}
if(i == MAX)
top--;
}
}
int main(){
int visited[MAX] = {0};
int adj[MAX][MAX], i, j;
printf("Enter the Adjacency Matrix\n");
for(i = 0; i < MAX; i++)
for(j = 0; j < MAX; j++)
scanf("%d", &adj[i][j]);
printf("\nBFS Traversal of Given Adjacency Matrix is:");
breadth_first_search(adj,visited,0);
int visited2[MAX] = {0};
printf("\nDFS Traversal of Given Adjacency Matrix is:");
depth_first_search(adj,visited2,0);
return 0;
}

Connected Components and Spanning Trees

Basic Definitions:
A graph can be defined as a group of vertices and edges to connect these vertices. The types of
graphs are given as follows -
o Undirected graph: An undirected graph is a graph in which all the edges do not point to
any particular direction, i.e., they are not unidirectional; they are bidirectional. It can
also be defined as a graph with a set of V vertices and a set of E edges, each edge
connecting two different vertices.
o Connected graph: A connected graph is a graph in which a path always exists from a
vertex to any other vertex. A graph is connected if we can reach any vertex from any
other vertex by following edges in either direction.
o Directed graph: Directed graphs are also known as digraphs. A graph is a directed graph
(or digraph) if all the edges present between any vertices or nodes of the graph are
directed or have a defined direction.
• If G is a connected undirected graph, then all vertices of G will get visited on the first call to
BFS. If G is not connected, then at least two calls to BFS will be needed.
• Hence BFS can be used to determine whether G is connected. The connected components of a
graph can be obtained using BFT. If adjacency lists are used, a BFT will obtain the connected
components in 𝑂(𝑛+𝑒).
• BFT can also be used to obtain the reflexive transitive closure matrix of an undirected graph G.
If A* is this matrix, then A*(i, j)=1 iff either i=j or i≠j and i and j are in the same connected
component. The reflexive transitive closure matrix of an undirected graph G with n vertices and
e edges can be computed in O(n2).
• As a final application of BFS, the graph G has a spanning tree iff G is connected. Hence, BFS
easily determines the existence of spanning tree. Spanning trees obtained by using a BFS are
called breadth first spanning trees.
• DFT is also be used to find connected components, reflexive transitive closure matrix and
spanning trees. A spanning tree obtained by using DFT is called a depth first spanning tree.

Bi-Connected Components and DFS

• A vertex v in a connected graph G is an articulation point if and only if the deletion of
vertex v together will all edges incident to v disconnects the graph into two or more
nonempty components.

• A graph G is biconnected if and only if it contains no articulation points.

• The presence of articulation points in a connected graph can be an undesirable feature
in many cases.
• For example, if G represents a communication network with the vertices representing
communication stations and the edges communication lines, then the failure of a
communication station 𝑖 that is an articulation point would result in the loss of
communication to points other than 𝑖 too.
• On the other hand, if 𝐺 has no articulation point, then if any station 𝑖 fails, we can still
communicate between every two stations not including station 𝑖.
• A maximal bi-connected subgraph is a bi-connected component.
 Not Bi-connected Graph Bi-connected Graph

*There are 0 articulation points in a two biconnected components.

Finding Articulation Points

• The root node of a depth first spanning tree is an articulation point iff it has at least two
children
• If u is any other vertex, then it is not an articulation point iff from every child w of u it is
possible to reach an ancestor of u using only a path made up of descendents of w and a back
edge.
• If this cannot be done for some child w of it, then u is an articulation point.
• This observation leads to a simple rule to identify articulation points. For each vertex u, define
L[u] as follows:
L[u] = min {dfn[u],min {L[w] | w is a child of u}, min {dfn[w] | (u, w) is a back edge}}
• If u is not the root, then it is an articulation point iff it has a child w such that L[w] >= dfn[u].

Example:

8
6
1 7 5
1
2
4 6 2 7 9

3 3 8 1

4 1 9 5
Algorithm for finding Articulation Points
Algorithm Art(u, v)
//It is assumed that the global array dfn is initialized to zero
//global variable num is initialized to 1. n is the number of vertices in G.
{
dfn[u] := num; L[u] := num; num := num + 1;
for each vertex w adjacent from u do
{
if (dfn[w] = 0) then
{
Art(w,u); // w is unvisited.
L[u] := min(L[u], L[w]);
}
else if (w != v) then L[u] := min(L[u],dfn[w]);
}
}
Algorithm for finding bi-connected components:
Algorithm BiComp (u, v)
{
dfn [u] := num; L[u] := num; num := num + 1;
for each vertex w adjacent from u do
{
if ((v != w) and (dfn [w] < dfn [u])) then
add (u, w) to the top of a stack s;
if (dfn [w] = 0) then
{
BiComp (w, u); // w is unvisited.
L [u] := min (L [u], L [w]);
if (L [w] >= dfn [u]) then
{
write (“New bicomponent”);
repeat {
Delete an edge from the top of stack s;
Let this edge be (x, y);
Write (x, y);
} until (((x, y) = (u, w)) or ((x, y) = (w, u)));
}
}
else if (w != v) then L [u] : = min (L [u], dfn [w]);
}
}

***