Southern University Bangladesh

Department of Computer Science and Engineering

Spring 2023
DS Lab Performance 9

Lab Program 9.1:

DEPTH FIRST SEARCH

Objective:
To write a C program for implementing the traversal algorithm for Depth first traversal

Pre-Lab Discussion
Depth First Traversal (or Search) for a graph is similar to Depth First Traversal of a tree.
The only catch here is, unlike trees, graphs may contain cycles, so we may come to the same node
again. To avoid processing a node more than once, we use a boolean visited array.
For example, in the following graph, we start traversal from vertex 2. When we come to vertex 0,
we look for all adjacent vertices of it. 2 is also an adjacent vertex of 0. If we don’t mark visited
vertices, then 2 will be processed again and it will become a non-terminating process. A Depth
First Traversal of the following graph is 2, 0, 1, 3.

Algorithm:
Step 1: Start from any vertex, say Vi .
Step 2: Vi is visited and then all vertices adjacent to Vi are traversed recursively
using DFS.
Step 3: Since, a graph can have cycles. We must avoid revisiting a node. To do
this, when we visit a vertex V, we mark it visited.
Step 4: A node that has already been marked as visited should not be selected for
traversal.
Step 5: Marking of visited vertices can be done with the help of a global array
visited[ ].
Step 6: Array visited[ ] is initialized to false (0).
Page 1 of 11
Program
/*
To write a C program for implementing the traversal
algorithm for Depth
first traversal
*/

#include<stdio.h>
#include<stdlib.h>

typedef struct node

{
struct node *next;
int vertex;
} node;
node *G[20];
//heads of linked list
int visited[20];
int n;
void read_graph();
//create adjacency list
voidinsert(int,int);
//insert an edge (vi,vj) in te adjacency list
void DFS(int);
void main()
{
int i;
read_graph();
//initialised visited to 0
for(i=0; i<n; i++)

Page 2 of 11
 visited[i]=0;
DFS(0);
}
void DFS(int i)
{
node *p;
printf("\n%d",i);
p=G[i];
visited[i]=1;
while(p!=NULL)
{
i=p->vertex;
if(!visited[i])
DFS(i);
p=p->next;
}
}
void read_graph()
{
int i,vi,vj,no_of_edges;
printf("Enter number of vertices:");
scanf("%d",&n);
//initialise G[] with a null
for(i=0; i<n; i++)
{
G[i]=NULL;
//read edges and insert them in G[]
printf("Enter number of edges:");
scanf("%d",&no_of_edges);
for(i=0; i<no_of_edges; i++)
{
Page 3 of 11
 printf("Enter an edge(u,v):");
scanf("%d%d",&vi,&vj);
insert(vi,vj);
}
}
}
void insert(int vi,int vj)
{
node *p,*q;
//acquire memory for the new node
q=(node*)malloc(sizeof(node));
q->vertex=vj;
q->next=NULL;
//insert the node in the linked list numbervi
if(G[vi]==NULL)
G[vi]=q;
else
{
//go to end of the linked list
p=G[vi];
while(p->next!=NULL)
p=p->next;
p->next=q;
}
}

Page 4 of 11
Output:

VIVA (PRE & POST LAB) QUESTIONS:

1. A person wants to visit some places. He starts from a vertex and then wants to visit every
vertex till it finishes from one vertex, backtracks and then explore other vertex from same vertex.
What algorithm he should use?
2. When the Depth First Search of a graph is unique?
3. In Depth First Search, how many times a node is visited?
4. Give the applications of DFS.
5. Depth First Search is equivalent to which of the traversal in the Binary Trees?

Result:
Thus, the C program for implementing the traversal algorithm for Depth first traversal was implemented
successfully.

Page 5 of 11
Lab Program 9.2:
BREADTH FIRST SEARCH

Objective:
To write a C program for implementing the traversal algorithm for Breadth first traversal

