BFS and DFS

 

/* B.F.S AND D.F.S */
 
#include<stdio.h>
int q[ 20 ], top = -1, front = -1, rear = -1, a[ 20 ][ 20 ], vis[ 20 ], stack[ 20 ];
int delete();
 
void add ( int item );
 
void bfs( int s, int n );
 
void dfs( int s, int n );
 
void push( int item );
 
int pop();
 
main()
{
    int n, i, s, ch, j;
    char c, dummy;
    printf( "ENTER THE NUMBER VERTICES " );
    scanf( "%d", &n );
 
    for ( i = 1;i <= n;i++ )
        {
            for ( j = 1;j <= n;j++ )
                {
                    printf( "ENTER 1 IF %d HAS A NODE WITH %d ELSE 0 ", i, j );
                    scanf( "%d", &a[ i ][ j ] );
                }
        }
 
    printf( "THE ADJACENCY MATRIX IS\n" );
 
    for ( i = 1;i <= n;i++ )
        {
            for ( j = 1;j <= n;j++ )
                {
                    printf( " %d", a[ i ][ j ] );
                }
 
            printf( "\n" );
        }
 
    do
        {
            for ( i = 1;i <= n;i++ )
                vis[ i ] = 0;
 
            printf( "\nMENU" );
 
            printf( "\n1.B.F.S" );
 
            printf( "\n2.D.F.S" );
 
            printf( "\nENTER YOUR CHOICE" );
 
            scanf( "%d", &ch );
 
            printf( "ENTER THE SOURCE VERTEX :" );
 
            scanf( "%d", &s );
 
            switch ( ch )
                {
 
                case 1:
                    bfs( s, n );
                    break;
 
                case 2:
                    dfs( s, n );
                    break;
                }
 
            printf( "DO U WANT TO CONTINUE(Y/N) ? " );
            scanf( "%c", &dummy );
            scanf( "%c", &c );
        }
    while ( ( c == 'y' ) || ( c == 'Y' ) );
}
 
void bfs( int s, int n )
{
    int p, i;
 
    add
        ( s );
 
    vis[ s ] = 1;
 
    p = delete();
 
    if ( p != 0 )
        printf( " %d", p );
 
    while ( p != 0 )
        {
            for ( i = 1;i <= n;i++ )
                if ( ( a[ p ][ i ] != 0 ) && ( vis[ i ] == 0 ) )
                    {
                        add
                            ( i );
 
                        vis[ i ] = 1;
                    }
 
            p = delete();
 
            if ( p != 0 )
                printf( " %d ", p );
        }
 
    for ( i = 1;i <= n;i++ )
        if ( vis[ i ] == 0 )
            bfs( i, n );
}
 
void add
    ( int item )
    {
        if ( rear == 19 )
            printf( "QUEUE FULL" );
        else
            {
                if ( rear == -1 )
                    {
                        q[ ++rear ] = item;
                        front++;
                    }
                else
                    q[ ++rear ] = item;
            }
    }
 
int delete()
{
    int k;
 
    if ( ( front > rear ) || ( front == -1 ) )
        return ( 0 );
    else
        {
            k = q[ front++ ];
            return ( k );
        }
}
 
void dfs( int s, int n )
{
    int i, k;
    push( s );
    vis[ s ] = 1;
    k = pop();
 
    if ( k != 0 )
        printf( " %d ", k );
 
    while ( k != 0 )
        {
            for ( i = 1;i <= n;i++ )
                if ( ( a[ k ][ i ] != 0 ) && ( vis[ i ] == 0 ) )
                    {
                        push( i );
                        vis[ i ] = 1;
                    }
 
            k = pop();
 
            if ( k != 0 )
                printf( " %d ", k );
        }
 
    for ( i = 1;i <= n;i++ )
        if ( vis[ i ] == 0 )
            dfs( i, n );
}
 
void push( int item )
{
    if ( top == 19 )
        printf( "Stack overflow " );
    else
        stack[ ++top ] = item;
}
 
int pop()
{
    int k;
 
    if ( top == -1 )
        return ( 0 );
    else
        {
            k = stack[ top-- ];
            return ( k );
        }
}
VN:F [1.9.21_1169]
Rating: 7.3/10 (75 votes cast)
VN:F [1.9.21_1169]
Rating: +16 (from 36 votes)
BFS and DFS, 7.3 out of 10 based on 75 ratings

Related posts:

  1. queue operations using linked list
  2. Implementation of stack using linked list
  3. implementation of stack using array
  4. infix expression evaluation

28. September 2008 by Jishnu
Categories: C Programming | Tags: , , | 9 comments

Comments (9)

  1. Anonymous says November 9, 2008 at 7:51 pm

    gr8 work…. may ur work continue lik this 4ever….

  2. Pankaj Jain says March 16, 2009 at 2:42 pm

    thanks i need it desperately!!!!
    thanks a lot

  3. ankit uppal says March 18, 2009 at 5:50 pm

    this program gives wrong output!!!!!!

  4. Anonymous says May 19, 2009 at 1:46 pm

    thanx a lot!!

  5. manuel says April 12, 2011 at 3:44 pm

    Why is it that no one ever comment the code?!??

  6. candis says March 26, 2012 at 12:33 pm

    instead of 2 delete(/pop) operations, we could have just 1, right inside the loop (amongst the first statements!!)

  7. Anonymous says March 28, 2012 at 8:03 am

    great work :) i find this code useful

  8. amit says April 2, 2012 at 9:08 am

    it is really very tough to read this code. please improve your skills. use better variable names and please write explanatory comments.

  9. shantanu santoki says August 6, 2012 at 6:05 pm

    dfs is not work for this graph i show a graph in matrix level
    0 1 1 0 0 1
    1 0 0 1 1 0
    1 0 0 1 1 0
    0 1 1 0 0 1
    0 1 1 0 0 1
    1 0 0 1 1 0
    dear please help me for given matrix