Graph algorithms are among the most versatile tools in competitive programming and coding interviews. A graph is simply a collection of nodes (vertices) connected by edges, and nearly every “network,” “grid,” or “relationship” problem maps onto one. This page provides production-ready Python templates for the most common graph patterns — from basic traversal to advanced connectivity — so you can focus on modeling the problem rather than re-deriving algorithms from scratch. All templates are 0-indexed unless noted.

New to Graphs? A graph consists of nodes (things) connected by edges (relationships between things). Most graph problems on LeetCode reduce to one of three categories: traversal (BFS/DFS — explore or find shortest paths), shortest paths with weights (Dijkstra, Bellman-Ford), or connectivity / ordering (Union-Find, Topological Sort). If you can identify which category your problem falls into, you’re halfway to the solution.

Graph Problem? Unweighted edges? Ordering with dependencies? Connected components? BFS Topological Sort DSU or DFS Weighted edges? Dijkstra (non-negative) Bellman-Ford (negative allowed) ↓ weighted? see below

Contents

BFS (unweighted)

When to use: “shortest path” or “minimum steps” on a grid or unweighted graph; “nearest exit”; “level-order traversal.”

Grid: 4-directional. Use for shortest path when all edges have weight 1.

from collections import deque


def bfs_grid(g: list[str], s: tuple[int, int], t: tuple[int, int]) -> int:
    m, n = len(g), len(g[0])
    q = deque([s])
    dist = [[-1] * n for _ in range(m)]
    dist[s[0]][s[1]] = 0
    dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]

    while q:
        x, y = q.popleft()
        if (x, y) == t:
            return dist[x][y]
        for dx, dy in dirs:
            nx, ny = x + dx, y + dy
            if 0 <= nx < m and 0 <= ny < n and g[nx][ny] != "#" and dist[nx][ny] == -1:
                dist[nx][ny] = dist[x][y] + 1
                q.append((nx, ny))
    return -1
ID Title Link
200 Number of Islands Link
542 01 Matrix Link

Multi-source BFS

When to use: “distance from nearest X”; “spread from multiple starting points simultaneously”; “rotting oranges” or “fire spreading” patterns.

Start from multiple nodes (distance 0). Same as BFS with initial queue containing all sources.

from collections import deque


def multi_source_bfs(g: list[str], sources: list[tuple[int, int]]) -> int:
    m, n = len(g), len(g[0])
    q = deque()
    dist = [[-1] * n for _ in range(m)]

    for x, y in sources:
        dist[x][y] = 0
        q.append((x, y))

    dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    best = 0
    while q:
        x, y = q.popleft()
        for dx, dy in dirs:
            nx, ny = x + dx, y + dy
            if 0 <= nx < m and 0 <= ny < n and g[nx][ny] != "#" and dist[nx][ny] == -1:
                dist[nx][ny] = dist[x][y] + 1
                best = max(best, dist[nx][ny])
                q.append((nx, ny))
    return best
ID Title Link
994 Rotting Oranges Link
286 Walls and Gates Link

BFS with state (bitmask)

When to use: “visit all nodes/keys”; “shortest path visiting a subset”; state changes at each step (e.g., collecting keys unlocks doors).

State = (node, mask). Use when “visit all keys” or “visit all nodes” is part of the goal.

from collections import deque


def bfs_mask(g: list[list[int]], start: int) -> int:
    n = len(g)
    full = (1 << n) - 1
    q = deque([(start, 1 << start, 0)])  # node, mask, distance
    seen = {(start, 1 << start)}

    while q:
        u, mask, d = q.popleft()
        if mask == full:
            return d
        for v in g[u]:
            m2 = mask | (1 << v)
            state = (v, m2)
            if state not in seen:
                seen.add(state)
                q.append((v, m2, d + 1))
    return -1
ID Title Link
847 Shortest Path Visiting All Nodes Link
864 Shortest Path to Get All Keys Link

Topological sort (Kahn)

When to use: “course prerequisites”; “build order”; “can I finish all tasks?”; finding a valid ordering of a DAG; cycle detection in directed graphs.

Indegree-based. Edge (u, v) means u before v. Returns order or empty if cycle.

① Compute indegrees ② Process A, B ③ Process C, D A 0 B 0 C 2 D 1 Queue: A B Output: [ ] A ✓ B ✓ C 2→0 D 1 Queue: C Output: [A, B] A B C D Queue: (empty) Output: [A, B, C, D] ✓ 
from collections import deque


