traversing a graph through BFS and DFS
Program for traversing a graph through BFS and DFS.
#include<stdio.h>
#define MAX 20
typedef enum boolean{false, true} bool;
int adj[ MAX ][ MAX ];
bool visited[ MAX ];
int n; /* Denotes number of nodes in the graph */
main()
{
int i, v, choice;
create_graph();
while ( 1 )
{
printf( "\n" );
printf( "1. Adjacency matrix\n" );
printf( "2. Depth First Search using stack\n" );
printf( "3. Depth First Search through recursion\n" );
printf( "4. Breadth First Search\n" );
printf( "5. Adjacent vertices\n" );
printf( "6. Components\n" );
printf( "7. Exit\n" );
printf( "Enter your choice : " );
scanf( "%d", &choice );
switch ( choice )
{
case 1:
printf( "Adjacency Matrix\n" );
display();
break;
case 2:
printf( "Enter starting node for Depth First Search : " );
scanf( "%d", &v );
for ( i = 1;i <= n;i++ )
visited[ i ] = false;
dfs( v );
break;
case 3:
printf( "Enter starting node for Depth First Search : " );
scanf( "%d", &v );
for ( i = 1;i <= n;i++ )
visited[ i ] = false;
dfs_rec( v );
break;
case 4:
printf( "Enter starting node for Breadth First Search : " );
scanf( "%d", &v );
for ( i = 1;i <= n;i++ )
visited[ i ] = false;
bfs( v );
break;
case 5:
printf( "Enter node to find adjacent vertices : " );
scanf( "%d", &v );
printf( "Adjacent Vertices are : " );
adj_nodes( v );
break;
case 6:
components();
break;
case 7:
exit( 1 );
default:
printf( "Wrong choice\n" );
break;
} /*End of switch*/
} /*End of while*/
} /*End of main()*/
create_graph()
{
int i, max_edges, origin, destin;
printf( "Enter number of nodes : " );
scanf( "%d", &n );
max_edges = n * ( n – 1 );
for ( i = 1;i <= max_edges;i++ )
{
printf( "Enter edge %d( 0 0 to quit ) : ", i );
scanf( "%d %d", &origin, &destin );
if ( ( origin == 0 ) && ( destin == 0 ) )
break;
if ( origin > n || destin > n || origin <= 0 || destin <= 0 )
{
printf( "Invalid edge!\n" );
i–;
}
else
{
adj[ origin ][ destin ] = 1;
}
} /*End of for*/
} /*End of create_graph()*/
display()
{
int i, j;
for ( i = 1;i <= n;i++ )
{
for ( j = 1;j <= n;j++ )
printf( "%4d", adj[ i ][ j ] );
printf( "\n" );
}
} /*End of display()*/
dfs_rec( int v )
{
int i;
visited[ v ] = true;
printf( "%d ", v );
for ( i = 1;i <= n;i++ )
if ( adj[ v ][ i ] == 1 && visited[ i ] == false )
dfs_rec( i );
} /*End of dfs_rec()*/
dfs( int v )
{
int i, stack[ MAX ], top = -1, pop_v, j, t;
int ch;
top++;
stack[ top ] = v;
while ( top >= 0 )
{
pop_v = stack[ top ];
top–; /*pop from stack*/
if ( visited[ pop_v ] == false )
{
printf( "%d ", pop_v );
visited[ pop_v ] = true;
}
else
continue;
for ( i = n;i >= 1;i– )
{
if ( adj[ pop_v ][ i ] == 1 && visited[ i ] == false )
{
top++; /* push all unvisited neighbours of pop_v */
stack[ top ] = i;
} /*End of if*/
} /*End of for*/
} /*End of while*/
} /*End of dfs()*/
bfs( int v )
{
int i, front, rear;
int que[ 20 ];
front = rear = -1;
printf( "%d ", v );
visited[ v ] = true;
rear++;
front++;
que[ rear ] = v;
while ( front <= rear )
{
v = que[ front ]; /* delete from queue */
front++;
for ( i = 1;i <= n;i++ )
{
/* Check for adjacent unvisited nodes */
if ( adj[ v ][ i ] == 1 && visited[ i ] == false )
{
printf( "%d ", i );
visited[ i ] = true;
rear++;
que[ rear ] = i;
}
}
} /*End of while*/
} /*End of bfs()*/
adj_nodes( int v )
{
int i;
for ( i = 1;i <= n;i++ )
if ( adj[ v ][ i ] == 1 )
printf( "%d ", i );
printf( "\n" );
} /*End of adj_nodes()*/
components()
{
int i;
for ( i = 1;i <= n;i++ )
visited[ i ] = false;
for ( i = 1;i <= n;i++ )
{
if ( visited[ i ] == false )
dfs_rec( i );
}
printf( "\n" );
} /*End of components()*/
traversing a graph through BFS and DFS, Related posts:
- BFS and DFS
- BFS and DFS
- program for topological sorting
- addition and deletion of nodes and edges in a graph
- implentation of queue using arrays
buddy the code fails when i m using following graph :
total nodes : 7
node pairs:
1,3
1,5
1,8
3,6
5,6
8,9
6,7
9,7
although its a valid graph…..i hav asignment of this graph…
will u help me?????