BFS Program in C

Last Updated on August 18, 2023 by Mayank Dham

Breadth-First Search (BFS) is a fundamental graph traversal algorithm used to explore and analyze graphs and trees in a systematic manner. It starts from a specified source vertex and visits all the vertices in the graph, level by level, before moving to the next depth level. This approach ensures that vertices at lower levels are visited before vertices at deeper levels, making BFS particularly useful for finding the shortest path between nodes and solving problems where proximity matters. BFS program in C can be implemented using data structures like queues to manage the order in which vertices are visited, providing an efficient and reliable way to explore the interconnected structure of graphs and trees.

What is Breadth First Search (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 taken into consideration the size of the queue.

Conclusion
The Breadth First Search program in C is a valuable tool for traversing and analyzing graphs and trees. Its systematic exploration of vertices in levels ensures that nodes closer to the source are visited first, making it ideal for tasks such as finding the shortest paths or uncovering the structure of interconnected data. By utilizing data structures like queues, BFS efficiently manages the order of vertex visits, offering a reliable way to navigate complex graphs and trees. Whether applied to networking, pathfinding, or data analysis, the BFS algorithm in C exemplifies the power of organized exploration in solving a range of computational challenges.

Frequently Asked Questions (FAQs)

Here are some frequently asked questions about the BFS program in C.

Q1. What is Breadth First Search (BFS) in a graph or tree?
Ans: BFS is a graph traversal algorithm that explores vertices level by level, starting from a specified source vertex. It visits all vertices at the current level before moving to the next level, ensuring a breadth-first exploration.

Q2. How does the BFS algorithm work in a C program?
Ans: In a BFS program implemented in C, a queue data structure is often used to manage the order of vertex visits. The algorithm starts from the source vertex, enqueues its neighbors, and continues the process iteratively, dequeuing vertices as they are visited.

Q3. What is the advantage of using BFS over other graph traversal methods?
Ans: BFS is particularly useful when finding the shortest path between nodes, as it guarantees that the shortest path is discovered before longer paths. It’s also well-suited for scenarios where nodes are interconnected at various levels, ensuring a balanced exploration.

Q4. Can BFS be used to search in unweighted and weighted graphs?
Ans: BFS is typically used for unweighted graphs. Weighted graphs can use variants like Dijkstra’s algorithm for single-source shortest paths or Bellman-Ford algorithm for negative-weight edges.

Q5. How memory efficient is a BFS program in C?
Ans: A BFS program in C utilizes a queue to manage vertices, which can consume memory proportional to the number of vertices in the graph. For large graphs, memory usage might become a concern, and optimization strategies like compressed data structures can be applied to mitigate this.