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.
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:
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.
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 frontierProcess 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:
$$ \ \sum_{v=0}^{n} 1+deg(v)=|V|+|E| $$
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:
Use adjacency matrices when: