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

Frequently Asked Questions

When should I use BFS vs DFS for graph problems?

Use BFS for shortest path (unweighted), level-order traversal, and finding minimum steps. Use DFS for cycle detection, topological sort, connected components, and path existence problems.

What is topological sort and when is it used?

Topological sort orders vertices in a DAG such that every edge (u, v) has u before v. Used for course scheduling, task dependencies, build systems, and any problem with prerequisite constraints.

How do you detect a cycle in a directed graph?

Use DFS with three states per node: unvisited (0), in current path (1), done (2). A back edge (node is in state 1 when visited again) indicates a cycle. For undirected graphs, a visited neighbor that is not the parent indicates a cycle.