**Graph traversals ** - Traversing a graph means
visiting all vertices in G that are reachable from the given start
vertex V.Two different methods are available as follows -

**Depth first search** - The start vertex V is visited.Next
an unvisited vertex w adjacent to V is selected and a depth first
search from w is initiated. When a vertex U is reached such that
all its adjacent vertices have been visited back up to the last
vertex visited which has been an unvisited vertex W adjacent to
it and initiate a depth first search from W. The search terminates
when no unvisted vertex can be reached from any of the visited ones.

**Breath first search** - Starting at vertex V and
marking it as visited, breath first search differs from depth first
search in that all unvisited vertices adjacent to V are visited
next. Then unvisited vertices adjacent to these vertices are visited
and so on.

//.. A Program to implement Depth First Search & Breadth First Search methods # include < stdio.h > # include < conio.h > void main() { int option, i, j, n; int adj_mat[50][50]; clrscr(); printf("\n A Program to implement Depth First Search (DFS) &"); printf("\n Breadth First Search (BFS) methods \n "); printf("\n How Many Vertices ? : "); scanf("%d", &n); read_graph(adj_mat, n); printf("\n\n DFS Output is \n\n"); dfs( adj_mat, n ); printf("\n"); printf("\n BFS Output is \n\n "); bfs( adj_mat, n ); } // main int read_graph ( int adj_mat[50][50], int n ) { int i, j; char reply; for ( i = 1 ; i < = n ; i++ ) { for ( j = 1 ; j <= n ; j++ ) { if ( i == j ) { adj_mat[i][j] = 0; continue; } // if printf("\n Vertices %d & %d are Adjacent ? (Y/N) :",i,j); flushall(); scanf("%c", &reply); if ( reply == 'y' || reply == 'Y' ) adj_mat[i][j] = 1; else adj_mat[i][j] = 0; } // for } // for return; } // read_graph int dfs ( int adj_mat[50][50], int n ) { int visited[20]; int stk[20]; int top, i, j, v; //... Initialize Stack top = -1; //... Initialize Visited Array to 0 for ( i = 1 ; i <= n ; i++ ) visited[i] = 0; //... Push First Node top++; stk[top] = 1; //... While Stack is Not Empty do the following while ( top != -1 ) { //... Pop Stack Top Node v = stk[top]; top--; //... Print V On Screen if it not visited if ( visited[v] == 0 ) { printf("\t%d", v); visited[v] = 1; //... Push the Non-Visited Adj_Node of V in Stack for( i = n ; i >= 1 ; i-- ) { if ( adj_mat[v][i] == 1 && visited[i] == 0 ) { top++; stk[top] = i; } // if } // for } // if } // while return; } // dfs int bfs (int adj_mat[50][50], int n ) { int visited[20]; int q[20], f, r, i, j, v; //... Initialize Queue f = r = 1; //... Initialize Visited Array to 0 for ( i = 1 ; i < = n ; i++ ) visited[i] = 0; //... Add First Node in Queue 'q' r++; q[r] = 1; //... While Queue is Not Empty do the following while ( f != r ) { //... Delete Front Node f++; v = q[f]; //... Print 'v' On Screen if it Not Visited if ( visited[v] == 0 ) { printf("\t%d", v); visited[v] = 1; //... Add the Non-Visited Adj_Node of 'v' in Queue for ( i = 1 ; i <= n ; i++ ) { if ( adj_mat[v][i] == 1 && visited[i] == 0 ) { r++; q[r] = i; } // if } // for } // if } // while return; } // bfs