Graph Traversal Patterns 2026: BFS, DFS, Topological Sort [20+ Problems]

Last Updated: June 2026

Why Graph Problems Are High-Leverage

Candidates report graph problems as appearing in roughly 20-25% of FAANG coding rounds and approximately 10-15% of service company rounds, based on public preparation resources and candidate-reported interview threads from 2025 to 2026. The same BFS/DFS templates, applied correctly, solve problems across domains: social networks, maps, compilers, scheduling, and distributed systems.

The key insight: most graph problems reduce to one of six traversal patterns. Learn the pattern, apply it, adapt for constraints.

Graph Representation

# Adjacency List (most common)
graph = {
    0: [1, 2],
    1: [2],
    2: [0, 3],
    3: [3]
}

# For weighted graphs
graph = {
    0: [(1, 5), (2, 3)],   # (neighbor, weight)
    1: [(2, 2)],
    2: [(3, 1)]
}

# Grid as implicit graph
# Cell (r, c) has neighbors (r+1,c), (r-1,c), (r,c+1), (r,c-1)
DIRS = [(0, 1), (0, -1), (1, 0), (-1, 0)]

Pattern 1: BFS (Breadth-First Search)

Use for: Shortest path (unweighted), level-order, minimum steps, multi-source BFS.

from collections import deque

def bfs(graph, start):
    """
    Standard BFS template.
    Time: O(V + E)  Space: O(V)
    """
    visited = set([start])
    queue = deque([start])

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

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

Problem 1.1: Number of Islands (BFS)

Asked at: Amazon, Google, Microsoft, Facebook

def num_islands(grid):
    """
    BFS flood fill. Count connected components of '1's.
    Time: O(m*n)  Space: O(min(m,n)) for BFS queue
    """
    if not grid:
        return 0

    rows, cols = len(grid), len(grid[0])
    count = 0

    def bfs(r, c):
        queue = deque([(r, c)])
        grid[r][c] = '0'
        while queue:
            row, col = queue.popleft()
            for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
                nr, nc = row + dr, col + dc
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == '1':
                    grid[nr][nc] = '0'
                    queue.append((nr, nc))

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                bfs(r, c)
                count += 1

    return count

# Example
grid = [['1','1','0','0','0'],
        ['1','1','0','0','0'],
        ['0','0','1','0','0'],
        ['0','0','0','1','1']]
print(num_islands(grid))  # 3

Complexity: Time O(m*n), Space O(min(m,n))

Problem 1.2: Shortest Path in Binary Matrix

Asked at: Amazon, Google, Bloomberg

def shortest_path_binary_matrix(grid):
    """
    BFS from (0,0) to (n-1,n-1). 8-directional movement.
    Time: O(n^2)  Space: O(n^2)
    """
    n = len(grid)
    if grid[0][0] == 1 or grid[n-1][n-1] == 1:
        return -1

    queue = deque([(0, 0, 1)])  # row, col, path_length
    grid[0][0] = 1              # mark visited

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

    while queue:
        r, c, length = queue.popleft()

        if r == n - 1 and c == n - 1:
            return length

        for dr, dc in DIRS:
            nr, nc = r + dr, c + dc
            if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0:
                grid[nr][nc] = 1  # mark visited
                queue.append((nr, nc, length + 1))

    return -1

# Example
print(shortest_path_binary_matrix([[0,0,0],[1,1,0],[1,1,0]]))  # 4

Complexity: Time O(n^2), Space O(n^2)

Problem 1.3: Word Ladder (BFS on State Graph)

Asked at: Amazon, Google, Facebook - classic BFS state space

def ladder_length(begin_word, end_word, word_list):
    """
    BFS where state = word. Neighbor = words differing by 1 char.
    Time: O(M^2 * N) where M = word length, N = word list size
    Space: O(M^2 * N)
    """
    word_set = set(word_list)
    if end_word not in word_set:
        return 0

    queue = deque([(begin_word, 1)])
    visited = {begin_word}

    while queue:
        word, length = queue.popleft()

        for i in range(len(word)):
            for c in 'abcdefghijklmnopqrstuvwxyz':
                new_word = word[:i] + c + word[i+1:]
                if new_word == end_word:
                    return length + 1
                if new_word in word_set and new_word not in visited:
                    visited.add(new_word)
                    queue.append((new_word, length + 1))

    return 0

