Graphs: BFS, DFS, topological sort & shortest paths

A graph is the most general relational structure — nodes plus edges — and trees and lists are just special cases. The skill that wins interviews is recognizing the graph hiding in a problem; once you see the nodes and edges, the algorithm is one of a small handful.

Why this data structure

A graph is a set of nodes (vertices) and edges connecting them. Trees and linked lists are special cases (a tree is a connected acyclic graph; a list is a path). Once you model a problem as "nodes + relationships", graph traversal solves a huge class of questions: reachability, shortest path, ordering with dependencies, grouping connected things, cycle detection.

Many problems do not say "graph": a grid is a graph (each cell connects to its neighbors), a set of course prerequisites is a graph, word-ladder transformations are a graph. Once you see the nodes and edges, the algorithm is one of the handful below.

Representations

The implicit-grid framing is worth internalising: cell (r, c) connects to its 4 (or 8) neighbors, and you never build an adjacency list — you generate neighbors with direction vectors.

for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
    nr, nc = r + dr, c + dc

The two core traversals

• BFS (breadth-first, a queue): explores in rings of increasing distance from the source. The first time BFS reaches a node, it did so via the fewest edges — so BFS gives shortest paths in an unweighted graph or grid. Multi-source BFS seeds the queue with many starts at once (rotting oranges, nearest-exit).
• DFS (depth-first, a stack or recursion): plunges down one path fully before backtracking. Great for "explore an entire region" (connected components, islands, flood fill), cycle detection, and topological order.

Decision guide — when to use which

BFS — shortest path in an unweighted graph

BFS expands nodes in order of distance, so the first time we dequeue target we have found it via the fewest edges. Mark visited at enqueue time (not dequeue) to avoid pushing the same node multiple times.

def bfs_shortest_path(adj: Dict[int, List[int]],
                      source: int, target: int) -> int:
    if source == target:
        return 0
    visited: Set[int] = {source}
    q: deque = deque([(source, 0)])        # (node, distance)
    while q:
        node, dist = q.popleft()
        for nbr in adj.get(node, []):
            if nbr == target:
                return dist + 1
            if nbr not in visited:
                visited.add(nbr)           # mark on enqueue
                q.append((nbr, dist + 1))
    return -1

Grid BFS — grid-as-graph + direction vectors (LeetCode 1091 flavour)

Each open cell is a node; edges connect orthogonal neighbors. BFS from the start; the first time we reach the goal is the shortest path length. Direction vectors generate neighbors without ever materializing an adjacency list.

DIRS4 = [(-1, 0), (1, 0), (0, -1), (0, 1)]   # up, down, left, right

def grid_bfs_shortest(grid: List[List[int]]) -> int:
    R, C = len(grid), len(grid[0])
    if grid[0][0] != 0 or grid[R - 1][C - 1] != 0:
        return -1
    visited = {(0, 0)}
    q: deque = deque([(0, 0, 1)])          # (row, col, steps incl. this cell)
    while q:
        r, c, steps = q.popleft()
        if (r, c) == (R - 1, C - 1):
            return steps
        for dr, dc in DIRS4:
            nr, nc = r + dr, c + dc
            if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] == 0 \
                    and (nr, nc) not in visited:
                visited.add((nr, nc))
                q.append((nr, nc, steps + 1))
    return -1

Multi-source BFS — rotting oranges (LeetCode 994)

Here 0 = empty, 1 = fresh, 2 = rotten. Each minute, every rotten orange rots its 4-neighbours. Seed the BFS queue with all initially-rotten oranges at once (multi-source); each BFS "ring" is one minute of spreading. The number of rings is the answer; if any fresh orange is unreachable, return -1.

def oranges_rotting(grid: List[List[int]]) -> int:
    R, C = len(grid), len(grid[0])
    q: deque = deque()
    fresh = 0
    for r in range(R):
        for c in range(C):
            if grid[r][c] == 2:
                q.append((r, c))           # all rotten sources start together
            elif grid[r][c] == 1:
                fresh += 1
    minutes = 0
    while q and fresh > 0:
        minutes += 1
        for _ in range(len(q)):            # process one full minute's ring
            r, c = q.popleft()
            for dr, dc in DIRS4:
                nr, nc = r + dr, c + dc
                if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] == 1:
                    grid[nr][nc] = 2       # it rots
                    fresh -= 1
                    q.append((nr, nc))
    return -1 if fresh > 0 else minutes

DFS — connected components (LeetCode 323)

Build an adjacency list, then DFS from every unvisited node. Each DFS floods one entire component; the number of DFS launches equals the number of components. Shown here with an explicit-stack flood.

def count_components(n: int, edges: List[Tuple[int, int]]) -> int:
    adj: Dict[int, List[int]] = defaultdict(list)
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)                   # undirected -> both directions
    visited: Set[int] = set()

    def dfs(start: int) -> None:           # iterative flood of one component
        stack = [start]
        visited.add(start)
        while stack:
            node = stack.pop()
            for nbr in adj[node]:
                if nbr not in visited:
                    visited.add(nbr)
                    stack.append(nbr)

    components = 0
    for node in range(n):
        if node not in visited:
            components += 1
            dfs(node)
    return components

Number of islands (LeetCode 200) — DFS flood on a grid

Here '1' = land, '0' = water. Each island is a connected component of land cells (4-directional). Scan the grid; each time you hit an unvisited land cell, DFS-flood the whole island — marking cells visited by sinking them to '0' — and count one island.

