0
2.8kviews
Write a program in C to implement the BFS traversal of a graph. Explain the code with an example
1 Answer
0
91views
    BFS Traversal Program 
    #include<stdio.h>
    #include<stdlib.h>

    #define MAX 100  

    #define initial 1
    #define waiting 2
    #define visited 3

    int n;    
    int adj[MAX][MAX];
    int state[MAX]; 
    void create_graph();
    void BF_Traversal();
    void BFS(int v);

    int queue[MAX], front = -1,rear = -1;
    void insert_queue(int vertex);
    int delete_queue();
    int isEmpty_queue();

    int main()
    {
        create_graph();
        BF_Traversal();
        return 0;
    }

    void BF_Traversal()
    {
        int v;

        for(v=0; v<n; v++) 
            state[v] = initial;

        printf("Enter Start Vertex for BFS: \n");
        scanf("%d", &v);
        BFS(v);
    }

    void BFS(int v)
    {
        int i;

        insert_queue(v);
        state[v] = waiting;

        while(!isEmpty_queue())
        {
            v = delete_queue( );
            printf("%d ",v);
            state[v] = visited;

            for(i=0; i<n; i++)
            {
                if(adj[v][i] == 1 && state[i] == initial) 
                {
                    insert_queue(i);
                    state[i] = waiting;
                }
            }
        }
        printf("\n");
    }

    void insert_queue(int vertex)
    {
        if(rear == MAX-1)
            printf("Queue Overflow\n");
        else
        {
            if(front == -1) 
                front = 0;
            rear = rear+1;
            queue[rear] = vertex ;
        }
    }

    int isEmpty_queue()
    {
        if(front == -1 || front > rear)
            return 1;
        else
            return 0;
    }

    int delete_queue()
    {
        int delete_item;
        if(front == -1 || front > rear)
        {
            printf("Queue Underflow\n");
            exit(1);
        }

        delete_item = queue[front];
        front = front+1;
        return delete_item;
    }

    void create_graph()
    {
        int count,max_edge,origin,destin;

        printf("Enter number of vertices : ");
        scanf("%d",&n);
        max_edge = n*(n-1);

        for(count=1; count<=max_edge; count++)
        {
            printf("Enter edge %d( -1 -1 to quit ) : ",count);
            scanf("%d %d",&origin,&destin);

            if((origin == -1) && (destin == -1))
                break;

            if(origin>=n || destin>=n || origin<0 || destin<0)
            {
                printf("Invalid edge!\n");
                count--;
            }
            else
            {
                adj[origin][destin] = 1;
            }
        }
    }
  1. Example of BFS

    a. Consider below Graph as follows

    enter image description here

    b. The vertex 0 is the starting vertex in our case. We start our traversal from the vertex 0. Then we will visit all vertices adjacent to vertex 0 i.e., 1, 4, 3. Here, we can visit these three vertices in any order.

    c. Suppose we visit the vertices in order 1,3,4.The traversal would be: 0 1 3 4

    d. Now, we shall visit all the vertices adjacent to 1, then all the vertices adjacent to 3 and then all the vertices adjacent to

    e. So first we shall visit 2 (since it is adjacent to 1), then 6 (since it is adjacent to 3) and 5, 7 (since these are adjacent to 3.

    f. The traversal would be: 0 1 3 4 2 6 5 7

Please log in to add an answer.