← All patterns

Graphs

Encode relations as edges. BFS for shortest unweighted paths, DFS for connectivity and topological order, Dijkstra / Bellman-Ford for weighted shortest paths, A* when a heuristic is available.

17 problems 3 Easy 8 Medium 6 Hard

Represent relations as nodes and edges; algorithms differ by edge weighting. BFS for shortest unweighted paths; DFS for connectivity, topological order, articulation points; Dijkstra for non-negative weighted; Bellman-Ford for negative weights or k-edge limits; A* with an admissible heuristic; Floyd-Warshall for all-pairs.

Implicit graphs are everywhere: word ladder, sliding puzzle, state-space search — same algorithms, you just generate neighbors on demand.

When to reach for this pattern

  • Input has 'edges' or implied relations between entities
  • Shortest path, reachability, connectivity
  • Strongly connected components, articulation points
  • Network flow, matching, minimum spanning tree

Canonical template 

// BFS shortest unweighted path
queue<int> q;
q.push(source);
vector<int> dist(n, -1);
dist[source] = 0;
while (!q.empty()) {
    int u = q.front(); q.pop();
    for (int v : adj[u]) if (dist[v] == -1) {
        dist[v] = dist[u] + 1;
        q.push(v);
    }
}

// Dijkstra (non-negative weights)
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
pq.emplace(0, source);
while (!pq.empty()) {
    auto [d, u] = pq.top(); pq.pop();
    if (d > dist[u]) continue;
    for (auto& [v, w] : adj[u])
        if (d + w < dist[v]) {
            dist[v] = d + w;
            pq.emplace(dist[v], v);
        }
}

C++ · adapt the names and types to your problem.

Common pitfalls

  • Using BFS for shortest path on a *weighted* graph — only works for unweighted
  • Dijkstra on graphs with negative edges — silently wrong; use Bellman-Ford
  • Marking visited at dequeue time (vs enqueue time) — exponential queue size
  • Implicit graphs: word ladder, state-space search — same algorithms, different node generators

Related patterns

Tree DFS Tree BFS Topological Sort Union Find

Problems (17)

Search ESC

Keyboard shortcuts

Shortcuts are disabled while typing in inputs.