# Example
print(ladder_length("hit", "cog", ["hot","dot","dog","lot","log","cog"]))  # 5

Complexity: Time O(M^2 * N), Space O(M^2 * N)

Problem 1.4: Rotting Oranges (Multi-Source BFS)

Asked at: Amazon, Google, Uber

def oranges_rotting(grid):
    """
    Multi-source BFS starting from all rotten oranges simultaneously.
    Time: O(m*n)  Space: O(m*n)
    """
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh = 0

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c, 0))
            elif grid[r][c] == 1:
                fresh += 1

    max_time = 0

    while queue:
        r, c, t = queue.popleft()
        for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                grid[nr][nc] = 2
                fresh -= 1
                max_time = max(max_time, t + 1)
                queue.append((nr, nc, t + 1))

    return max_time if fresh == 0 else -1

# Example
print(oranges_rotting([[2,1,1],[1,1,0],[0,1,1]]))  # 4

Complexity: Time O(mn), Space O(mn)

Pattern 2: DFS (Depth-First Search)

Use for: Cycle detection, topological sort, connected components, path finding, backtracking.

def dfs(graph, node, visited):
    """
    Standard recursive DFS.
    Time: O(V + E)  Space: O(V) call stack
    """
    visited.add(node)
    print(node)  # process node

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

Problem 2.1: Number of Islands (DFS)

def num_islands_dfs(grid):
    """
    DFS flood fill. Modify grid to mark visited.
    Time: O(m*n)  Space: O(m*n) stack
    """
    if not grid:
        return 0

    rows, cols = len(grid), len(grid[0])
    count = 0

    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != '1':
            return
        grid[r][c] = '0'
        dfs(r+1, c); dfs(r-1, c); dfs(r, c+1); dfs(r, c-1)

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                dfs(r, c)
                count += 1

    return count

Problem 2.2: All Paths From Source to Target (DFS)

Asked at: Google, Amazon

def all_paths_source_target(graph):
    """
    DFS: track current path. Add to result when reaching last node.
    Time: O(2^V * V)  Space: O(V)
    """
    n = len(graph)
    result = []

    def dfs(node, path):
        if node == n - 1:
            result.append(list(path))
            return
        for neighbor in graph[node]:
            path.append(neighbor)
            dfs(neighbor, path)
            path.pop()

    dfs(0, [0])
    return result

# Example
print(all_paths_source_target([[1,2],[3],[3],[]])) # [[0,1,3],[0,2,3]]

Complexity: Time O(2^V * V), Space O(V)

Pattern 3: Cycle Detection

Directed Graph (DFS with coloring)

def has_cycle_directed(n, edges):
    """
    3-state DFS: 0=unvisited, 1=in-path, 2=done.
    Back edge (to in-path node) = cycle.
    Time: O(V+E)  Space: O(V)
    """
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)

    state = [0] * n

    def dfs(node):
        state[node] = 1   # in current path

        for neighbor in graph[node]:
            if state[neighbor] == 1:
                return True   # back edge = cycle
            if state[neighbor] == 0:
                if dfs(neighbor):
                    return True

        state[node] = 2   # done
        return False

    return any(dfs(i) for i in range(n) if state[i] == 0)

Undirected Graph

def has_cycle_undirected(n, edges):
    """
    DFS: cycle if visited neighbor is not the parent.
    Time: O(V+E)  Space: O(V)
    """
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)

    visited = [False] * n

    def dfs(node, parent):
        visited[node] = True
        for neighbor in graph[node]:
            if not visited[neighbor]:
                if dfs(neighbor, node):
                    return True
            elif neighbor != parent:
                return True
        return False

    return any(dfs(i, -1) for i in range(n) if not visited[i])

Pattern 4: Topological Sort

