type
status
date
summary
tags
category
icon
password
featured
freq
difficulty
Breadth-First Search (BFS) is a traversal algorithm that explores all the neighbor nodes at the current depth level before moving on to the nodes at the next depth level. It explores the graph (or tree) layer by layer or level by level by using a queue (deque). The FIFO structure of the queue guarantees level-order traversal by enqueuing children of a node as it is discovered and processing the nodes in the order they arrived.
The “wavefront” property of BFS makes it perfect for:
- finding shortest paths in unweighted graphs (or equally weighted edges),
- computing minimum steps / distances on grids,
- doing layered traversals on trees (level order, zigzag, bottom-left value),
- answering “within k hops” queries.
Tree BFS
BFS traverses the tree level by level, visiting all nodes at the same depth before moving to the next. It uses a queue (
deque) to process nodes in first-in-first-out(FIFO) order, making it ideal for problems like level-order traversal, zigzag traversal, or finding the bottom-left value.
Since every node is processed exactly once, and a tree has 𝑛 − 1 edges for 𝑛 nodes, BFS takes O(n) time. And the space it uses is O(w), where 𝑤 is the maximum width of the tree (nodes at the widest level).
Shortest Distance to a Target Node
All edges have equal weight (e.g., distance = 1). BFS explores nodes in increasing distance order, ensuring the first time the target node is reached corresponds to the minimum number of steps or edges from the source.
Per-Level Loop: apply level-wise logic
When we need to apply level-wise logic, such as for level grouping, visual layouts, or get the last node per level, we can explicitly tracks the size of each level and groups nodes accordingly.
Example: Returns a nested list where each sublist contains values from the a level.
Grid / Matrix BFS
Grid / Matrix with cells as the nodes, 4- or 8-directional moves are edges of equal cost (1 step).
To ensure correctness: 1) bounds check prevents out-of-range access, 2) obstacle check skips invalid cells, 3)
visited tracking avoids revisiting nodes. BFS explores each cell and its neighbors once, resulting in O(m × n) time. And each cell is tracked and processed only once leading to O(m × n) space complexity for the visited matrix and queue.
Graph BFS
Graph BFS explores nodes in layers, starting from a source and visiting all its neighbors before moving to the next level.
It also uses a queue (FIFO) to ensure nodes are processed in the order they’re discovered, and a visited set to prevent revisiting.
BFS runs in O(V + E) time, where 𝑉 is the number of vertices and 𝐸 is the number of edges. Each node and edge is visited at most once, and it uses O(V) space for the visited set and queue. In dense graphs, the queue can grow large if many nodes are at the same level.
Shortest Distance to a Target Node
When finding the minimum distance, we often store the distance along with the node in the queue (e.g.,
(distance, node)).In graphs or matrices (grids), avisitedset is necessary to prevent cycles from causing infinite loops and to ensure O(V+E) complexity. Checkingvisitedbefore enqueuing a neighbor is the most common and efficient, as it ensures each node enters the queue exactly once.
Per-Layer Loop: apply layer-wise logic
This structure is necessary when you need to perform calculations that depend on the layer (distance), such as computing average values per layer or when the processing logic differs per layer.
Dijkstra's Algorithm (BFS + Heap)
Dijkstra's Algorithm is an extension of BFS tailored for finding the shortest path in a weighted graph (where edges have different costs/times). It swaps the standard FIFO queue for a Min-Heap (Priority Queue).
- Min-Heap: The heap ensures that the node with the current smallest tentative total distance from the source is always processed next. This maintains the "shortest path first" property of BFS, even with varying weights.
- Key Difference:
- BFS assumes every edge costs the same (e.g., 1 step). It uses a FIFO queue and nodes are finalized in increasing distance by levels. It check
visitedat enqueue is common, but checking at dequeue also work and they are equivalent. - Dijkstra handles positive weighted edges. It replaces the deque with a min-heap. It has to check
visitedupon dequeue, allowing a node enqueue multiple times, and uses a min-heap to ensure the smallest node is processed first at pop.
Time Complexity: O((V + E) * log V)
- Each node may be inserted and updated in the priority queue, and edges are relaxed once.
- Each of the V nodes may be inserted and updated in the heap → O(logV) per operation.
- Each of the E edges may trigger a relaxation (i.e., a priority update) → O(logV) per update.
Space Complexity: O(V + E) Stores the graph, distance array, and priority queue.
Endnote
Breadth-First Search (BFS) is the fundamental level-order exploration strategy—ideal whenever all moves have equal cost or when problems ask for the minimum number of steps.
The power of BFS lies in its use of a queue (+ visited), which ensures level-order traversal where each layer reflects increasing distance from the source. This pattern makes BFS highly adaptable—whether in trees, graphs, grids, or even arrays—for solving shortest paths, layer-based logic, and propagation problems with clarity and precision.
- Author:Fan Luo
- URL:https://fanluo.me/article/breadth-first-search-level-order-exploration
- Copyright:All articles in this blog adopt BY-NC-SA agreement. Please indicate the source!
上一篇
Depth-First Search: Exploring Deep Before Wide
下一篇
Understanding Recursion: Functions That Call Themselves