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 Java 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

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) |

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. | ID | Title | Link | |—-|——–|——| | 200 | Number of Islands | Link | | 542 | 01 Matrix | Link |

// import java.util.*;
static int bfsGrid(char[][] g, int si, int sj, int ti, int tj) {
    int m = g.length, n = g[0].length;
    int[][] dist = new int[m][n];
    for (int[] row : dist) Arrays.fill(row, -1);
    ArrayDeque<int[]> q = new ArrayDeque<>();
    q.offer(new int[] {si, sj});
    dist[si][sj] = 0;
    int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    while (!q.isEmpty()) {
        int[] cur = q.poll();
        int i = cur[0], j = cur[1];
        if (i == ti && j == tj) return dist[i][j];
        for (int[] d : dirs) {
            int ni = i + d[0], nj = j + d[1];
            if (ni >= 0 && ni < m && nj >= 0 && nj < n && g[ni][nj] != '#'
                    && dist[ni][nj] == -1) {
                dist[ni][nj] = dist[i][j] + 1;
                q.offer(new int[] {ni, nj});
            }
        }
    }
    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. | ID | Title | Link | |—-|——–|——| | 994 | Rotting Oranges | Link | | 286 | Walls and Gates | Link |

// import java.util.*;
static int multiBfs(char[][] g, List<int[]> sources) {
    int m = g.length, n = g[0].length;
    int[][] dist = new int[m][n];
    for (int[] row : dist) Arrays.fill(row, -1);
    ArrayDeque<int[]> q = new ArrayDeque<>();
    for (int[] s : sources) {
        dist[s[0]][s[1]] = 0;
        q.offer(s);
    }
    int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    int best = 0;
    while (!q.isEmpty()) {
        int[] cur = q.poll();
        int i = cur[0], j = cur[1];
        for (int[] d : dirs) {
            int ni = i + d[0], nj = j + d[1];
            if (ni >= 0 && ni < m && nj >= 0 && nj < n && g[ni][nj] != '#'
                    && dist[ni][nj] == -1) {
                dist[ni][nj] = dist[i][j] + 1;
                best = Math.max(best, dist[ni][nj]);
                q.offer(new int[] {ni, nj});
            }
        }
    }
    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.

ID Title Link
847 Shortest Path Visiting All Nodes Link
864 Shortest Path to Get All Keys Link 
// import java.util.*;
static int bfsMask(int n, List<List<Integer>> g, int start) {
    int full = (1 << n) - 1;
    boolean[][] vis = new boolean[n][1 << n];
    ArrayDeque<int[]> q = new ArrayDeque<>();
    q.offer(new int[] {start, 1 << start});
    vis[start][1 << start] = true;
    for (int d = 0; !q.isEmpty(); d++) {
        int sz = q.size();
        while (sz-- > 0) {
            int[] cur = q.poll();
            int u = cur[0], mask = cur[1];
            if (mask == full) return d;
            for (int v : g.get(u)) {
                int m2 = mask | (1 << v);
                if (!vis[v][m2]) {
                    vis[v][m2] = true;
                    q.offer(new int[] {v, m2});
                }
            }
        }
    }
    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] ✓
ID Title Link
207 Course Schedule Link
210 Course Schedule II Link
269 Alien Dictionary Link 
// import java.util.*;
static List<Integer> topoKahn(int n, List<List<Integer>> g) {
    int[] indeg = new int[n];
    for (int u = 0; u < n; u++) for (int v : g.get(u)) indeg[v]++;
    ArrayDeque<Integer> q = new ArrayDeque<>();
    for (int i = 0; i < n; i++) if (indeg[i] == 0) q.offer(i);
    List<Integer> order = new ArrayList<>();
    while (!q.isEmpty()) {
        int u = q.poll();
        order.add(u);
        for (int v : g.get(u)) if (--indeg[v] == 0) q.offer(v);
    }
    return order.size() == n ? order : List.of();
}
ID Title Link
207 Course Schedule Link
210 Course Schedule II Link
269 Alien Dictionary Link

Topological sort (DFS)

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] ✓
ID Title Link
207 Course Schedule Link
210 Course Schedule II Link
269 Alien Dictionary Link 
// import java.util.*;
static List<Integer> topoDfs(int n, List<List<Integer>> g) {
    int[] color = new int[n];
    List<Integer> order = new ArrayList<>();
    boolean[] ok = {true};
    for (int i = 0; i < n; i++) {
        if (color[i] == 0) dfs(i, g, color, order, ok);
    }
    if (!ok[0]) return List.of();
    Collections.reverse(order);
    return order;
}

private static void dfs(int u, List<List<Integer>> g, int[] color,
                      List<Integer> order, boolean[] ok) {
    color[u] = 1;
    for (int v : g.get(u)) {
        if (color[v] == 0) dfs(v, g, color, order, ok);
        else if (color[v] == 1) ok[0] = false;
    }
    color[u] = 2;
    order.add(u);
}
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
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].

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 java.util.*;
static long[] dijkstra(int n, List<List<int[]>> g, int s) {
    long INF = 1L << 60;
    long[] dist = new long[n];
    Arrays.fill(dist, INF);
    dist[s] = 0;
    PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));
    pq.offer(new long[] {0, s});
    while (!pq.isEmpty()) {
        long[] cur = pq.poll();
        long d = cur[0];
        int u = (int) cur[1];
        if (d != dist[u]) continue;
        for (int[] e : g.get(u)) {
            int v = e[0], w = e[1];
            if (dist[v] > d + w) {
                dist[v] = d + w;
                pq.offer(new long[] {dist[v], 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].

// import java.util.*;
static int[] dijkstraDisappear(int n, List<List<int[]>> g, int[] disappear) {
    int[] dist = new int[n];
    Arrays.fill(dist, -1);
    dist[0] = 0;
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
    pq.offer(new int[] {0, 0});
    while (!pq.isEmpty()) {
        int[] cur = pq.poll();
        int d = cur[0], u = cur[1];
        if (dist[u] != -1 && d > dist[u]) continue;
        for (int[] e : g.get(u)) {
            int v = e[0], w = e[1];
            int nd = d + w;
            if (nd < disappear[v] && (dist[v] == -1 || nd < dist[v])) {
                dist[v] = nd;
                pq.offer(new int[] {nd, v});
            }
        }
    }
    return dist;
}

Variant: grid with earliest-entry times (3341). Moving costs 1, but you may need to wait to enter the next cell.

// import java.util.*;
static long dijkstraGridOpen(int[][] open) {
    int n = open.length, m = open[0].length;
    long INF = 1L << 60;
    long[][] dist = new long[n][m];
    for (long[] row : dist) Arrays.fill(row, INF);
    dist[0][0] = 0;
    PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));
    pq.offer(new long[] {0, 0, 0});
    int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    while (!pq.isEmpty()) {
        long[] cur = pq.poll();
        long t = cur[0];
        int i = (int) cur[1], j = (int) cur[2];
        if (t != dist[i][j]) continue;
        if (i == n - 1 && j == m - 1) return t;
        for (int[] d : dirs) {
            int ni = i + d[0], nj = j + d[1];
            if (ni < 0 || ni >= n || nj < 0 || nj >= m) continue;
            long nt = Math.max(t, open[ni][nj]) + 1;
            if (nt < dist[ni][nj]) {
                dist[ni][nj] = nt;
                pq.offer(new long[] {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).

// import java.util.*;
static int[] bfs01(int n, List<List<int[]>> g, int s) {
    int[] dist = new int[n];
    Arrays.fill(dist, 1_000_000_000);
    dist[s] = 0;
    ArrayDeque<Integer> dq = new ArrayDeque<>();
    dq.offerFirst(s);
    while (!dq.isEmpty()) {
        int u = dq.pollFirst();
        for (int[] e : g.get(u)) {
            int v = e[0], w = e[1];
            int nd = dist[u] + w;
            if (nd < dist[v]) {
                dist[v] = nd;
                if (w == 0) dq.offerFirst(v);
                else dq.offerLast(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.

ID Title Link
787 Cheapest Flights Within K Stops Link 
// import java.util.*;
static long[] bellmanFordK(int n, int[][] edges, int src, int k) {
    long INF = 1L << 60;
    long[] dist = new long[n];
    Arrays.fill(dist, INF);
    dist[src] = 0;
    for (int i = 0; i <= k; i++) {
        long[] ndist = dist.clone();
        for (int[] e : edges) {
            int u = e[0], v = e[1], w = e[2];
            if (dist[u] != INF && 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].

ID Title Link
1192 Critical Connections in a Network Link 
// import java.util.*;
static class Tarjan {
    int n, timer = 0, ncomp = 0;
    List<List<Integer>> g;
    int[] tin, low, comp;
    List<Integer> st = new ArrayList<>();
    boolean[] in;

    Tarjan(int n) {
        this.n = n;
        g = new ArrayList<>();
        for (int i = 0; i < n; i++) g.add(new ArrayList<>());
        tin = new int[n];
        low = new int[n];
        comp = new int[n];
        in = new boolean[n];
        Arrays.fill(tin, -1);
        Arrays.fill(comp, -1);
    }

    void add(int u, int v) { g.get(u).add(v); }

    void dfs(int u) {
        tin[u] = low[u] = timer++;
        st.add(u);
        in[u] = true;
        for (int v : g.get(u)) {
            if (tin[v] == -1) {
                dfs(v);
                low[u] = Math.min(low[u], low[v]);
            } else if (in[v]) {
                low[u] = Math.min(low[u], tin[v]);
            }
        }
        if (low[u] == tin[u]) {
            while (true > 0) {
                int v = st.remove(st.size() - 1);
                in[v] = false;
                comp[v] = ncomp;
                if (v == u) break;
            }
            ncomp++;
        }
    }

    int run() {
        for (int i = 0; i < n; i++) if (tin[i] == -1) dfs(i);
        return ncomp;
    }
}

// import java.util.*;
static List<int[]> bridges(int n, List<List<Integer>> g) {
    int timer = 0;
    int[] tin = new int[n], low = new int[n];
    Arrays.fill(tin, -1);
    List<int[]> out = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        if (tin[i] == -1) bridgeDfs(i, -1, g, tin, low, new int[] {0}, out);
    }
    return out;
}

private static void bridgeDfs(int u, int p, List<List<Integer>> g,
        int[] tin, int[] low, int[] timer, List<int[]> out) {
    tin[u] = low[u] = timer[0]++;
    for (int v : g.get(u)) {
        if (tin[v] == -1) {
            bridgeDfs(v, u, g, tin, low, timer, out);
            low[u] = Math.min(low[u], low[v]);
            if (low[v] > tin[u]) out.add(new int[] {u, v});
        } else if (v != p) {
            low[u] = Math.min(low[u], tin[v]);
        }
    }
}
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

More templates