Graph Traversal Methods

Graph Traversal Methods

The graph can be traversed using Breadth first search and depth first search method. Let us discuss these methods with the help of examples -

Breadth First Traversal

For the graph to traverse it by BFS, a vertex V₁ in the graph will be visited first, then all the vertices adjacent to V₁ will be traversed suppose adjacent to V₁ are (V₂ V₃, V₄...V_n). So V₂, V₃….V_n will be printed first. Then again from V₂ the adjacent vertices will be printed. This process will be continued for all the vertices to get encounterd. To keep track of all the vertices and their adjacent vertices we will make use of queue data structure. Also we will make use of an array for visited nodes. The nodes which are get visited are set to 1. Thus we can keep track of visited nodes.

In short in BFS traversal we follow the path in breadthwise fashion. Let us see the algorithm for breadth first search.

Algorithm :

1. Create a graph. Depending on the type of graph i.e. directed or undirected set the value of the flag as either 0 or 1 respectively.

2. Read the vertex from which you want to traverse the graph say Vi.

3. Initialize the visited array to 1 at the index of Vi.

4. Insert the visited vertex Vi in the queue.

5. Visit the vertex which is at the front of the queue. Delete it from the queue and place its adjacent nodes in the queue.

6. Repeat the step 5, till the queue is not empty.

7. Stop.

1. BFS (non-recursive) For Adjacency Matrix

Ex. 5.1 'C' Program

/******************************************************************

Program to create a Graph. The graph is represented using Adjacency Matrix.

*****************************************************************/

#include<stdio.h>

#include<conio.h>

#include<stdlib.h>

#define size 20

#define TRUE 1

#define FALSE O

/*

int g[size][size];

int visit[size];

int Q[size];

int front, rear;

int n;

void main()

{

int v1, v2;

char ans ='y';

void create(),bfs();;

clrscr();

create();

clrscr();

printf("The Adjacency Matrix for the graph is \n");

for (v1 = 0; v1 < n; v1++)

{

for (v2 = 0; v2 < n; v2++)

printf("%d ", g[v1][v2]);

printf("\n");

}

getch();

do

{

for (v1 = 0; v1 < n; v1++)

visit [v1] = FALSE;

clrscr();

printf("Enter the Vertex from which you want to traverse ");

scanf("%d", &v1);

if (v1 >= n )

printf("Invalid Vertex\n");

else

{

printf("The Breadth First Search of the Graph is \n");

bfs(v1);

getch();

}

printf("\nDo you want to traverse from any other node?");

ans=getche();

} while(ans=='y');

exit(0);

}

void create()

{

Int v1, v2;

char ans='y';

printf("\n\t\t This is a Program To Create a Graph");

printf("\n\t\t The Display Is In Breadth First Manner");

printf("\nEnter no. of nodes");

scanf("%d",&n);

for (v1= 0; v1 < n; v1++)

for (v2 = 0; v2 < n; v2++)

g[v1][v2] = FALSE;

printf("\nEnter the vertices no. starting from 0");

do

{

printf("\nEnter the vertices v1 & v2");

scanf("%d %d", &v1, &v2);

if (v1 >= n || v2 >= n)

printf("Invalid Vertex Value\n");

else

{

g[v1][v2]=TRUE;

g[v2][v1] = TRUE;

}

printf("\n\nAdd more edges??(y/n)");

ans=getche();

}while(ans =='y');

}

void bfs(int v1)

{

int v2;

visit [v1] = TRUE;

front rear = -1;

Q[++rear] = v1;

while (front != rear)

{

v1 = Q[++front];

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

for ( v2 = 0; v2 < n; v2++)

{

if (g[v1][v2]==TRUE && visit [v2]==FALSE)

{

Q[++rear] = v2;

visit [v2]: TRUE;

}

}

}

}

Output

This is a Program To Create a Graph

The Display Is In Breadth First Manner

Enter no. of nodes 4

Enter the vertices no. starting from 0

Enter the vertices v1 & v2

01

Add more edges??(y/n)y

Enter the vertices v1 & v2

02

Add more edges??(y/n)y

Enter the vertices v1 & v2

13

Add more edges??(y/n)y

Enter the vertices v1 & v2

23

Add more edges??(y/n)

The Adjacency Matrix for the graph is

0 1 1 0

1 0 0 1

1 0 0 1

0 1 1 0

Enter the Vertex from which you want to traverse 0

The Breadth First Search of the Graph is

0

1

2

3

Do you want to traverse from any other node?

Enter the Vertex from which you want to traverse 1

The Breadth First Search of the Graph is

1

0

3

2

Do you want to traverse from any other node?

Explanation of logic of BFS

In BFS the queue is maintained for storing the adjacent nodes and an array 'visited' is maintained for keeping the track of visited nodes i.e. once a particular  node is visited it should not be revisited again. Let us see how our program works.

So output will be - BFS for above graph as

1 2 3 4

C Function for BFS using Adjacency List

/* Global declarations */

