What is Breadth First Search & how they works?

Last updated on January 5th, 2025 at 01:47 am

This article explores the Breadth First Search, its implementation in different programming languages, and its runtime complexities.

1. Graph Traversals

Graph traversal means visiting every vertex and edge exactly once in a well-defined order. During a traversal, you must track which vertices have been visited. The most common way of tracking vertices is to mark them

There are two such algorithms for traversing the graphs:

1. Breadth First Search (BFS)
2. Depth First Search (DFS)

2. What is Breadth First Search?

Breadth First Search (BFS) is a graph traversal algorithm that explores all the vertices of a graph layer by layer. Starting from a source node, BFS visits all its neighbors before moving on to the next level of neighbors. This systematic approach makes BFS ideal for finding the shortest path in unweighted graphs and solving problems like maze navigation, social network analysis, and more.

BFS is better choice if the solution closer to the top of the tree.

BFS works similarly to the level-order traversal of the trees. BFS works level by level. This algorithm is a generalization of the breadth-first traversal algorithm for binary trees. It uses a queue.

3. How Does Breadth First Search Work?

The algorithm uses a queue data structure to keep track of nodes to be visited. It follows these steps:

1. Start with the source node and mark it as visited.
2. Add the source node to the queue.
3. While the queue is not empty:
   • Dequeue a node.
   • Visit all its unvisited neighbors, mark them as visited, and enqueue them.

4. Breadth First Search Recursive vs Iterative

While BFS is typically implemented iteratively using a queue, it can also be implemented recursively. However, the recursive approach is less common due to the need for additional memory to manage the recursion stack.

5. Pseudo Code for Breadth First Search

Simple pseudo code for BFS:

BFS(graph, start_node):  
    Create a queue Q  
    Mark start_node as visited and enqueue it into Q  

    While Q is not empty:  
        node = Dequeue from Q  
        For each neighbor of node:  
            If neighbor is not visited:  
                Mark neighbor as visited  
                Enqueue neighbor into Q  

6. Breadth First Search in Different Programming Languages

6.1 Breadth First Search Java

In Java, BFS can be implemented using the Queue interface from the java.util package

import java.util.*;

public class BFS {
    public void bfsTraversal(int start, List<List<Integer>> graph) {
        boolean[] visited = new boolean[graph.size()];
        Queue<Integer> queue = new LinkedList<>();
        
        visited[start] = true;
        queue.add(start);
        
        while (!queue.isEmpty()) {
            int node = queue.poll();
            System.out.print(node + " ");
            
            for (int neighbor : graph.get(node)) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.add(neighbor);
                }
            }
        }
    }
}

6.2 Breadth First Search C++

C++ provides the queue container from the Standard Template Library (STL) for BFS implementation.

#include <iostream>
#include <vector>
#include <queue>

void bfs(int start, const std::vector<std::vector<int>>& graph) {
    std::vector<bool> visited(graph.size(), false);
    std::queue<int> q;
    
    visited[start] = true;
    q.push(start);
    
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        std::cout << node << " ";
        
        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }
}

6.3 Breadth First Search JavaScript

In JavaScript, BFS can be implemented using arrays to simulate a queue.

function bfs(graph, start) {
    let visited = new Array(graph.length).fill(false);
    let queue = [];
    
    visited[start] = true;
    queue.push(start);
    
    while (queue.length > 0) {
        let node = queue.shift();
        console.log(node);
        
        for (let neighbor of graph[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                queue.push(neighbor);
            }
        }
    }
}

7. Breadth First Search Time Complexity

The time complexity of Breadth First Search depends on the number of vertices (V) and edges (E) in the graph:

• Breadth First Search Best Case Runtime: O(V) (when the graph has no edges).
• Breadth First Search Average Case Runtime: O(V + E).
• Breadth First Search Worst Case Runtime: O(V + E) (when all vertices and edges are visited).

8. Applications of Breadth First Search

BFS has numerous applications in computer science, including:

• Network analysis: Used to find the shortest path between two nodes in a network.
• Web crawlers: Used to crawl the web and index web pages.
• Social media platforms: Used to recommend friends and find the shortest path between two users.

FAQs