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.22_1171]
Rating: 7.4/10 (76 votes cast)
VN:F [1.9.22_1171]
Rating: +16 (from 36 votes)
BFS and DFS, 7.4 out of 10 based on 76 ratings

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

Comments (10)

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

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

  3. this program gives wrong output!!!!!!

  4. thanx a lot!!

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

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

  7. great work :) i find this code useful

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

  9. 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

  10. how it work can u explain that

Leave a Reply