BFS Program in C

In this article, we will discuss the BFS program in C language for a graph. There are 2 types of graph traversals DFS and BFS. DFS stands for Depth First Search and BFS stands for Breadth First Search. In DFS, we traverse a graph recursively depth-wise whereas, in BFS, we traverse a graph radially. So, let’s start by understanding BFS, and then we will write the program.

What is BFS?

Consider the graph given below.

So, in the undirected graph shown above, 0 is the source vertex i.e. starting from 0, we have to do the BFS traversal. To understand BFS, we need to understand what Preorder and Levelorder traversals are in a tree. So, consider the tree shown below.

For the preorder traversal of a tree, we have to traverse the tree in the order “Node-Left-Right”. This means we have to first go to a node, then its left and right child recursively. The preorder traversal of the above tree is shown below.

This is also called the DFS (Depth First Traversal) of a tree because here we are traversing depth-wise and exploring the nodes on the same level later.

In fact, not just Preorder but Postorder and Inorder (for a binary tree only) are also DFS in the case of a tree. This is because in all the tree traversals viz, Preorder, Postorder and Inorder, the recursion call stack is formed in such a way that we traverse the tree depth wise and then explore the nodes on the same level.

The Level order traversal of a tree is the traversal where we traverse the tree level-wise i.e. the nodes on the same level are explored first. The level order traversal of a tree is shown below.

In programming, we have to use a stack when performing the DFS and we use a Queue while performing Levelorder traversal in a tree.

Now, the Level order traversal is the BFS (Breadth First Search) traversal of a tree as the nodes are explored radially i.e. the nodes on the same level are explored first.

For a graph also, the BFS traversal means the same as level order traversal. So, let us now start understanding the procedure of implementing the BFS program in C.

BFS Program in C (Dry Run Example)

We will continue the example shown above. Consider the graph, an empty queue and a boolean array “visited” as shown below.

The visited array contains all the values “False” initially indicating that we have not visited any vertex till now. So, we know that the source is given to us.

The initial step is to put the source into the queue. Please note that the vertices will be marked visited when they will exit the queue, not while entering the queue.

So, the source is kept in the queue as shown below.

Now, we will start the repeating steps. So, we have to perform the following repeating steps now till the queue is empty.

1. Take a vertex out of the queue.
2. Mark the vertex as visited in the “visited” boolean array.
3. Add this vertex to the BFS traversal.
4. Add all the unvisited neighbors of this vertex into the queue.

So, let’s follow the step shown above. We will remove 0 from the queue, mark it visited, add 0 to the BFS, and add all the unvisited neighbors of 0 (i.e. 1 and 2) into the queue.

Now, as already discussed, we have to repeat the 4 steps again and again until the queue is empty. Since the queue is not empty right now, we again repeat the 4 steps. So, we will dequeue vertex 1 from the queue, mark it visited, add it to the BFS, and will add 3 to the queue. This is because 0 (which is also a neighbor of vertex 1) is already visited.

Since the queue is not empty now also, we will again dequeue the next vertex. So, vertex 2 will be dequeued from the queue, will be marked visited, will be added to the BFS, and its unvisited neighbor i.e. vertex 4 will be added to the queue.

So, the queue is not empty yet. Again, we will now take out vertex 3 from the queue, mark it visited, add it to the BFS, and will add its unvisited neighbor to the queue. Since 3 does not have any unvisited neighbors, nothing will be added to the queue in this step.

Next, we remove vertex 4, mark it visited, add it to the BFS, and add its unvisited neighbors (5 and 6) to the queue.

Vertex 5 will be removed from queue no.w It will be marked visited and will be added to the BFS. Since there are no unvisited neighbors of vertex 5, nothing will be added to the queue.

Finally, we will remove vertex 6 from the queue. We will mark it visited, and add it to the BFS, and since there are no unvisited neighbors of vertex 6, nothing will be added to the queue.

The queue has now become empty and we have to stop our procedure. So, we have got BFS as shown below.

So, now that we know the complete procedure, let us write the BFS program in C language.

BFS Program in C

#include<stdio.h>
#include<stdlib.h>
 
struct queue
{
    int size;
    int f;
    int r;
    int* arr;
};
 
 
int isEmpty(struct queue *q){
    if(q->r==q->f){
        return 1;
    }
    return 0;
}
 
int isFull(struct queue *q){
    if(q->r==q->size-1){
        return 1;
    }
    return 0;
}
 
void enqueue(struct queue *q, int val){
    if(isFull(q)){
        printf("This Queue is full\n");
    }
    else{
        q->r++;
        q->arr[q->r] = val;
        // printf("Enqued element: %d\n", val);
    }
}
 
int dequeue(struct queue *q){
    int a = -1;
    if(isEmpty(q)){
        printf("This Queue is empty\n");
    }
    else{
        q->f++;
        a = q->arr[q->f]; 
    }
    return a;
}

int main() {
    struct queue q;
    q.size = 400;
    q.f = q.r = 0;
    q.arr = (int*) malloc(q.size*sizeof(int));
    
    // BFS Implementation 
    int node;
    int i = 0;
    int visited[7] = {0,0,0,0,0,0,0};
    int a [7][7] = {
        {0,1,1,0,0,0,0},
        {1,0,0,1,0,0,0},
        {1,0,0,1,1,0,0},
        {0,1,1,0,0,0,0},
        {0,0,1,0,0,1,1},
        {0,0,0,0,1,0,1}, 
        {0,0,0,0,1,1,0} 
    };
    printf("%d ", i);
    enqueue(&q, i);
    while (!isEmpty(&q))
    {
        int node = dequeue(&q); //remove
        visited[i] = 1; //mark visited
        for (int j = 0; j < 7; j++)
        {
            if(a[node][j] ==1 && visited[j] == 0){
                printf("%d ", j); //add to the bfs
                visited[j] = 1;
                enqueue(&q, j); //add neighbors
            }
        }
    }
    return 0;
}

Time Complexity of BFS Program in C:

The time complexity of the BFS program in C is O(V+E) where V is the number of vertices (or nodes) and E is the number of edges.

Space Complexity of BFS Program in C:

The space complexity of the BFS program in C is O(V) as we have created a visited array of size V and also the size of queue is taken into consideration.

So, this is the BFS program in C. We hope that you have understood the concept of BFS and Level order traversal in Graphs and trees. We also hope that you liked the complete dry run procedure and have practiced the dry run yourself too. We have implemented the C program using adjacency matrix which might increase the time complexity in the worst case. Try to implement it using adjacency list on your own.