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 C++ 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.

int bfs_grid(const vector<string>& g, int si, int sj, int ti, int tj) {
    int m = g.size(), n = g[0].size();
    vector<vector<int>> dist(m, vector<int>(n, -1));
    queue<pair<int,int>> q;
    q.push({si, sj});
    dist[si][sj] = 0;
    const int dirs[4][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}};
    while (!q.empty()) {
        auto [i, j] = q.front();
        q.pop();
        if (i == ti && j == tj) return dist[i][j];
        for (auto& 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.push({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.

int multi_bfs(const vector<string>& g, const vector<pair<int,int>>& sources) {
    int m = g.size(), n = g[0].size();
    vector<vector<int>> dist(m, vector<int>(n, -1));
    queue<pair<int,int>> q;
    for (auto [i, j] : sources) {
        dist[i][j] = 0;
        q.push({i, j});
    }
    const int dirs[4][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}};
    int best = 0;
    while (!q.empty()) {
        auto [i, j] = q.front();
        q.pop();
        for (auto& 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 = max(best, dist[ni][nj]);
                q.push({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.

int bfs_mask(int n, const vector<vector<int>>& g, int start) {
    int full = (1 << n) - 1;
    vector<vector<bool>> vis(n, vector<bool>(1 << n, false));
    queue<pair<int,int>> q;
    q.push({start, 1 << start});
    vis[start][1 << start] = true;
    for (int d = 0; !q.empty(); d++) {
        int sz = q.size();
        while (sz--) {
            auto [u, mask] = q.front();
            q.pop();
            if (mask == full) return d;
            for (int v : g[u]) {
                int m2 = mask | (1 << v);
                if (!vis[v][m2]) {
                    vis[v][m2] = true;
                    q.push({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] ✓ 
vector<int> topo_kahn(int n, const vector<vector<int>>& g) {
    vector<int> indeg(n);
    for (int u = 0; u < n; u++)
        for (int v : g[u]) indeg[v]++;
    queue<int> q;
    for (int i = 0; i < n; i++)
        if (indeg[i] == 0) q.push(i);
    vector<int> order;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        order.push_back(u);
        for (int v : g[u])
            if (--indeg[v] == 0) q.push(v);
    }
    return (int)order.size() == n ? order : vector<int>{};
}
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.

vector<int> topo_dfs(int n, const vector<vector<int>>& g) {
    vector<int> color(n, 0), order;
    bool ok = true;
    function<void(int)> dfs = [&](int u) {
        color[u] = 1;
        for (int v : g[u]) {
            if (color[v] == 0) dfs(v);
            else if (color[v] == 1) ok = false;
        }
        color[u] = 2;
        order.push_back(u);
    };
    for (int i = 0; i < n; i++)
        if (color[i] == 0) dfs(i);
    if (!ok) return {};
    reverse(order.begin(), order.end());
    return order;
}
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 
vector<long long> dijkstra(int n, const vector<vector<pair<int,int>>>& g, int s) {
    const long long INF = 1LL << 60;
    vector<long long> dist(n, INF);
    dist[s] = 0;
    using P = pair<long long, int>;
    priority_queue<P, vector<P>, greater<P>> pq;
    pq.push({0, s});
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (d != dist[u]) continue;
        for (auto [v, w] : g[u]) {
            if (dist[v] > d + w) {
                dist[v] = d + w;
                pq.push({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].

vector<int> dijkstra_disappear(int n, const vector<vector<pair<int,int>>>& g,
                               const vector<int>& disappear) {
    vector<int> dist(n, -1);
    dist[0] = 0;
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
    pq.push({0, 0});
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (dist[u] != -1 && d > dist[u]) continue;
        for (auto [v, w] : g[u]) {
            int nd = d + w;
            if (nd < disappear[v] && (dist[v] == -1 || nd < dist[v])) {
                dist[v] = nd;
                pq.push({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: [ \text{nextTime} = \max(\text{curTime},\ \text{open}[ni][nj]) + 1 ]

long long dijkstra_grid_open(const vector<vector<int>>& open) {
    int n = open.size(), m = open[0].size();
    const long long INF = 1LL << 60;
    vector<vector<long long>> dist(n, vector<long long>(m, INF));
    dist[0][0] = 0;
    using S = pair<long long, pair<int,int>>; // (time, (i,j))
    priority_queue<S, vector<S>, greater<>> pq;
    pq.push({0, {0, 0}});
    const int dirs[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
    while (!pq.empty()) {
        auto [t, pos] = pq.top();
        pq.pop();
        auto [i, j] = pos;
        if (t != dist[i][j]) continue;
        if (i == n - 1 && j == m - 1) return t;
        for (auto& d : dirs) {
            int ni = i + d[0], nj = j + d[1];
            if (ni < 0 || ni >= n || nj < 0 || nj >= m) continue;
            long long nt = max(t, (long long)open[ni][nj]) + 1;
            if (nt < dist[ni][nj]) {
                dist[ni][nj] = nt;
                pq.push({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).

vector<int> bfs01(int n, const vector<vector<pair<int,int>>>& g, int s) {
    vector<int> dist(n, 1e9);
    dist[s] = 0;
    deque<int> dq;
    dq.push_front(s);
    while (!dq.empty()) {
        int u = dq.front();
        dq.pop_front();
        for (auto [v, w] : g[u]) {
            int nd = dist[u] + w;
            if (nd < dist[v]) {
                dist[v] = nd;
                if (w == 0) dq.push_front(v);
                else dq.push_back(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.

vector<long long> bellman_ford_k(int n, const vector<array<int,3>>& edges, int src, int k) {
    const long long INF = 1LL << 60;
    vector<long long> dist(n, INF);
    dist[src] = 0;
    for (int i = 0; i <= k; i++) {
        vector<long long> ndist = dist;
        for (auto& 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 = move(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].

struct Tarjan {
    int n, timer = 0;
    vector<vector<int>> g;
    vector<int> tin, low, comp, st;
    vector<char> in;
    int ncomp = 0;

    Tarjan(int n) : n(n), g(n), tin(n, -1), low(n), comp(n, -1), in(n, 0) {}
    void add(int u, int v) { g[u].push_back(v); }

    void dfs(int u) {
        tin[u] = low[u] = timer++;
        st.push_back(u);
        in[u] = 1;
        for (int v : g[u]) {
            if (tin[v] == -1) {
                dfs(v);
                low[u] = min(low[u], low[v]);
            } else if (in[v])
                low[u] = min(low[u], tin[v]);
        }
        if (low[u] == tin[u]) {
            while (true) {
                int v = st.back();
                st.pop_back();
                in[v] = 0;
                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;
    }
};

// Bridges: during dfs, if (low[v] > tin[u]) then (u,v) is bridge
vector<pair<int,int>> bridges(int n, const vector<vector<int>>& g) {
    int timer = 0;
    vector<int> tin(n, -1), low(n);
    vector<pair<int,int>> out;
    function<void(int,int)> dfs = [&](int u, int p) {
        tin[u] = low[u] = timer++;
        for (int v : g[u]) {
            if (tin[v] == -1) {
                dfs(v, u);
                low[u] = min(low[u], low[v]);
                if (low[v] > tin[u]) out.push_back({u, v});
            } else if (v != p)
                low[u] = min(low[u], tin[v]);
        }
    };
    for (int i = 0; i < n; i++)
        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