def num_islands(grid: List[List[str]]) -> int:
    if not grid or not grid[0]:
        return 0
    R, C = len(grid), len(grid[0])

    def sink(r: int, c: int) -> None:      # iterative DFS flood
        stack = [(r, c)]
        grid[r][c] = "0"
        while stack:
            cr, cc = stack.pop()
            for dr, dc in DIRS4:
                nr, nc = cr + dr, cc + dc
                if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] == "1":
                    grid[nr][nc] = "0"     # mark visited by sinking
                    stack.append((nr, nc))

    islands = 0
    for r in range(R):
        for c in range(C):
            if grid[r][c] == "1":
                islands += 1
                sink(r, c)
    return islands

Flood fill (LeetCode 733) — recursive DFS region paint

Recolor the start pixel and every 4-connected pixel of the same original color. Plain DFS, where the "visited" marker is the recolor itself.

def flood_fill(image: List[List[int]], sr: int, sc: int,
               new_color: int) -> List[List[int]]:
    R, C = len(image), len(image[0])
    original = image[sr][sc]
    if original == new_color:
        return image                       # nothing to do; avoid looping

    def dfs(r: int, c: int) -> None:
        if not (0 <= r < R and 0 <= c < C) or image[r][c] != original:
            return
        image[r][c] = new_color
        for dr, dc in DIRS4:
            dfs(r + dr, c + dc)

    dfs(sr, sc)
    return image

Cycle detection — directed graph via 3-color DFS

Color each node WHITE (unvisited), GRAY (on the current DFS recursion path), or BLACK (fully explored). A back edge to a GRAY node means we returned to a node still on our active path — a cycle. Reaching a BLACK node is fine (already finished, no cycle through it).

def has_cycle_directed(n: int, edges: List[Tuple[int, int]]) -> bool:
    WHITE, GRAY, BLACK = 0, 1, 2
    adj: Dict[int, List[int]] = defaultdict(list)
    for u, v in edges:
        adj[u].append(v)                   # directed: only u -> v
    color = [WHITE] * n

    def dfs(u: int) -> bool:
        color[u] = GRAY                    # entering: on the active path
        for v in adj[u]:
            if color[v] == GRAY:
                return True                # back edge -> cycle
            if color[v] == WHITE and dfs(v):
                return True
        color[u] = BLACK                   # leaving: fully explored
        return False

    for node in range(n):
        if color[node] == WHITE and dfs(node):
            return True
    return False

Cycle detection — undirected graph via parent tracking

DFS while remembering where we came from (the parent). If we reach an already-visited neighbor that is not the parent, we have found a second way into that node — a cycle. The parent check is essential: the edge back to the parent is the one we just used, not a cycle.

def has_cycle_undirected(n: int, edges: List[Tuple[int, int]]) -> bool:
    adj: Dict[int, List[int]] = defaultdict(list)
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
    visited: Set[int] = set()

    def dfs(u: int, parent: int) -> bool:
        visited.add(u)
        for v in adj[u]:
            if v not in visited:
                if dfs(v, u):
                    return True
            elif v != parent:              # visited & not where we came from
                return True
        return False

    for node in range(n):
        if node not in visited and dfs(node, -1):
            return True
    return False

Topological sort — Kahn's algorithm (BFS by in-degree, LeetCode 210)

An edge u -> v means "u before v". A node with in-degree 0 has no unmet prerequisites, so it can go next. Repeatedly emit in-degree-0 nodes and decrement their successors' in-degrees; newly-zeroed nodes join the queue. If we emit fewer than n nodes, a cycle remained (those nodes never hit in-degree 0), and ordering is impossible.

def topo_sort_kahn(n: int, edges: List[Tuple[int, int]]) -> Optional[List[int]]:
    adj: Dict[int, List[int]] = defaultdict(list)
    indeg = [0] * n
    for u, v in edges:
        adj[u].append(v)
        indeg[v] += 1
    q: deque = deque(node for node in range(n) if indeg[node] == 0)
    order: List[int] = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in adj[u]:
            indeg[v] -= 1                  # one prerequisite satisfied
            if indeg[v] == 0:
                q.append(v)
    return order if len(order) == n else None   # short -> cycle

The DFS variant uses the fact that a node finishes (postorder) only after every node it can reach has finished. So the reverse postorder is a valid topological order; the 3-color trick detects a cycle along the way.

def topo_sort_dfs(n: int, edges: List[Tuple[int, int]]) -> Optional[List[int]]:
    WHITE, GRAY, BLACK = 0, 1, 2
    adj: Dict[int, List[int]] = defaultdict(list)
    for u, v in edges:
        adj[u].append(v)
    color = [WHITE] * n
    order: List[int] = []
    ok = True

    def dfs(u: int) -> None:
        nonlocal ok
        color[u] = GRAY
        for v in adj[u]:
            if color[v] == GRAY:
                ok = False                 # back edge -> cycle
            elif color[v] == WHITE:
                dfs(v)
        color[u] = BLACK
        order.append(u)                    # postorder: u finished

    for node in range(n):
        if color[node] == WHITE:
            dfs(node)
    if not ok:
        return None
    order.reverse()                        # reverse postorder = topo order
    return order

Dijkstra — shortest paths, non-negative weights

Greedily finalize the closest unfinalized node. A min-heap keyed by tentative distance always hands us that node next — the greedy invariant that makes Dijkstra correct, which relies on non-negative weights so finalized distances never improve later. Relax each outgoing edge, pushing improved distances. We skip stale heap entries (a popped distance worse than the best recorded) instead of doing a separate decrease-key.

def dijkstra(adj: Dict[int, List[Tuple[int, int]]],
             source: int) -> Dict[int, float]:
    dist: Dict[int, float] = {source: 0.0}
    heap: List[Tuple[float, int]] = [(0.0, source)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist.get(u, float("inf")):
            continue                       # stale; a better path was finalized
        for v, w in adj.get(u, []):
            nd = d + w
            if nd < dist.get(v, float("inf")):
                dist[v] = nd
                heapq.heappush(heap, (nd, v))
    return dist