Breadth First Search(BFS) and Depth First Search(DFS) program in C

Below is the c program to implement Breadth First Search(BFS) and Depth First Search(DFS). BFS and DFS are the shortest path algorithm. Both use different structures. BFS(Breadth First Search) uses a queue data structure to find the shortest path of traversal. DFS(Depth First Search) uses a stack data structure to find the shortest path of traversal.

BFS stands for Breadth First Traversal is a vertex-based method for traversing the shortest path in the graph. BFS uses a Queue arrangement that follows first in first out. In BFS, one vertex is chosen at a time when it's visited and marked then its adjacency list is visited and stored within the queue. BEF is slower than DFS.

DFS stands for Depth First Traversal is an edge-based technique. DFS performs it in two stages, first visited vertices are pushed into the stack and second, if there are no vertices then visited vertices are popped.

Difference between BFS and DFS

BFSDFS
BFS stands for Breadth First Search.DFS stands for Depth First Search.
The time complexity of BFS is O(V+E). Here, E stands for Edges and V stands for Vertices.The time complexity of DFS is also O(V+E). Here, E stands for Edges and V stands for Vertices.
Breadth First Search (BFS) uses a Queue data structure for finding the shortest path.Depth First Search (DFS) uses a Stack data structure
BFS proceeds level by level.DFS follows first a path form the starting to the ending node.
Memory consumption is Inefficient.Memory consumption is Efficient.
The structure of the constructed tree is Wide and short.The structure of the constructed tree is Narrow and long.
Application Examines bipartite graph, connected component and shortest path present in a graph.Application Examines two-edge connected graph, strongly connected graph, acyclic graph, and topological order.
BFS starts traversal from the root node and visits nodes in a level by level manner. DFS starts the traversal from the root node and visits nodes as far as possible from the root node.


BFS(Breadth First Search) Example step by step

Below is the BFS algorithm example, Which shows step by step traversal from nodes. The example contains a total of 7 nodes, A to G in different sequences. BFS algorithm traverses as per the rules mentioned below.

BFS Algorithm Rules:
  1. Visit the unvisited vertex and mark it visited. Also, insert it in the queue and display it.
  2. If no unvisited adjacent vertex found, remove the first vertex from the queue.
  3. Repeat step 1 and step 2 until the queue is empty.
BFS graph example with traversal and BFS program in c
BFS graph example with traversal










To understand the BFS algorithm more effectively, follow the below-mentioned steps with representation shown with the queue structure. Queue follows FIFO (First in, First out) pattern.

BFS Algorithm example with queue structure
BFS Algorithm example with queue structure
BFS Algorithm steps:
  1. Vertex A is stored in the queue and expanded.
  2. Expand successors of A, Which are vertices B, D and G. Store B, D and G in the queue and remove vertex A from the queue.
  3. Remove B from the front end of the queue and store its successor vertices E and F in the queue.
  4. Remove D from the front end of the queue and its successor F is already visited.
  5. Remove G from the front end of the queue and its successor E is already visited.
  6. Remove E & F from the front end of the queue and store its successor vertice C in the queue.
  7. Remove C from the queue.
The final output is A, B, D, G, E, F, C.

DFS(Depth First Search) Example step by step

Below is the DFS algorithm example, Which shows DFS graph traversal step by step. The example contains a total of 7 nodes, A to G in different sequences. DFS algorithm traverses as per the rules mentioned below.

BFS Algorithm Rules:
  1. Push the first vertices on top of the stack 
  2. Take the top node of the stack and add it to the visited vertices list.
  3. Find vertex's adjacent nodes. Which is not in the list of the visited nodes add them top of the stack.
  4. Keep repeating step 2 &3 until the stack is empty.



To understand the DFS algorithm more effectively, follow the below-mentioned steps with representation shown with the queue structure. Stack follows LIFO (Last in, First out) pattern.



DFS Algorithm steps:

  1. Consider A is the first vertex, explore it and store it in the stack.
  2. Vertex A has three successors B, D, and G. Between them alphabetically B is explored first and stored in the stack.
  3. Vertex B has two successors E and F, amongst them alphabetically E is explored first and stored in the stack.
  4. The only successor of E is G, which is explored and stored in the stack.
  5. The successors A and E of vertex G are already visited.
  6. Now, vertex B is at top of the stack, which does have unexplored vertex F. Explore it and store it in the stack.
  7. Next, Vertex F has two successors C and D. Between them alphabetically C is explored and stored firest in the stack.
  8. Vertex C has only one successor F, which is already visited.
  9. The second successor of vertex F is D is visited and stored in the stack.
  10. Vertex D does not have any unvisited successors.
  11. Final output if A, B, E, G, F, C, and D


Simple BFS and DFS Program in C

/* simple dfs algorithm in c and simple bfs program in c */
#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 );
        }
}


Post a Comment

1 Comments