Pre-Lab Discussion:
Breadth First Traversal (or Search) for a graph is similar to Breadth First Traversal of a tree. The only
catch here is, unlike trees, graphs may contain cycles, so we may come to the same node again. To avoid
processing a node more than once, we use a boolean visited array. For simplicity, it is assumed that all
vertices are reachable from the starting vertex. For example, in the following graph, we start traversal
from vertex 2. When we come to vertex 0, we look for all adjacent vertices of it. 2 is also an adjacent
vertex of 0. If we don’t mark visited vertices, then 2 will be processed again and it will become a non-
terminating process. A Breadth First Traversal of the following graph is 2, 0, 3, 1.

Pre-Lab Questions:
1. What is BFS
2. What is the application of BFS?
3. How does BFS work?
4. Breadth First Search is equivalent to which of the traversal in the Binary Trees?
5. What is advantages and disadvantages in BFS?

Algorithm:
Step 1: Start from any vertex, say Vi .
Step 2: Vi is visited and then all vertices adjacent to Vi are traversed recursively using BFS.
Step 3: avoid revisiting a node. To do this, when we visit a vertex V, we mark it visited.
Step 4: A node that has already been marked as visited should not be selected for traversal.
Step 5: Marking of visited vertices can be done with the help of a global array visited [ ].
Step 6: Array visited [ ] is initialized to false (0).

Page 6 of 11
Program:
/*
To write a C program for implementing the traversal
algorithm for
Breadth first traversal
*/

#include<stdio.h>
#include<stdlib.h>
#define MAX 100
#define initial 1
#define waiting 2
#define visited 3

int n;
intadj[MAX][MAX];
intstate[MAX];
void create_graph();
void BF_Traversal();
void BFS(intv);
int queue[MAX], front = -1,rear = -1;
void insert_queue(int vertex);
int delete_queue();
int isEmpty_queue();
int main()
{
create_graph();
BF_Traversal();
return 0;

Page 7 of 11
}
void BF_Traversal()
{
int v;
for(v=0; v<n; v++)
state[v] = initial;
printf("Enter Start Vertex for BFS: \n");
scanf("%d", &v);
BFS(v);
}
void BFS(int v)
{
int i;
insert_queue(v);
state[v] = waiting;
while(!isEmpty_queue())
{
v = delete_queue( );
printf("%d ",v);
state[v] =visited;
for(i=0; i<n; i++)
{
if(adj[v][i] == 1 && state[i] ==
initial)
{
insert_queue(i);
state[i] = waiting;
}
}
}
printf("\n");
Page 8 of 11
}
void insert_queue(int vertex)
{
if(rear == MAX-1)
printf("Queue Overflow\n");
else
{
if(front == -1)
front = 0;
rear = rear+1;
queue[rear] = vertex ;
}
}
int isEmpty_queue()
{
if(front == -1 || front > rear)
return 1;
else
return 0;
}
intdelete_queue()
{
intdelete_item;
if(front == -1 || front > rear)
{
printf("Queue Underflow\n");
exit(1);
}
delete_item = queue[front];
front = front+1;
return delete_item;
Page 9 of 11
}
void create_graph()
{
int count,max_edge,origin,destin;
printf("Enter number of vertices : ");
scanf("%d",&n);
max_edge = n*(n-1);
for(count=1; count<=max_edge; count++)
{
printf("Enter edge %d( -1 -1 to quit ) :
",count);
scanf("%d %d",&origin,&destin);
if((origin == -1) && (destin == -1))
break;
if(origin>=n || destin>=n || origin<0 ||
destin<0)
{
printf("Invalid edge!\n");
count--;
}
else
{
adj[origin][destin] = 1;
}
}
}

Page 10 of 11
Output:

VIVA (PRE & POST LAB) QUESTIONS:

1. Which data structure is used in standard implementation of Breadth First Search?
2. A person wants to visit some places. He starts from a vertex and then wants to visit every
1. place connected to this vertex and so on. What algorithm he should use?
2. In BFS, how many times a node is visited?
3. Regarding implementation of Breadth First Search using queues, what is the maximum
4. distance between two nodes present in the queue?
5. When the Breadth First Search of a graph is unique?

Result:
Thus, the C program for implementing the traversal algorithm for Breadth first traversal was
implemented successfully

Page 11 of 11