What is Breadth First Search (BFS) Algorithm for Graph?

Imagine you are going to your college from your home and want to choose the quickest path. Instead of randomly taking any route, you will check the closest turn that leads to your destination. This is exactly how Breadth-First Search works.

BFS is a graph traversal algorithm that starts from a selected point that we call a source node. From that source node, it explores its neighbour before moving further nodes, just like visiting everything at one layer before going to the next.

Table of Contents:

Graph traversal in data structure

We know that the graph is a data structure that represents the relationships between different elements. It is made up of nodes which are objects and edges which show the connection between the nodes.

Graph traversal is a way to visit all the nodes that are present in the graph. We start from one node and then explore the next node with the help of edges.

There are two different types of graph traversal algorithm that allows us to traverse the graph in a specific order.

1. Depth-First-Search (DFS): It first visits all nodes of one branch deeply and then considers the other nodes. It uses stack or recursion to keep an eye on nodes.

2. Breadth-First-Search (BFS): It first visits all the nodes that are present in the same level and then moves to the next level.

Breadth-First Search Algorithm

Breadth-first search is a traversal algorithm that allows us to explore all the neighbor nodes first and then visit the next neighbor nodes like traversing one level first and then moving to another. It uses a queue to check on the nodes (vertices).

For example, our starting point or source node of the graph below is 0. Let’s see how the BFS algorithm traverses the graph.

Step 1:

• Firstly, We will create an empty queue for checking neighbour nodes and an empty array to get a list of visited nodes (visited array).

Step 2:

• We will push the starting node (source node)  to the queue that is 0 in our case. We will also mark it as visited.

Step 3:

• Now we will remove zero from the front of the queue and visit the neighbour nodes and will push them into the queue, that is [1,2] in our case. Also, we will add them to the visited array.
• We will shift the front to node 1

Step 4:

• Now the front node in a queue is 1. We will push the next neighbour of 1 in the queue and add them to the visited array as well. In our case 3 is the next neighbour.
• We will shift the front to node 2.

Step 5:

• Now we will remove node 2 from the queue and visit the next unvisited node.
• Push them to the queue and also add them to the visited array.
• We will shift the front to node 3.

Step 6:

• Now we will remove node 3 from the queue and visit the next neighbour node.
• In our case, we have visited all the neighbors of node 3. So, now we can proceed with the next node in the queue.
• We will shift the front to node 4

Step 7:

• At last, we will remove node 4 from the queue and visit the neighbour nodes.
• Since there are no unvisited neighbours of node 4. We won’t add any new nodes to the queue.

Finally, We traversed all the nodes that are present in the graph and stored them in a visited array. That is [0,1,2,3,4].

Pseudocode

Below is the pseudocode for the BFS function.

BFS(graph, start_node):
    1. We will create an empty queue and enqueue the start_node(source node)
    2. We will mark start_node as visited
    3. While the queue is not empty: ( we will perform a loop)
        a. We will remove a node (current_node)
        b. For each neighbor of current_node: (we will perform an inner loop)
            i. If the neighbor node is not visited:
               - Add it to the visited array
               - Then push the neighbor into a queue

BFS implementation in C

Let’s see BFS implementation in C.

#include 
#include 
#define MAX 100

// Function to perform BFS traversal from a given starting node
void bfs(int adj[MAX][MAX], int V, int start) {
    int queue[MAX], front = 0, rear = 0; // Queue to manage BFS traversal
    bool visited[MAX] = { false };      // Array to track visited nodes

    visited[start] = true;              // Mark the starting node as visited (Bool -> True)
    queue[rear++] = start;              // Add the starting node to the queue

    // Continue until the queue is empty
    while (front < rear) {
        int current = queue[front++];   // Dequeue the next node
        printf("%d ", current);         // Print the current node

        // Check all vertices connected to the current node
        for (int i = 0; i < V; i++) {
            if (adj[current][i] && !visited[i]) {  // If connected and not visited
                visited[i] = true;                // Mark it as visited
                queue[rear++] = i;                // Add it to the queue
            }
        }
    }
}

// Function to add an edge between two node in an undirected graph
void addEdge(int adj[MAX][MAX], int u, int v) {
    adj[u][v] = adj[v][u] = 1;  // Update the adjacency matrix to indicate the connection
}

int main() {
    int V = 5;                  // Total number of vertices in the graph
    int adj[MAX][MAX] = {0};    // Initialize the adjacency matrix with all zeros

    // Define edges in the graph
    addEdge(adj, 0, 1);         // Add edge between vertex 0 and 1
    addEdge(adj, 0, 2);         // Add edge between vertex 0 and 2
    addEdge(adj, 1, 3);         // Add edge between vertex 1 and 3
    addEdge(adj, 1, 4);         // Add edge between vertex 1 and 4
    addEdge(adj, 2, 4);         // Add edge between vertex 2 and 4

    // Perform BFS starting from vertex 0
    printf("BFS starting from 0:\n");
    bfs(adj, V, 0);

    return 0;
}

Output:

BFS starting from 0:

0 1 2 3 4

Complexity Analysis of Breadth-First Search (BFS) Algorithm

1. Time Complexity of BFS

We know that in the worst-case scenario, the BFS algorithm will visit all the nodes and edges in the graph at least once. That is why the time complexity of BFS is O(V+E), here V and E are the number of nodes(vertices) and edges in a graph.

2. Space Complexity of BFS

Since BFS uses a queue to keep track of the nodes that we have not visited yet. In the worst-case scenario, the queue can store all the vertices in the graph. Hence, the space complexity of BFS is O(V).

Applications of BFS

The applications of BFS are mentioned below:

1. Shortest Path in Unweighted Graphs:
   • BFS ensures that we get the shortest route between the starting node and the goal node in an unweighted graph.
   • For example: Finding the shortest path to reach a restaurant.
2. Broadcasting the network:
   • BFS makes sure that all nodes are receiving the packages while performing network broadcasting simulation.
   • For example: Sending a message from one computer network to another.
3. Detect cycle in undirected graphs:
   • We are maintaining an array that allows us to keep track of visited nodes and their parent nodes.
4. Searching minimum spanning tree:
   • BFS can be part of algorithms (for example, Prim’s) working for finding minimum spanning trees in unweighted graphs.
5. Social Network Evaluation:
   • BFS helps to explore the connection between the users, which allows us to find the relation between two users( by checking the degree of separation)
   • For example: Finding mutual friends on Facebook.

Conclusion

BFS is one of the simplest but still powerful algorithms that allows us to traverse the graph layer by layer which makes it the best algorithm to find the shortest path in an unweighted graph. It is a structured approach that ensures every node is visited in a specific order, making it easy to understand the graph problem, whether you are trying to solve puzzles or navigating a map.

To deepen your understanding of algorithms like BFS and enhance your career in software engineering, enroll in our comprehensive software engineering course today.