typedef struct node

{

int vertex;

struct node *next;

}node;

/* Declare an adjacency matrix for storing the graph */

node *head[10];

int visited[MAX];

int Queue[MAX];

int front, rear;

int n;

void bfs(int V1)

{

int i;

node *first;

front=-1;

rear=-1;

Queue[++rear] = V1;

while (front != rear)

{

i = Queue[++front];

if (visited[i] == FALSE)

{

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

visited[i]= TRUE;

}

first=head[i];

while (first != NULL)

{

if (visited[first->vertex] == FALSE)

Queue[++rear] = first->vertex;

first=first->next;

}

}

}

Depth First Traversal

• In depth first search traversal, we start from one vertex, and traverse the path as deeply as we can go. When there is no vertex further, we traverse back and search for unvisited vertex.

• An array is maintained for storing the visited vertex.

For example:

• The DFS will be (if the source vertex is 0) 0-1-2-3-4.

• The DFS will be (if we start from vertex 3) 3-4-0-1-2.

DFS by Adjacency Matrix (Recursive Program)

Ex. 5.2 'C' Program

/****************************************************************

Program to create a Graph. The graph is represented using Adjacency Matrix.

****************************************************************/

#include <stdio.h>

#include<conio.h>

#include<stdlib.h>

/* List of defined constants */

#define MAX 20

#define TRUE 1

#define FALSE O

/* Declare an adjacency matrix for storing the graph */

int g[MAX][MAX];

int v[MAX];

int n;

void main()

{

/* Local declarations */

int v1, v2;

char ans;

void create();

void Dfs(int);

clrscr();

create();

clrscr();

printf("The Adjacency Matrix for the graph is \n");

for (v1 = 0; v1 < n; v1++)

{

for (v2 = 0; v2 < n; v2++)

printf("%d ", g[v1][v2]);

printf("\n");

}

getch();

do

{

for (v1 = 0; v1 < n; v1++)

v[v1] = FALSE;

clrscr();

printf("Enter the Vertex from which you want to traverse :");

scanf("%d", &v1);

if (v1 >= MAX)

printf("Invalid Vertex\n");

else

{

printf("The Depth First Search of the Graph is \n");

Dfs(v1);

}

printf("\n Do U want To Taverse By any Other Node?");

ans=getch();

} while(ans=='y');

}

void create()

{

int ch, v1, v2, flag;

char ans='y';

printf("\n\t\t This is a Progrm To Create a Graph");

printf("\n\t\t The Display Is In Depth First Manner");

getch();

clrscr();

flushall();

for (v1 = 0; v1 < n; v1++)

for (v2 = 0; v2 < n; v2++)

g[v1][v2]=FALSE;

printf("\nEnter no. of nodes");

scanf("%d", &n);

printf("\nEnter the vertices no. starting from 0");

do

{                                              

printf("\nEnter the vertices v1 & v2");

scanf("%d %d", &v1, &v2);

if (v1 >= n || v2 >= n)

printf("Invalid Vertex Value\n" );

else

{

g[v1][v2] = TRUE;

g[v2][v1] = TRUE;

}

printf("\n\nAdd more edges??(y/n)");

ans=getche();

} while(ans=='y');

}

