The Graph Traversal Question That Trips Up Senior Engineers

Graph traversal trips up senior engineers not because they don't know BFS and DFS, but because they miss that the problem is a graph at all. This is the written companion to the video — four snippets, in the order they appear on screen: the BFS template, the number of islands solution, the DFS template, and the course schedule cycle-detection solution.

BFS template

The skeleton to have memorized. Visited set initialized before the loop, nodes marked visited when they're added to the queue (not when they're processed), and popleft on a deque instead of pop on a list, since popleft is O(1).

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)

    while queue:
        node = queue.popleft()
        # process node here

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

Number of islands (BFS)

Given an m by n grid of 0s and 1s, count the number of islands — groups of connected 1s, connected horizontally or vertically.

def numIslands(grid):
    if not grid:
        return 0

    rows, cols = len(grid), len(grid[0])
    visited = set()
    islands = 0

    def bfs(r, c):
        queue = deque([(r, c)])
        visited.add((r, c))

        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        while queue:
            row, col = queue.popleft()
            for dr, dc in directions:
                nr, nc = row + dr, col + dc
                if (nr, nc) not in visited \
                   and 0 <= nr < rows \
                   and 0 <= nc < cols \
                   and grid[nr][nc] == "1":
                    queue.append((nr, nc))
                    visited.add((nr, nc))

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1" and (r, c) not in visited:
                bfs(r, c)
                islands += 1

    return islands

The outer loop handles disconnected islands — every unvisited "1" starts a fresh BFS. This pattern transfers directly to number of connected components, flood fill, and Pacific Atlantic water flow.

DFS template

Same shape as BFS, but recursion replaces the queue, and the visited check happens at the top of the function rather than before the recursive call.

def dfs(graph, node, visited):
    if node in visited:
        return
    visited.add(node)
    # process node here

    for neighbor in graph[node]:
        dfs(graph, neighbor, visited)

Course schedule (DFS cycle detection)

Given numCourses and a list of prerequisite pairs [course, prereq], determine whether it's possible to finish all courses — i.e., whether the prerequisite graph has a cycle. This is the problem where DFS isn't just an option, it's the natural tool: the recursion call stack is the current path, so checking "is this node an ancestor of itself" falls out of the traversal for free.

def canFinish(numCourses, prerequisites):
    graph = {i: [] for i in range(numCourses)}
    for course, prereq in prerequisites:
        graph[course].append(prereq)

    # 0 = unvisited, 1 = in current path, 2 = fully cleared
    state = [0] * numCourses

    def dfs(course):
        if state[course] == 1:
            return False  # back edge -- cycle found
        if state[course] == 2:
            return True   # already verified safe

        state[course] = 1
        for prereq in graph[course]:
            if not dfs(prereq):
                return False
        state[course] = 2
        return True

    return all(dfs(course) for course in range(numCourses))

The three states are the key idea — a plain visited set only tells you "have I seen this node ever." Here you need to track whether a node is currently in the path, which state 1 represents. This is also fundamental to topological sort: append each node to a result list after marking it state 2, and it becomes a Course Schedule II solution.