BFS explores nodes level by level. Unlike DFS, which dives deep along one path, BFS visits all nodes at the current depth before moving to the next.

Think of BFS like ripples in a pond:

BFS applies to any structure that can be represented as a set of nodes and edges like trees, tries, graphs and 2D grids.

Here is how BFS traverses this tree:

Final BFS traversal order is: 1, 2, 3, 4, 5

BFS uses a queue to track which nodes to visit next and a visited set to avoid revisiting nodes. Enqueue the starting node, mark it visited, then repeatedly dequeue a node, process it, and enqueue its unvisited neighbors until the queue is empty.

The time complexity of BFS is O(V + E), where V is the number of vertices and E is the number of edges in the graph.

This is because each node is processed once when it is dequeued and each edge is examined at most twice in an undirected graph (once from each endpoint) and exactly once in a directed graph.

The space complexity of BFS is O(V) since, in the worst case, the queue and visited set can store up to V nodes.

In some BFS-related problems, you may have multiple starting nodes instead of just one. These are called multi-source BFS problems.

The only change compared to standard BFS is that we enqueue all starting nodes at the beginning and mark them as visited. Then run BFS as usual.

Time Complexity

The time complexity of BFS on a graph stored as an adjacency list is O(V + E), where V is the number of vertices and E is the number of edges. Every vertex enters the queue once and leaves it once, because the visited set blocks any second insertion, so the work tied to vertices adds up to O(V).

For each vertex that gets dequeued, BFS scans its adjacency list to find neighbors, and across the whole traversal those scans look at every edge once in a directed graph and once from each endpoint in an undirected graph, which adds up to O(E).

Combining the two gives O(V + E). When the graph is stored as an adjacency matrix instead, finding the neighbors of a vertex requires checking an entire row of V entries, so the traversal costs O(V^2).

Space Complexity

The space complexity of BFS is O(V). The queue can hold many vertices at once, since BFS keeps every vertex of the current frontier waiting to be processed, and in the worst case that frontier grows until it contains close to all V vertices.

The visited set also stores up to V vertices, because it records every vertex BFS has reached. Both structures are bounded by the number of vertices, so the total extra space is O(V).

Shortest Path

BFS finds the shortest path in an unweighted graph because it reaches every vertex through the fewest possible edges from the source, so the first time it touches a vertex it has already found the minimum number of steps to get there.

Level-Order Traversal

BFS produces the level-order traversal of a tree, visiting every node at one depth before any node at the next depth, which is exactly the order 1, 2, 3, 4, 5 used in the example above.

Connected Components

BFS finds the connected components of an undirected graph by starting a fresh traversal from each unvisited vertex, since one run reaches every vertex that can be linked to the starting point through edges.

Bipartite Check

BFS tests whether a graph is bipartite by coloring each vertex with one of two colors as it is discovered and giving every neighbor the opposite color, because a conflict between a vertex and an already colored neighbor means no valid two-coloring exists.

Flood Fill

BFS solves multi-source spread problems such as flood fill and computing the distance from each grid cell to its nearest source, since enqueuing all sources at once lets the frontier expand outward evenly and assign each cell the distance to the closest source.

Web-Crawling

BFS powers web crawling by treating pages as vertices and links as edges, so it can discover pages close to a seed URL before following links that lead further away.