void Dfs( int v1)

{

int v2;

printf("%d\n", v1);.

for ( v2 = 0; v2 < MAX; v2++)

if (g[v1][v2] == TRUE && v[v2] == FALSE)

Dfs(v2);

}

Output

This is a Program To Create a Graph

 The Display Is In Depth First Manner

 Enter no. of nodes 4

Enter the vertices no. starting from 0

Enter the vertices v1 & v2 0 1

 Add more edges??(y/n)y

Enter the vertices v1 & v2 0 2

Add more edges??(y/n)y

Enter the vertices v1 & v2 1 3

Add more edges??(y/n)y

Enter the vertices v1 & v2 2 3

Add more edges??(y/n)

The Adjacency Matrix for the graph is

0 1 1 0

1 0 0 1

1 0 0 1

0 1 1 0

Enter the Vertex from which you want to traverse: 1

The Depth First Search of the Graph is

1

0

2

3

Do U want To Traverse By any Other Node?

Explanation of Logic for Depth First Traversal

In DFS the basic data structure for storing the adjacent nodes is stack. In our program we have used a recursive call to DFS function. When a recursive call is invoked actually push operation gets performed. When we exit from the loop pop operation will be performed. Let us see how our program works.

Since all the nodes are covered stop the procedure.

So output of DFS is

1  2  4  3

Ex. 5.3 C Function (Non-recursive)

/****************************************************************

Program to create a Graph. The graph is represented using

Adjacency Matrix (Non recursive program)

***************************************************************/

#include<stdio.h>

void Dfs(int v1)

{

int v2;

void push(int item);

int pop();

push(v1);

while(top!= -1)

{

v1=pop();

if(v[v1]==FALSE)

{

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

v[v1]=TRUE;

}

for (v2 = 0; v2 < n; v2++)

if (g[v1][v2] == TRUE && v[v2]==FALSE)

push(v2);

}

}

void push(int item)

{

st[++top]=item;

}

int pop()

{

int item;

item=st[top];

top--;

return item;

}

Ex. 5.4 C Function - Adjacency List

typedef struct node

{

int vertex;

struct node *next;

}node;

/* Declare an adjacency matrix for storing the graph */

node *head[MAX]; /*Array Of head nodes*/

int visited[MAX]; /*visited array for checking whether the array is visited or not*/ void Dfs(int V1)

{

int V2;

node *first;

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

visited[V1]=TRUE;

first = head[V1];

while (first != NULL)

if (visited [first->vertex] == FALSE)

Dfs (first->vertex);

else

first first ->next;

}

Ex. 5.8.1 Define DFS and BFS graph. Show DFS and BFS for the graph given below.

Sol. :

DFS Refer section 5.8.2.

BFS Refer section 5.8.1.

BFS for given graph

Now delete each vertex from Queue and print it as BFS sequence:

V1 V2 V3 V4 V5 V6 V7 V8

DFS for given graph

As all nodes are visited so.

DFS of graph = V1, V2

Ex. 5.8.2 For the following construct:

i) Adjacency matrix

ii) Adjacency list

iii) DFS search

iv) BFS search

iii) DFS :

1 2 5 4 63

iv) BFS :

1 2 3 5 64

Ex. 5.8.3 From the Fig. 5.8.3, in what order are the vertices visited using DFS and BFS starting from vertex A? Where a choice exists, use alphabetical order.

Difference between DFS and BFS

Review Questions

1. Distinguish between breadth first search and depth first search with example.

2. Explain depth first and breadth first traversal.