BFS (Kahn's Algorithm) - preferred in interviews

def topological_sort_bfs(n, prerequisites):
    """
    Kahn's: repeatedly remove nodes with in-degree 0.
    Time: O(V+E)  Space: O(V+E)
    """
    from collections import deque

    graph = [[] for _ in range(n)]
    in_degree = [0] * n

    for u, v in prerequisites:
        graph[v].append(u)
        in_degree[u] += 1

    queue = deque(i for i in range(n) if in_degree[i] == 0)
    order = []

    while queue:
        node = queue.popleft()
        order.append(node)

        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    return order if len(order) == n else []  # empty if cycle

Problem 4.1: Course Schedule (Cycle Detection via Topological Sort)

Asked at: Amazon, Google, Facebook, Microsoft

def can_finish(num_courses, prerequisites):
    """
    Can you complete all courses? = Is the graph a DAG?
    Use Kahn's - if topological order contains all nodes, no cycle.
    Time: O(V+E)  Space: O(V+E)
    """
    order = topological_sort_bfs(num_courses, prerequisites)
    return len(order) == num_courses

# Example
print(can_finish(2, [[1,0]]))        # True
print(can_finish(2, [[1,0],[0,1]]))  # False (cycle)

Problem 4.2: Course Schedule II (Return Order)

Asked at: Amazon, Google, Microsoft

def find_order(num_courses, prerequisites):
    """
    Return topological order or [] if cycle.
    Time: O(V+E)  Space: O(V+E)
    """
    return topological_sort_bfs(num_courses, prerequisites)

# Example
print(find_order(4, [[1,0],[2,0],[3,1],[3,2]]))  # [0, 1, 2, 3] or [0, 2, 1, 3]

Pattern 5: Connected Components

Undirected Graph

def count_components(n, edges):
    """
    Count connected components using DFS/Union-Find.
    Time: O(V+E)  Space: O(V+E)
    """
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)

    visited = [False] * n
    count = 0

    def dfs(node):
        visited[node] = True
        for neighbor in graph[node]:
            if not visited[neighbor]:
                dfs(neighbor)

    for i in range(n):
        if not visited[i]:
            dfs(i)
            count += 1

    return count

Problem 5.1: Number of Provinces (Connected Components)

Asked at: Amazon, Google, TCS

def find_circle_num(is_connected):
    """
    DFS over adjacency matrix.
    Time: O(n^2)  Space: O(n)
    """
    n = len(is_connected)
    visited = [False] * n
    provinces = 0

    def dfs(i):
        visited[i] = True
        for j in range(n):
            if is_connected[i][j] == 1 and not visited[j]:
                dfs(j)

    for i in range(n):
        if not visited[i]:
            dfs(i)
            provinces += 1

    return provinces

# Example
print(find_circle_num([[1,1,0],[1,1,0],[0,0,1]]))  # 2

Pattern 6: Shortest Path Algorithms

BFS for Unweighted Graphs

Already covered: BFS naturally gives shortest path in unweighted graphs.

Dijkstra for Weighted Graphs (No Negative Weights)

import heapq

def dijkstra(graph, start, n):
    """
    Heap-based Dijkstra.
    Time: O((V + E) log V)  Space: O(V)
    """
    dist = [float('inf')] * n
    dist[start] = 0
    heap = [(0, start)]  # (distance, node)

    while heap:
        d, u = heapq.heappop(heap)

        if d > dist[u]:
            continue

        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(heap, (dist[v], v))

    return dist

Problem 6.1: Network Delay Time

Asked at: Amazon, Google, Uber

def network_delay_time(times, n, k):
    """
    Dijkstra from source k. Answer = max distance (or -1 if unreachable).
    Time: O((V+E) log V)  Space: O(V+E)
    """
    import heapq

    graph = [[] for _ in range(n + 1)]
    for u, v, w in times:
        graph[u].append((v, w))

    dist = [float('inf')] * (n + 1)
    dist[k] = 0
    heap = [(0, k)]

    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(heap, (dist[v], v))

    max_dist = max(dist[1:])
    return max_dist if max_dist < float('inf') else -1

# Example
print(network_delay_time([[2,1,1],[2,3,1],[3,4,1]], 4, 2))  # 2

Complexity: Time O((V+E) log V), Space O(V+E)

BFS vs DFS Decision Guide

Complexity Summary

Common Mistakes

1. Not marking visited before pushing to BFS queue: Mark on push, not on pop, or you re-enqueue nodes.
2. Using visited set for topological sort instead of Kahn's: Kahn's naturally detects cycles via the remaining in-degree count.
3. Undirected cycle: forgetting to check parent: A visited node that is the parent does not constitute a cycle.
4. Dijkstra with negative edges: Use Bellman-Ford instead.

Related Articles

• Graph Questions Placement
• Union Find Questions 2026
• Tree Traversal Patterns 2026
• Dynamic Programming Patterns 2026
• Must-Do Coding Questions