[go: up one dir, main page]
Scribd
Upload
38 views12 pages

12th Done

Uploaded by

Raj yadav
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
38 views12 pages

12th Done

Uploaded by

Raj yadav
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 12

EXPERIMENT NO:-12

Date of Performance:

Date of Submission:

Aim: Implement Graph Traversal techniques : a) Depth First Search (DFS) b) Breadth
First Search(BFS).

Theory:
Graph traversal is a technique used for a searching vertex in a graph. The graph traversal is also
used to decide the order of vertices is visited in the search process. A graph traversal finds the
edges to be used in the search process without creating loops. That means using graph traversal we
visit all the vertices of the graph without getting into looping path.

There are two graph traversal techniques and they are as follows.
1. DFS (Depth First Search)
2. BFS (Breadth First Search)

DFS (Depth First Search)


DFS traversal of a graph produces a spanning tree as final result. Spanning Tree is a graph
without loops. We use Stack data structure with maximum size of total number of vertices in the
graph to implement DFS traversal.

Algorithms: DFS

We use the following steps to implement DFS traversal...

• Step 1 - Define a Stack of size total number of vertices in the graph.


• Step 2 - Select any vertex as starting point for traversal. Visit that vertex and push it
on to the Stack.
• Step 3 - Visit any one of the non-visited adjacent vertices of a vertex which is at the
top of stack and push it on to the stack.
• Step 4 - Repeat step 3 until there is no new vertex to be visited from the vertex which
is at the top of the stack.
• Step 5 - When there is no new vertex to visit then use back tracking and pop one
vertex from the stack.
• Step 6 - Repeat steps 3, 4 and 5 until stack becomes Empty.
• Step 7 - When stack becomes Empty, then produce final spanning tree by removing
unused edges from the graph.

Back tracking is coming back to the vertex from which we reached the current vertex.
Example: DFS

Undirected graph with 5 vertices


We start from vertex 0, the DFS algorithm starts by putting it in the Visited list and putting all its
adjacent vertices in the stack.

Visit the element and put it in the visited list


Next, we visit the element at the top of stack i.e. 1 and go to its adjacent nodes. Since 0 has
already been visited, we visit 2 instead.

Visit the element at the top of stack

Vertex 2 has an unvisited adjacent vertex in 4, so we add that to the top of the stack and visit it.
Vertex 2 has an unvisited adjacent vertex in 4, so we add that to the top of the stack and visit it.

Vertex 2 has an unvisited adjacent vertex in 4, so we add that to the top of the stack and visit it.

After we visit the last element 3, it doesn't have any unvisited adjacent nodes, so we have
completed the Depth First Traversal of the graph.

BFS (Breadth First Search)


BFS traversal of a graph produces a spanning tree as final result. Spanning Tree is a graph
without loops. We use Queue data structure with maximum size of total number of vertices in
the graph to implement BFS traversal.
Algorithms: BFS

We use the following steps to implement BFS traversal...

• Step 1 - Define a Queue of size total number of vertices in the graph.


• Step 2 - Select any vertex as starting point for traversal. Visit that vertex and insert it into
the Queue.
• Step 3 - Visit all the non-visited adjacent vertices of the vertex which is at front of the
Queue and insert them into the Queue.
• Step 4 - When there is no new vertex to be visited from the vertex which is at front of
the Queue then delete that vertex.
• Step 5 - Repeat steps 3 and 4 until queue becomes empty.
• Step 6 - When queue becomes empty, then produce final spanning tree by removing unused
edges from the graph

Example: BFS

Let's see how the Breadth First Search algorithm works with an example. We use an undirected
graph with 5 vertices.

Undirected graph with 5 vertices

We start from vertex 0, the BFS algorithm starts by putting it in the Visited list and putting all its
adjacent vertices in the stack.
Visit start vertex and add its adjacent vertices to queue
Next, we visit the element at the front of queue i.e. 1 and go to its adjacent nodes. Since 0 has
already been visited, we visit 2 instead.

Visit the first neighbor of start node 0, which is 1


Vertex 2 has an unvisited adjacent vertex in 4, so we add that to the back of the queue and visit
3, which is at the front of the queue.

4 remains in the queue


Visit 2 which was added to queue earlier to add its neighbors Only 4
remains in the queue since the only adjacent node of 3 i.e. 0 is already
visited. We visit it.

Visit last remaining item in the queue to check if it has unvisited neighbors

Since the queue is empty, we have completed the Breadth First Traversal of the graph.

INPUT CODE : (BFS)


#include <stdio.h>

#include <conio.h>

int vis[10] = {0}, vertices, edge[10][10] = {0}, neighbour, i, j, noe, q[10], front = 0, rear = 0,

size = 0;

void bfs(int node) {

vis[node] = 1;

q[rear] = node;

rear = (rear + 1) % 10;

size++;

while (size != 0) {

int removed = q[front];

front = (front + 1) % 10;

size--;

printf("%d\n", removed);

for (neighbour = 0; neighbour < vertices; neighbour++) {

if (edge[removed][neighbour] == 1 && !vis[neighbour]) {

vis[neighbour] = 1;

q[rear] = neighbour;

rear = (rear + 1)%10;

size++;

}
}

void display() {

printf("Adjacency Matrix:\n");

for (i = 0; i < vertices; i++) {

for (j = 0; j < vertices; j++) {

printf("%d ", edge[i][j]);

printf("\n");

void main() {

clrscr();

vertices = 4;

edge[0][1] = 1; // Edge from 0 to 1

edge[0][2] = 1; // Edge from 0 to 2

edge[1][0] = 1; // Edge from 1 to 0

edge[1][3] = 1; // Edge from 1 to 3

edge[2][0] = 1; // Edge from 2 to 0

edge[2][3] = 1; // Edge from 2 to 3

edge[3][1] = 1; // Edge from 3 to 1


edge[3][2] = 1;

bfs(0);

display();

getch();

OUTPUT :

INPUT CODE : (DFS)

#include <stdio.h>
#include <conio.h>

int vis[10] = {0}, vertices, edge[10][10] ={0}, neighbour, i, j, noe;

void DFS(int node) {

printf("%d\n", node);

vis[node] = 1;

for (neighbour = 0; neighbour < vertices; neighbour++) {

//check whether they are connected

//and if not visited do dfs

if (edge[node][neighbour] == 1 && !vis[neighbour]) {

DFS(neighbour);

void main() {

int v, u;

clrscr();

printf("Enter number of vertices:\n");

scanf("%d", &vertices);
printf("enter number of edges:\n");

scanf("%d", &noe);

for (i = 0; i < noe; i++) {

scanf("%d%d", &u, &v);

edge[u][v] = 1;

edge[v][u] = 1;

// for (i = 0; i < vertices; i++) {

// if (!vis[i]) {

// DFS(i);

// }

// }

DFS(0);

getch();

OUTPUT :
Conclusion:

Sign and Remark:


R1 R2 R3 R4 Total Marks Signature
(3) (5) (4) (3) (15)

You might also like