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()*/
VN:F [1.9.22_1171]
Rating: 8.0/10 (20 votes cast)
VN:F [1.9.22_1171]
Rating: -3 (from 9 votes)
traversing a graph through BFS and DFS, 8.0 out of 10 based on 20 ratings

15. November 2009 by Jishnu
Categories: C Programming | Tags: | 1 comment

One Comment

  1. 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?????

Leave a Reply