Graph Traversal Patterns: BFS, DFS, Topological Sort, and Shortest Path

Graphs appear in a wide range of LeetCode problems: grid traversal, social networks, dependency ordering, shortest paths. Mastering BFS, DFS, topological sort, and Dijkstra gives you the tools to solve almost any graph problem. This guide provides templates and solutions for each pattern.

Graph Representation

from collections import defaultdict, deque

# Adjacency list (most common)
graph = defaultdict(list)
edges = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4)]
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)  # omit for directed graphs

# Adjacency matrix (use for dense graphs)
n = 5
matrix = [[0] * n for _ in range(n)]
for u, v in edges:
    matrix[u][v] = 1
    matrix[v][u] = 1

Pattern 1: BFS (Breadth-First Search)

BFS explores all neighbors at the current depth before moving deeper. Use it for shortest path in unweighted graphs and level-order traversal.

Template

def bfs(graph, start):
    visited = {start}
    queue = deque([start])
    
    while queue:
        node = queue.popleft()
        # Process node
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

Number of Islands (LC 200)

def numIslands(grid: list[list[str]]) -> int:
    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

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

Rotting Oranges (LC 994) — Multi-source BFS

def orangesRotting(grid: list[list[int]]) -> int:
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh = 0
    
    # Find all rotten oranges and count fresh ones
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c, 0))  # (row, col, time)
            elif grid[r][c] == 1:
                fresh += 1
    
    if fresh == 0:
        return 0
    
    max_time = 0
    while queue:
        r, c, time = 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 = time + 1
                queue.append((nr, nc, time + 1))
    
    return max_time if fresh == 0 else -1

Pattern 2: DFS (Depth-First Search)

DFS goes as deep as possible before backtracking. Use it for path finding, cycle detection, and connected components.

Template (Iterative and Recursive)

# Recursive DFS
def dfs_recursive(graph, node, visited):
    visited.add(node)
    # Process node
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)

# Iterative DFS
def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        # Process node
        for neighbor in graph[node]:
            if neighbor not in visited:
                stack.append(neighbor)

Clone Graph (LC 133)

class Node:
    def __init__(self, val=0, neighbors=None):
        self.val = val
        self.neighbors = neighbors if neighbors else []

def cloneGraph(node):
    if not node:
        return None
    
    cloned = {}
    
    def dfs(n):
        if n in cloned:
            return cloned[n]
        
        copy = Node(n.val)
        cloned[n] = copy
        
        for neighbor in n.neighbors:
            copy.neighbors.append(dfs(neighbor))
        
        return copy
    
    return dfs(node)

Cycle Detection in Directed Graph

def has_cycle_directed(n: int, edges: list[list[int]]) -> bool:
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
    
    # 0: unvisited, 1: in current path, 2: fully processed
    state = [0] * n
    
    def dfs(node):
        state[node] = 1  # visiting
        for neighbor in graph[node]:
            if state[neighbor] == 1:
                return True   # back edge = cycle
            if state[neighbor] == 0 and dfs(neighbor):
                return True
        state[node] = 2  # done
        return False
    
    return any(state[i] == 0 and dfs(i) for i in range(n))

Cycle Detection in Undirected Graph

def has_cycle_undirected(n: int, edges: list[list[int]]) -> bool:
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    
    visited = set()
    
    def dfs(node, parent):
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                if dfs(neighbor, node):
                    return True
            elif neighbor != parent:
                return True  # visited neighbor that is not parent = cycle
        return False
    
    return any(i not in visited and dfs(i, -1) for i in range(n))

Pattern 3: Topological Sort

Order nodes in a directed acyclic graph (DAG) so that every edge goes from earlier to later. Two approaches: Kahn’s algorithm (BFS) and DFS-based.

Kahn’s Algorithm (BFS)

def topological_sort_bfs(n: int, edges: list[list[int]]) -> list[int]:
    graph = defaultdict(list)
    in_degree = [0] * n
    
    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1
    
    # Start with all nodes that have no incoming edges
    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)
    
    # If order has all nodes, no cycle exists
    return order if len(order) == n else []

Course Schedule (LC 207)

def canFinish(numCourses: int, prerequisites: list[list[int]]) -> bool:
    graph = defaultdict(list)
    in_degree = [0] * numCourses
    
    for course, prereq in prerequisites:
        graph[prereq].append(course)
        in_degree[course] += 1
    
    queue = deque([i for i in range(numCourses) if in_degree[i] == 0])
    completed = 0
    
    while queue:
        node = queue.popleft()
        completed += 1
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    
    return completed == numCourses

print(canFinish(4, [[1,0],[2,0],[3,1],[3,2]]))  # True
print(canFinish(2, [[1,0],[0,1]]))               # False (cycle)

// Java version
public boolean canFinish(int numCourses, int[][] prerequisites) {
    List<List<Integer>> graph = new ArrayList<>();
    int[] inDegree = new int[numCourses];
    for (int i = 0; i < numCourses; i++) graph.add(new ArrayList<>());
    
    for (int[] pre : prerequisites) {
        graph.get(pre[1]).add(pre[0]);
        inDegree[pre[0]]++;
    }
    
    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < numCourses; i++)
        if (inDegree[i] == 0) queue.offer(i);
    
    int completed = 0;
    while (!queue.isEmpty()) {
        int node = queue.poll();
        completed++;
        for (int neighbor : graph.get(node)) {
            if (--inDegree[neighbor] == 0) queue.offer(neighbor);
        }
    }
    return completed == numCourses;
}

Pattern 4: Shortest Path (Dijkstra)

For weighted graphs with non-negative edges.

import heapq

def dijkstra(graph: dict, start: int, n: int) -> list[int]:
    dist = [float('inf')] * n
    dist[start] = 0
    heap = [(0, start)]  # (distance, node)
    
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue  # skip stale entries
        
        for v, weight in graph[u]:
            new_dist = dist[u] + weight
            if new_dist < dist[v]:
                dist[v] = new_dist
                heapq.heappush(heap, (new_dist, v))
    
    return dist

Network Delay Time (LC 743)

def networkDelayTime(times: list[list[int]], n: int, k: int) -> int:
    graph = defaultdict(list)
    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

print(networkDelayTime([[2,1,1],[2,3,1],[3,4,1]], 4, 2))  # 2

Quick Reference

Pattern	Use When	Time Complexity
BFS	Shortest path (unweighted), level-order	O(V + E)
DFS	Path finding, cycle detection, components	O(V + E)
Topological Sort	Dependency ordering, DAG processing	O(V + E)
Dijkstra	Shortest path (weighted, non-negative)	O((V + E) log V)

Key Takeaways

Use BFS for shortest path in unweighted graphs and any problem that requires level-by-level processing. Use DFS for exploring all paths, detecting cycles, and finding connected components. Use topological sort when you need to order tasks with dependencies. Use Dijkstra for shortest paths in weighted graphs. Most grid problems are graph problems where each cell is a node and edges connect to adjacent cells. Build the adjacency list first, then apply the appropriate traversal pattern.