Lesson 13 of 16 Graphs

Graph BFS, DFS and Topological Sort

Graph traversal patterns: DFS for connected regions (number of islands), BFS for shortest paths in grids, and topological sort with Kahn's algorithm.

45-55 min intermediate 0/16 lessons done
Course contents Lesson 13 of 16 · 0 done
On this page (7 sections)
  1. What you will learn
  2. Signals
  3. Code
  4. BFS or DFS?
  5. Key takeaways
  6. Exercises
  7. Quiz

What you will learn

  • How to see a grid or a dependency list as a graph.
  • DFS for regions, BFS for fewest steps.
  • Topological sort with Kahn’s algorithm, and cycle detection for free.

Signals

  • Grids where cells connect to neighbours: islands, flood fill, rotting oranges, mazes.
  • “Prerequisites”, “build order”, “dependencies”, “can all tasks finish?” → topological sort.
  • “Minimum number of steps/moves” with equal-cost moves → BFS.

Code

"""Graph BFS/DFS on grids and adjacency lists, plus topological sort (Kahn)."""
from collections import deque


def count_islands(grid):
    rows, cols = len(grid), len(grid[0])
    seen = set()

    def dfs(r, c):
        stack = [(r, c)]  # iterative DFS avoids recursion limits on big grids
        while stack:
            r, c = stack.pop()
            for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == "1" and (nr, nc) not in seen:
                    seen.add((nr, nc))
                    stack.append((nr, nc))

    islands = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1" and (r, c) not in seen:
                seen.add((r, c))
                dfs(r, c)
                islands += 1
    return islands


def shortest_path_grid(grid, start, goal):
    """BFS: fewest steps in an unweighted grid ('#' is a wall)."""
    rows, cols = len(grid), len(grid[0])
    q, dist = deque([start]), {start: 0}
    while q:
        r, c = q.popleft()
        if (r, c) == goal:
            return dist[(r, c)]
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] != "#" and (nr, nc) not in dist:
                dist[(nr, nc)] = dist[(r, c)] + 1
                q.append((nr, nc))
    return -1


def course_order(n, prerequisites):
    """Kahn's algorithm. Returns an order, or [] if there's a cycle."""
    graph = [[] for _ in range(n)]
    indegree = [0] * n
    for course, pre in prerequisites:
        graph[pre].append(course)
        indegree[course] += 1
    q = deque(i for i in range(n) if indegree[i] == 0)
    order = []
    while q:
        node = q.popleft()
        order.append(node)
        for nxt in graph[node]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                q.append(nxt)
    return order if len(order) == n else []


if __name__ == "__main__":
    grid = ["11000",
            "11000",
            "00100",
            "00011"]
    print(count_islands(grid))
    maze = ["..#.",
            ".##.",
            "....",
            "#.#."]
    print(shortest_path_grid(maze, (0, 0), (0, 3)))
    print(course_order(4, [[1, 0], [2, 0], [3, 1], [3, 2]]), course_order(2, [[0, 1], [1, 0]]))

Output:

3
7
[0, 1, 2, 3] []
  • Islands: scan every cell; each unvisited land cell starts a DFS that marks its whole island. Mark cells as seen when you push them, so nothing is pushed twice. An explicit stack avoids Python’s recursion limit on large grids.
  • Shortest path in a grid: BFS explores in rings of equal distance, so the first time it reaches the goal is the fewest steps (7 here, around the walls).
  • Course order: Kahn’s algorithm repeatedly takes nodes with no remaining prerequisites. If some nodes are never taken, they sit on a cycle, so no valid order exists (the second call returns []).

BFS or DFS?

QuestionUse
Fewest steps, all moves cost the sameBFS
Visit everything / count components / detect regionsEither (DFS is often shorter)
Order with dependenciesTopological sort (Kahn BFS or DFS post-order)
Weighted edgesDijkstra
Connectivity as edges arriveUnion-find

Multi-source BFS: when the question is “distance from the nearest X” (rotting oranges, walls and gates), push every source into the queue at the start.

Practise: graph BFS/DFS, topological sort and matrix problems.

Key takeaways

  • Grids are graphs with up to four neighbours per cell.
  • Mark visited when pushing, not when popping, to avoid duplicates.
  • BFS gives fewest steps for unweighted moves; multi-source BFS gives nearest distances.
  • Kahn’s algorithm yields a topological order and detects cycles when nodes remain.

Exercises

  1. Rotting oranges with multi-source BFS.
  2. Clone a graph given as adjacency lists.
  3. Pacific Atlantic water flow: BFS backwards from both oceans.

Quiz

  1. Why does BFS find the shortest path in an unweighted graph?
  2. How does Kahn’s algorithm detect a cycle?
  3. Why mark a cell visited when pushing rather than when popping?
Show answers
  1. It visits nodes in order of distance; the first time a node is reached is via a path with the fewest edges.
  2. Nodes on a cycle never reach in-degree 0, so the output order has fewer than n nodes.
  3. Otherwise the same cell can be pushed many times by different neighbours before it’s processed, wasting time and memory.

Finished this lesson?

Mark it complete to track your progress (saved in this browser).