BFS Program in C - Scaler Topics

Breadth-first search (BFS) is a fundamental algorithm for traversing tree or graph data structures. Whether applied to a tree root or an arbitrary node (referred to as a 'search key' in graphs), BFS explores all neighbour nodes at the current depth before progressing to the next depth level. Unlike depth-first search, which delves as far as possible before backtracking, BFS systematically visits nodes by depth levels. This algorithm employs a queue to manage the order of vertex visitation, starting from the root node and systematically traversing the structure while marking visited nodes.

Breadth First Search (BFS) Program in C

To implement the BFS algorithm in C, users need to store the nodes that are already visited but not processed; for this, we will store them in a queue, which will provide us the FIFO property (First in First Out). Also, we need to maintain the visited nodes to escape revisiting and reprocessing them. So, we will maintain an array to mark visited nodes.

Algorithm:

Initially, we will add the initial node from where we have to start the search and mark it visited in the visited array.
Run the while loop until the queue is non-empty.
At each iteration, find all the connected nodes to the front element of the queue.
If the connected nodes to the front elements are already visited, then do nothing
Else, mark them visited in the visited array and push them into the queue.

Note: These are the basic steps of the BFS in C algorithm; now, we can add some special points into the implementation, like: If we are searching for a special node, then we can end the while loop when we reach the required node.

Let’s take an example to show the working of the above-given algorithm: Imagine a graph with six nodes:

Here,

1 is connected to 2 and 3.
2 is connected to 1 and 3.
3 is connected to 1, 2, 4, and 5.
4 is connected to only 3.
5 is connected to 3 and 6.
6 is connected to only 5.

In starting there is nothing in the queue and all the indexes of the visited array are zero.

As we are going to start Breadth-First Search from 1, we will add it into the queue and make it visited:

Queue: 1

Visited: 1 0 0 0 0 0

We will process for node 1 and add connected nodes to it that are 2 and 3.

Queue: 2 3

Visited: 1 1 1 0 0 0

Now we will process over Node 2, but both of its connected nodes 1 and 3 are visited so we will simply pop 2 from queue and process on 3.

Queue: 3

Visited: 1 1 1 0 0 0

For node 3: Nodes 1 and 2 are already visited so we will add 4 and 5.

Queue: 4 5

Visited: 1 1 1 1 1 0

Now we will process over Node 4, but its connected nodes 3 is already visited so we will simply pop 4 from the queue and process on 5.

Queue: 5

Visited: 1 1 1 1 1 0

For node 5: Node 3 is already visited so we will add 6 to the queue.

Queue: 6

Visited: 1 1 1 1 1 1

For Node 6 the only connected Node is 5 and as it is already visited we will pop node 6 from the queue and the Algorithm will stop here.

The order of the nodes being added in the queue is: 1 2 3 4 5 6.

Now we are going to implement the above-explained example but, before moving to implement we will discuss queues in C. As we have seen that the queue data structure is used to store the nodes which are visited but not proceeded, we need to implement a queue data structure as there is no inbuilt queue data structure present in the C language.

Let’s see the code implementation of the above example:

Output Output for the above BFS implementation in C is:

As per our BFS program in C, our expected output will simply be the order of the nodes by which they are processed or added to the queue.

Explain the Working of the BFS Implementation in C Program

In the above program, we have implemented the BFS algorithm in C for that: Firstly, we implemented the queue data structure using an array, and defined two integer variables ‘front’ and ‘back’ to indicate the positions in the array named queue. We created two functions push and pop to perform queue operations:

push: push function takes a single parameter to push at the end of the queue and increments the end variable by 1.
pop: pop function pops the front element of the queue by incrementing the front variable by 1.

In the main function first, the adjacency matrix is provided which indicates ith and the jth node are connected or not.

Now our main BFS implementation in C starts: Initially, we added the 1st Node in the queue (as we are going to start BFS from here). Then, implement a while loop that will run until the queue is non-empty or the variable ‘front’ is not equal to ‘back’. In the while loop, we will store the front element of the queue in the current variable and pop it from the queue. We will use for loop to find all the connected nodes of the current node which are not been visited yet and add them to the queue by marking them visited. As we add nodes only if they are not visited and remove them at each step, we will end the loop with an empty queue that indicates no more connected nodes are left.

Time and Space Complexity

If the graph or tree has N nodes, then by using the BFS algorithm, we can travel at most N-1 nodes and for each Node, there are N nodes that may or may not be connected to them and we have to look for them that implies time complexity of the BFS algorithm is O(N*N).
If the graph or tree has **N nodes**in the queue, we are not storing the repeated/revisited nodes, which means only N nodes can be maximum present in the queue. So, the Space complexity of the BFS algorithm in C is O(N).

Conclusion

BFS algorithm in C, also known as the Breadth-First Search algorithm is commonly used as a search algorithm in graphs, trees, multidimensional arrays, or in general recursion.
BFS program in C is implemented by using a queue data structure to perform the basic characteristic of the BFS algorithm that is traversing level-wise.
The queue is a linear data structure that works on the FIFO(First in First out) property.
The time complexity of the BFS algorithm in C is O(N*N) and the space complexity of BFS implementation in C is O(N), where N is the number of nodes.
The DFS algorithm has a chance of being stuck in an infinite search, and it may never provide a solution, but the BFS algorithm in C always provides the solution.