The key use case of Breath-First Search is to find the shortest distance from one node to another.

More specifically, it solves the single source shortest path problem in the case where all edges are length 1 since it finds the shortest paths from a single starting node.

Working

Breadth-first search explores the vertices of a graph in layers in order of increasing distance from the starting vertex.

There are two ways to implement BFS. The key to BFS is the data structure we use:

1. Using a queue

   Maintain a FIFO queue of vertices to explore. Pop one vertex at a time, visit its neighbors, and enqueue any that haven’t been visited.

   This naturally processes vertices in increasing distance from the start.

2. Using Two Arrays (Level‑Synchronous BFS)

   Instead of a queue, maintain:

   • current[]: all vertices in the current BFS frontier (same distance from start)
   • next[]: all vertices discovered from the current frontier

   Process one “level” at a time.

   This is the level‑by‑level BFS used in parallel algorithms, GPUs, and distributed systems. This is because all vertices in current are processed independently.

The running time of BFS is \(O(|V|+|E|)\). It runs in linear time which is why it is incredibly fast.

This can be shown as follows. The loop has \(|V|\) iterations and for each iteration of the loop, we are going to do \(1 + deg(v)\) work. Now:

In the context of a general graph, the space complexity is \(O(|V|)\).

This is because the in the worst case, the queue may need to store all the vertices at a particular level, which can amount to all or nearly all vertices in the graph.

Warning

The complexity of DFS is different for adjacency matrices. This is because when you dequeue a node, you must scan the entire row of the matrix.

This leads to a complexity of \(O(V^2)\), regardless of how many edges actually exist.

Both adjacency matrices and lists behave the same logically, but the underlying representation changes the cost of enumerating neighbors.

Use adjacency lists when:

• Graph is sparse
• You want optimal BFS/DFS performance
• Memory matters

Use adjacency matrices when:

• Graph is dense
• You need constant‑time edge existence checks
• You’re doing algorithms like Floyd–Warshall or bitset‑optimized operations

Warning 2

We generally do not do BFS recursively (unlike DFS). It is more natural to deal with it iteratively.

Example Problems

When modelling scenarios to be able to use BFS, note that we don’t need to exactly copy the graph from the scenario. This is because the real graph might be too complicated. In all problems that involve BFS, we are always looking for ways to do two things:

• Reduce the number of times BFS is called
• Reduce the number of edges in the graph

Thus, before starting, always try to simplify the situation.

Here are some problems that can be tackled with BFS:

Shortest Path in Unweighted Graphs

• BFS guarantees the shortest path (fewest edges) between two nodes.
• Example: finding the minimum number of moves in a board game.

Connected Components

• Repeated BFS from unvisited nodes identifies all connected components.
• Useful in clustering, network analysis, and social graph segmentation.

Bipartite Graph Checking

• BFS can color nodes level by level.
• If a conflict arises (neighbor has same color), the graph is not bipartite.

Cycle Detection in Undirected Graphs

• BFS can detect cycles by checking if a visited neighbor is not the parent.

Level Order Traversal in Trees

• BFS naturally produces level-by-level traversal.
• Widely used in binary tree problems.

Cycle Detection

Having seen how to implement this using DFS, we will look into how we can do it using BFS:

BFS explores the graph level by level, ensuring that each node is visited in the shortest possible way. It also helps avoid deep recursion calls, making it more memory-efficient for large graphs.

In BFS, we also maintain a visited array to mark nodes that have been explored and a parent tracker to remember from which node we reached the current one.

If during traversal we encounter a node that is already visited and is not the parent of the current node, it means we’ve found a cycle in the graph.

Without information of which element is the parent, we cannot decide which nodes to ignore.

from collections import deque

# Function to perform BFS from node 'start' to detect cycle
def bfs(start, adj, visited):
    
    # Queue stores [current node, parent node]
    q = deque()
     
     # Start node has no parent
    q.append([start, -1])
    visited[start] = True

    while q:
        node = q[0][0]
        parent = q[0][1]
        q.popleft()

        # Traverse all neighbors of current node
        for neighbor in adj[node]:

            # If neighbor is not visited, mark it visited and push to queue
            if not visited[neighbor]:
                visited[neighbor] = True
                q.append([neighbor, node])
            # If neighbor is visited and not parent, a cycle is detected
            elif neighbor != parent:
                return True
    
    # No cycle found starting from this node
    return False

# Function to check if the undirected graph contains a cycle
def isCycle(adj):
    
    V = len(adj)
    
    # Keep track of visited vertices
    visited = [False] * V

    # Perform BFS from every unvisited node
    for i in range(V):
        if not visited[i]:
            
            # If BFS finds a cycle
            if bfs(i, adj, visited):
                return True
    
    # If no cycle is found in any component
    return False

Here is a comparision between the two algorithms:

In practice, if your goal is only cycle detection, DFS is the more efficient and elegant choice. BFS is better suited when cycle detection is a secondary task alongside shortest path or level‑order exploration.

Shortest Path

Whenever the goal is the find the shortest path to a solution, think of BFS. If the graph is unweighted, BFS is the ideal solution.

A simple extension is all that is needed to figure out the shortest path using BFS:

• Create a function \(l\) (usually in the form of a hash-table) that maps from vertices to unit edge lengths [this refers to each edge having length 1 as opposed to a weighted graph for which we would require Kruskal’s algorithm]
• Initialise the function with \(l(s) = 0\) where \(s\) is the starting vertex. For all other vertices \(v\), we have \(l(v)=\infin\)
• Update the shortest path function as \(l(v)=l(w)+1\) where the vertex \(v\) is reached from vertex \(w\).

Here are some problems where this comes in useful:

• Knight Chase: Moving a knight on a chessboard to reach a pawn is an excellent use case for BFS, where the least number of steps to reach any square on the chessboard can be mapped out with one run of the algorithm.
• Unlock the lock: We attempt to figure out the least number of turns to reach a given password, given a starting state and a list of nodes we are not allowed to visit. BFS applies because each edge is 1 turn and it is unweighted.

When modelling problems as a BFS problem, we need to make a choice of how we want to represent the graph: whether it is implicitly or explicitly encoded.

This is the transformation phase of problem solving where we convert our problem to a graph problem. If we explicitly construct the graph, the complexity will be on the order of the number of vertices and edges in the true problem space, which can be very large.

Thus, the better approach is always to build the graph implicitly. For BFS problems, we can handle this using a hash-table to handle seen distances/nodes. The expected run-times of this approach is better but in the worst case (under a scenario where all hashes collide) there is no change.

This idea can be applies to all of the example problems above.

Multi-Source Shortest Path (MSSP)

This uses the Multi-Source BFS algorithm which is a powerful but simple modification of

The problem is to find the shortest path given a list of possible source vertices. The shortest path is the shortest distance from any given source vertex.

There are multiple ways to think about it:

1. Do BFS starting from all nodes. This however, in the worst case, needs us to do BFS \(O(n)\) times leading to a time complexity of \(O(n (n+m))\).
2. Create a super-source node which connects to all nodes from which we can start. Then we run BFS but subtract 1 from the final distances to account for having started 1 node ahead.
3. Use the standard BFS algorithm but add all the source vertices into the queue at the beginning. In the initialization of the distances array, set the distances of all the source vertices as 0.

   This idea can be applied to Dijkstra as well.

Solutions 2 and 3 run in linear time because they are essentially just BFS.

Connected Components

Here is how BFS can be used to find all the connected components of a graph in linear time:

1. Maintain a array or set.
2. For each vertex :
   1. If is not visited, start a BFS from the vertex.
   2. All vertices reached by this BFS form one connected component.
3. Repeat until all vertices have been visited.

Even though we loop over all vertices and run BFS multiple times, each vertex is visited exactly once, and each edge is examined at most twice (once from each endpoint). This is why the time complexity remains \(O(|V| + |E|)\).

This can be applied to the following problems:

• Clustering: When we want to group nodes together based on similarities.
• Detecting network failures: This involves checking whether a network has become disconnected.
• Flood-Fill: If we want to set a particular attribute of all nodes in a connected component to a particular value. This algorithm to find connected components in a directed graph can be called flood-fill.
• Counting Connected Components: This is a simple adaptation of the algorithm used to find all connected components.

BFS with levels

When working with BFS, a useful augmentation to the algorithm that we can make is to keep track of levels. This is very common because it allows us to rewrite the BFS algorithm to solve some problems easier.

BFS-with-levels(Graph, start):
    create queue Q
    create array level[ ] initialized to -1
    level[start] = 0
    enqueue(start)

    while Q is not empty:
        u = dequeue(Q)
        for each neighbor v of u:
            if level[v] == -1:        // not visited yet
                level[v] = level[u] + 1
                enqueue(v)

Levels essentially encode the shortest path length from the source in an unweighted graph.

Example Problems

Shortest Path in an Unweighted Graph

Classic use case: levels directly give shortest path lengths. An example is finding the minimum number of moves in a maze/grid.

Another example of this problem is Word Ladder. You are given:

• A start word (e.g., "hit")
• An end word (e.g., "cog")
• A dictionary of valid words (e.g., ["hot","dot","dog","lot","log","cog"])

You can change exactly one letter at a time, and each intermediate word must exist in the dictionary. Find the minimum number of steps to transform the start word into the end word.

Bipartite Graph Checking

Assign levels to nodes; if an edge connects two nodes of the same level, the graph is not bipartite. Levels naturally partition the graph into two sets.

Seemingly non-graph problems

1. Minimum Swaps Needed to Sort an Array

• Graph model: Each element’s position can be seen as a node, with edges representing swaps.
• BFS explores swap states level by level until the sorted state is reached.
• Ensures minimal swaps because BFS finds the shortest path in the state graph.

2. MS Paint Fill Feature (Flood Fill)

• Graph model: Pixels are nodes, adjacency defined by neighboring pixels of the same color.
• BFS spreads outward from the starting pixel, filling connected regions.
• Guarantees complete coverage without recursion depth issues.

3. Class Size Allocations

• Graph model: Students as nodes, classes as bins, edges represent possible allocations.
• BFS can be used to explore feasible assignments level by level.
• Ensures fair distribution by finding minimal reassignments when constraints change.

4. Scheduling Problems

• Graph model: Tasks as nodes, dependencies as edges.
• BFS (topological-like traversal) ensures tasks are scheduled in dependency order.
• Level-by-level scheduling corresponds to parallelizable tasks.

5. Dependency Tracking and Resolution

• Graph model: Packages/modules as nodes, dependencies as directed edges.
• BFS resolves dependencies layer by layer.
• Ensures no module is processed before its prerequisites.