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.

🌊
Core mechanism
Queue + visited set = BFS
  • Queue (FIFO): Nodes are processed in the order they were discovered. Use collections.deque for 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

  1. Create a queue and add the starting node. Mark it as visited.
  2. While the queue is not empty, dequeue the front node.
  3. Process the node (print it, check a condition, etc.).
  4. For each unvisited neighbour, mark it visited and enqueue it.

BFS Level-by-Level Expansion (starting from node 0)

Level 0 Level 1 Level 2 0 visit 1st 1 visit 2nd 2 visit 3rd 3 visit 4th 4 visit 5th 5 visit 6th 6 visit 7th BFS visit order: 0 → 1 → 2 → 3 → 4 → 5 → 6 All of Level k is visited before any node at Level k+1
Visited (processed) In queue (discovered) Not yet reached
Why BFS finds shortest paths:
Because BFS visits nodes in order of increasing distance from the source, the first time it reaches a node is guaranteed to be via the shortest path (in an unweighted graph). This is why BFS is the go-to for "minimum moves" and "shortest distance" problems.

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.

🔍
Core mechanism
Stack (or recursion) + visited set = DFS
  • 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)

0 visit 1st 1 visit 2nd 3 visit 3rd 4 visit 4th 2 visit 5th 5 visit 6th 6 visit 7th DFS visit order: 0 → 1 → 3 → 4 → (backtrack) → 2 → 5 → 6 DFS dives deep (0→1→3) before backtracking to explore 4, then 2→5→6
Visited (fully explored) Backtracked to DFS traversal path

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)
Interview rule of thumb:
If the problem says "shortest", "minimum steps", or "nearest" — use BFS. If it says "all paths", "connected components", "cycle detection", or "topological order" — use DFS. Both are O(V + E), so the choice is about guarantees, not speed.

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.

BFS with deque Python
Output
BFS order: [0, 1, 2, 3, 4, 5, 6]
Critical detail:
Mark nodes as visited when you enqueue them, not when you dequeue them. If you wait until dequeue, multiple copies of the same node can end up in the queue, wasting time and potentially causing incorrect results in shortest-path calculations.

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

DFS — recursive Python
Output
DFS order: [0, 1, 3, 4, 2, 5, 6]

Iterative DFS

DFS — iterative with explicit stack Python
Output
DFS order: [0, 1, 3, 4, 2, 5, 6]
Recursion limit:
Python's default recursion limit is ~1000. For graphs with 10,000+ nodes in a chain, recursive DFS will crash with 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

🏝️
Classic interview problem
LeetCode 200 — asked at Amazon, Google, Meta

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.

Number of Islands — Grid DFS Python
Output
Number of islands: 3

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

🧭
BFS in action
Find the shortest path from top-left to bottom-right

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.

Shortest Path in Maze — BFS Python
Output
Shortest path: 6 Shortest path: -1

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)

📚
DFS cycle detection
LeetCode 207 — asked at Google, Amazon, Microsoft

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.

Course Schedule — DFS Cycle Detection (3-color) Python
Output
True False False

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

Push yourself further
Challenge 1: Clone Graph (LeetCode 133)

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.

Use a dictionary mapping original nodes to their clones. BFS approach: start from the given node, create its clone, add to queue. For each node you dequeue, iterate its neighbours. If a neighbour has no clone yet, create one and enqueue the original. Always connect clone_map[node].neighbors.append(clone_map[neighbor]).
Challenge 2: Word Ladder (LeetCode 127)

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.

Model this as a BFS problem: each word is a node, and two words are connected if they differ by exactly one letter. Use BFS from beginWord. To find neighbours efficiently, for each word try replacing each character with 'a' through 'z' and check if the result is in a set of remaining words. Remove words from the set when visited to avoid revisiting.

Quiz

Question 1 of 5
Which data structure does BFS use to determine the order of node exploration?
Question 2 of 5
Why does BFS guarantee the shortest path in an unweighted graph?
Question 3 of 5
In the 3-color DFS cycle detection, what does a GRAY node represent?
Question 4 of 5
What is the time complexity of the "Number of Islands" solution on an m x n grid?
Question 5 of 5
When should you mark a node as visited in BFS?
0
/5
Great work! You understand BFS & DFS.

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. Use collections.deque for 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.
Africa & India's Best AI Academy
🤖 AI-first 🎓 Placement Assistance

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 →