Breadth-First Search (BFS)
BFS explores a graph level by level. It visits all neighbours of the starting node first, then all neighbours of those neighbours, and so on. Think of it as dropping a stone into a pond — the ripple expands outward in concentric circles.
- Queue (FIFO): Nodes are processed in the order they were discovered. Use
collections.dequefor O(1) popleft. - Visited set: Prevents revisiting nodes and infinite loops on cyclic graphs.
- Level-order: All nodes at distance d from the source are visited before any node at distance d+1.
BFS algorithm
- Create a queue and add the starting node. Mark it as visited.
- While the queue is not empty, dequeue the front node.
- Process the node (print it, check a condition, etc.).
- For each unvisited neighbour, mark it visited and enqueue it.
BFS Level-by-Level Expansion (starting from node 0)
Depth-First Search (DFS)
DFS explores a graph by going as deep as possible along each branch before backtracking. It picks one neighbour, dives all the way down that path, then comes back and tries the next neighbour. Think of it as exploring a maze — you follow one corridor to its end before trying another.
- Stack (LIFO): Either an explicit stack or the call stack via recursion. The last node discovered is the first one explored.
- Visited set: Same purpose as BFS — prevents infinite loops on cyclic graphs.
- Backtracking: When a dead end is reached, DFS pops back to the most recent node with unexplored neighbours.
DFS Depth-First Exploration (starting from node 0)
When to Use BFS vs DFS
| Aspect | BFS | DFS |
|---|---|---|
| Data structure | Queue (deque) |
Stack (explicit or call stack) |
| Exploration | Level by level (breadth) | Branch by branch (depth) |
| Shortest path | Yes (unweighted graphs) | No guarantee |
| Space complexity | O(V) — stores entire frontier | O(V) — stores current path |
| Best for | Shortest path, minimum moves, level-order | Connected components, cycle detection, topological sort |
| Time complexity | O(V + E) | O(V + E) |
BFS Implementation
Here is a clean BFS implementation using collections.deque. This version prints nodes in BFS order and can be adapted for shortest-path problems by tracking distances.
Complexity
- Time: O(V + E) — every vertex is enqueued once and every edge is examined once.
- Space: O(V) — the queue can hold up to V nodes in the worst case (e.g., a star graph).
DFS Implementation
DFS can be written recursively (elegant) or iteratively with an explicit stack (avoids stack overflow on large graphs). Here are both versions.
Recursive DFS
Iterative DFS
RecursionError. Use iterative DFS for production code or call sys.setrecursionlimit() in interviews (and mention the trade-off to your interviewer).
Complexity (both versions)
- Time: O(V + E) — every vertex is visited once and every edge is examined once.
- Space: O(V) — the stack (or call stack) holds at most V frames in the worst case (a linear chain).
Problem: Number of Islands
Given an m x n grid of '1' (land) and '0' (water), count the number of islands. An island is a group of '1's connected horizontally or vertically (not diagonally).
Approach: Scan the grid. When you find an unvisited '1', increment the island count and run DFS/BFS to mark all connected land cells as visited. This "flood fill" ensures each island is counted exactly once.
Complexity
- Time: O(m * n) — every cell is visited at most once.
- Space: O(m * n) — the visited set and recursion stack in the worst case (all land).
Problem: Shortest Path in a Maze
Given a 2D grid where 0 is an open cell and 1 is a wall, find the shortest path from (0, 0) to (rows-1, cols-1). You can move up, down, left, or right. Return the distance, or -1 if no path exists.
Why BFS? Every move costs 1 step, so the graph is unweighted. BFS guarantees the first time we reach the destination is via the shortest path.
Complexity
- Time: O(m * n) — each cell is visited at most once.
- Space: O(m * n) — the queue and visited set.
Problem: Course Schedule (Cycle Detection)
There are numCourses courses labelled 0 to numCourses - 1. Some have prerequisites: [a, b] means you must take course b before course a. Determine if it is possible to finish all courses (i.e., the prerequisite graph has no cycle).
Approach — 3-color DFS: Assign each node one of three states: WHITE (unvisited), GRAY (in the current DFS path), BLACK (fully explored). If DFS reaches a GRAY node, we have found a back edge — a cycle.
Why 3 colors, not just a visited set?
A simple visited set cannot distinguish between a node that is on the current path (a cycle) and a node that was fully explored in a previous DFS call (safe). The GRAY/BLACK distinction solves this. GRAY means "I am an ancestor of the current node" — revisiting it means a cycle. BLACK means "I was explored earlier and am definitely cycle-free."
Complexity
- Time: O(V + E) — each node and edge is visited once.
- Space: O(V + E) — adjacency list storage plus the color array and recursion stack.
Try It Yourself
Count the Number of Islands in a Grid
Given a 2D grid of '1' (land) and '0' (water), count the number of islands. An island is a group of '1's connected horizontally or vertically. The starter code has the function signature and test cases ready — implement the DFS flood-fill logic.
Challenge
Given a reference to a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node has a val and a list of neighbors. Use BFS or DFS and a hashmap to track original-to-clone mappings.
clone_map[node].neighbors.append(clone_map[neighbor]).Given beginWord, endWord, and a word list, find the length of the shortest transformation sequence from beginWord to endWord, where each step changes exactly one letter and the intermediate word must be in the word list. Return 0 if no such sequence exists.
Quiz
Common Mistakes
- Marking visited on dequeue instead of enqueue (BFS). This causes duplicate entries in the queue. A node can be added multiple times before it is dequeued, wasting time and potentially giving wrong shortest-path distances. Always mark visited the moment you add to the queue.
- Using a plain list as a queue.
list.pop(0)is O(n) because it shifts every remaining element. Usecollections.dequefor O(1) popleft. On large graphs this difference is the gap between passing and TLE. - Forgetting to handle disconnected graphs. Both BFS and DFS only reach nodes connected to the start. If the graph has multiple components, you must loop through all nodes and start a new traversal for each unvisited one (as in Number of Islands).
- Using a simple visited set for directed cycle detection. In a directed graph, a visited set cannot distinguish "on the current path" from "explored in a previous call". You need 3-color marking (WHITE/GRAY/BLACK). Using just a visited set works only for undirected graphs.
- Recursive DFS on deep graphs without raising the recursion limit. Python defaults to ~1000 stack frames. A chain of 5000 nodes will crash. Use iterative DFS with an explicit stack, or call
sys.setrecursionlimit()and mention the risk to your interviewer.
Key Takeaways
- BFS = queue, DFS = stack. BFS explores level by level (breadth-first); DFS dives deep before backtracking. Both are O(V + E) time and O(V) space.
- BFS guarantees shortest path in unweighted graphs. Any problem asking for "minimum steps", "nearest", or "shortest distance" on an unweighted graph should trigger BFS. DFS does not guarantee shortest path.
- DFS powers connected components and cycle detection. Flood-fill (Number of Islands), topological sort, and cycle detection (Course Schedule) are all DFS applications. The 3-color technique is essential for directed cycle detection.
- Always use a visited set. Without it, BFS and DFS will loop infinitely on cyclic graphs. Mark nodes visited at the right moment — on enqueue for BFS, on entry for DFS.
- Grid problems are graph problems in disguise. Each cell is a node; 4-directional movement defines edges. Number of Islands and Shortest Path in Maze are just BFS/DFS on an implicit graph.
You've mastered BFS & DFS.
Now build the career they unlock.
Join the Best AI Programs — three 5-month courses, fully online, with placement assistance. Week 1 is free.
Explore our AI-era courses →