def topo_kahn(n: int, g: list[list[int]]) -> list[int]:
    indeg = [0] * n
    for u in range(n):
        for v in g[u]:
            indeg[v] += 1

    q = deque(i for i in range(n) if indeg[i] == 0)
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in g[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return order if len(order) == n else []
ID Title Link
207 Course Schedule Link
210 Course Schedule II Link
269 Alien Dictionary Link

Topological sort (DFS)

When to use: Same as Kahn’s, but preferred when you also need cycle detection via back-edges; “find all safe states”; problems where DFS post-order gives useful structure.

Three colors: 0 unvisited, 1 visiting, 2 done. Push to order when finishing. Reverse = topo order. Back edge (neighbor color 1) = cycle.

import heapq


def dijkstra(n: int, g: list[list[tuple[int, int]]], s: int) -> list[int]:
    INF = 10**18
    dist = [INF] * n
    dist[s] = 0
    pq = [(0, s)]

    while pq:
        d, u = heapq.heappop(pq)
        if d != dist[u]:
            continue
        for v, w in g[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist
ID Title Link
802 Find Eventual Safe States Link

Dijkstra

When to use: “shortest path” with non-negative weights; “minimum cost to reach destination”; “network delay time”; any weighted graph where all weights ≥ 0.

Nonnegative weights. Adjacency list: g[u] = [(v, w), …]. Returns distances from source s.

4 1 2 3 7 S dist: 0 A dist: ∞ B dist: ∞ C dist: ∞ Edges: S→A(4), S→B(1), B→A(2), A→C(3), B→C(7) Process S (dist 0) Relax S→A: dist[A] = 0+4 = 4 Relax S→B: dist[B] = 0+1 = 1 PQ: {(1, B), (4, A)} dist: [S=0, A=4, B=1] Process B (dist 1) ★ B→A: 1+2=3 < 4 — relaxed! Relax B→C: dist[C] = 1+7 = 8 PQ: {(3, A), (8, C)} dist: [S=0, B=1, A=3, C=8] Process A (dist 3) ★ A→C: 3+3=6 < 8 — relaxed! PQ: {(6, C)} Final: S=0, B=1, A=3, C=6 
from collections import deque


def zero_one_bfs(n: int, g: list[list[tuple[int, int]]], s: int) -> list[int]:
    INF = 10**18
    dist = [INF] * n
    dist[s] = 0
    dq = deque([s])

    while dq:
        u = dq.popleft()
        for v, w in g[u]:  # w must be 0 or 1
            nd = dist[u] + w
            if nd < dist[v]:
                dist[v] = nd
                if w == 0:
                    dq.appendleft(v)
                else:
                    dq.append(v)
    return dist
ID Title Link
743 Network Delay Time Link
1976 Number of Ways to Arrive at Destination Link
3112 Minimum Time to Visit Disappearing Nodes Link
3341 Find Minimum Time to Reach Last Room I Link
3342 Find Minimum Time to Reach Last Room II Link

Variant: nodes disappear at given times (3112). Only relax edge ((u,v)) if dist[u] + w < disappear[v].

def find_bridges(n: int, g: list[list[int]]) -> list[tuple[int, int]]:
    tin = [-1] * n
    low = [-1] * n
    timer = 0
    bridges = []

    def dfs(u: int, p: int) -> None:
        nonlocal timer
        tin[u] = low[u] = timer
        timer += 1

        for v in g[u]:
            if v == p:
                continue
            if tin[v] != -1:
                low[u] = min(low[u], tin[v])
            else:
                dfs(v, u)
                low[u] = min(low[u], low[v])
                if low[v] > tin[u]:
                    bridges.append((u, v))

    for i in range(n):
        if tin[i] == -1:
            dfs(i, -1)
    return bridges

Variant: grid with earliest-entry times (3341). Moving costs 1, but you may need to wait to enter the next cell: [ \text{nextTime} = \max(\text{curTime},\ \text{open}[ni][nj]) + 1 ]

import heapq


def dijkstra_grid_open(open: list[list[int]]) -> int:
    n, m = len(open), len(open[0])
    INF = 10**18
    dist = [[INF] * m for _ in range(n)]
    dist[0][0] = 0
    pq = [(0, 0, 0)]  # (time, i, j)
    dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    while pq:
        t, i, j = heapq.heappop(pq)
        if t != dist[i][j]:
            continue
        if i == n - 1 and j == m - 1:
            return t
        for di, dj in dirs:
            ni, nj = i + di, j + dj
            if ni < 0 or ni >= n or nj < 0 or nj >= m:
                continue
            nt = max(t, open[ni][nj]) + 1
            if nt < dist[ni][nj]:
                dist[ni][nj] = nt
                heapq.heappush(pq, (nt, ni, nj))
    return dist[n - 1][m - 1]

0-1 BFS

When to use: Edge weights are only 0 or 1; “minimum flips/changes to reach target”; grid problems where some moves are free and others cost 1.

Weights 0 or 1. Deque: push front for 0, back for 1. O(V + E).

from collections import deque


def bfs01(n: int, g: list[list[tuple[int, int]]], s: int) -> list[int]:
    dist = [10**9] * n
    dist[s] = 0
    dq = deque([s])
    while dq:
        u = dq.popleft()
        for v, w in g[u]:
            nd = dist[u] + w
            if nd < dist[v]:
                dist[v] = nd
                if w == 0:
                    dq.appendleft(v)
                else:
                    dq.append(v)
    return dist

Bellman-Ford (k edges)

When to use: “cheapest flight within K stops”; shortest path with a constraint on number of edges; negative edge weights allowed; detecting negative cycles.

Relax all edges up to k times. Use when path length (number of edges) is limited.

def bellman_ford_k(
    n: int, edges: list[tuple[int, int, int]], src: int, k: int
) -> list[int]:
    INF = 10**18
    dist = [INF] * n
    dist[src] = 0
    for _ in range(k + 1):
        ndist = dist[:]
        for u, v, w in edges:
            if dist[u] != INF and dist[u] + w < ndist[v]:
                ndist[v] = dist[u] + w
        dist = ndist
    return dist
ID Title Link
787 Cheapest Flights Within K Stops Link

Tarjan (SCC / bridges)

When to use: “critical connections”; “articulation points”; “strongly connected components”; finding bridges whose removal disconnects the graph.

SCC: same low-link = same component. Bridges: edge (u,v) is bridge iff low[v] > tin[u].

class Tarjan:
    def __init__(self, n: int):
        self.n = n
        self.timer = 0
        self.g = [[] for _ in range(n)]
        self.tin = [-1] * n
        self.low = [0] * n
        self.comp = [-1] * n
        self.st: list[int] = []
        self.in_stack = [False] * n
        self.ncomp = 0

    def add(self, u: int, v: int) -> None:
        self.g[u].append(v)

    def dfs(self, u: int) -> None:
        self.tin[u] = self.low[u] = self.timer
        self.timer += 1
        self.st.append(u)
        self.in_stack[u] = True
        for v in self.g[u]:
            if self.tin[v] == -1:
                self.dfs(v)
                self.low[u] = min(self.low[u], self.low[v])
            elif self.in_stack[v]:
                self.low[u] = min(self.low[u], self.tin[v])
        if self.low[u] == self.tin[u]:
            while True:
                v = self.st.pop()
                self.in_stack[v] = False
                self.comp[v] = self.ncomp
                if v == u:
                    break
            self.ncomp += 1

    def run(self) -> int:
        for i in range(self.n):
            if self.tin[i] == -1:
                self.dfs(i)
        return self.ncomp


# Bridges: during dfs, if low[v] > tin[u] then (u, v) is a bridge
def bridges(n: int, g: list[list[int]]) -> list[tuple[int, int]]:
    timer = 0
    tin = [-1] * n
    low = [0] * n
    out: list[tuple[int, int]] = []

    def dfs(u: int, p: int) -> None:
        nonlocal timer
        tin[u] = low[u] = timer
        timer += 1
        for v in g[u]:
            if tin[v] == -1:
                dfs(v, u)
                low[u] = min(low[u], low[v])
                if low[v] > tin[u]:
                    out.append((u, v))
            elif v != p:
                low[u] = min(low[u], tin[v])

    for i in range(n):
        if tin[i] == -1:
            dfs(i, -1)
    return out
ID Title Link
1192 Critical Connections in a Network Link

DSU

When to use: “number of connected components”; “are two nodes in the same group?”; “redundant connection” (cycle detection in undirected graph); dynamic connectivity as edges are added.

Path compression + rank. See Data Structures & Core Algorithms for full template.

① Initial (6 sets) ② After 3 unions ③ Path compression 0 1 2 3 4 5 Each node is its own root 0 1 2 3 4 5 union(0,1) union(2,3) union(4,5) Before find(3) 0 1 2 3 → After find(3) 0 1 2 3 3 now points directly to root 0
ID Title Link Solution
684 Redundant Connection Link -
721 Accounts Merge Link -
323 Number of Connected Components Link -
399 Evaluate Division Link -
1202 Smallest String With Swaps Link Solution
1319 Number of Operations to Make Network Connected Link Solution
1584 Min Cost to Connect All Points Link Solution
261 Graph Valid Tree Link Solution

Algorithm Summary

Algorithm When to Use Time Space
BFS Shortest path, unweighted O(V+E) O(V)
Dijkstra Shortest path, non-negative weights O((V+E) log V) O(V)
Bellman-Ford Shortest path, negative weights, k edges O(VE) O(V)
Topological Sort DAG ordering, prerequisites O(V+E) O(V)
DSU (Union-Find) Connected components, cycle detection O(α(n)) per op O(V)
Tarjan SCC, bridges, articulation points O(V+E) O(V)

More templates