Graph algorithms differ mainly in what the frontier promises. A DFS stack promises only that a path remains to explore. A BFS queue promises nondecreasing edge count. Dijkstra’s heap promises the smallest known tentative distance. Topological order promises that every removed vertex has no remaining prerequisite. Choose the frontier whose promise matches the question.
Representation and visited state
For vertices numbered 0..V-1, an adjacency list is usually
vector<vector<int>> or a vector of
{neighbor, weight} pairs. It uses O(V + E)
storage and iterates only actual edges. An adjacency matrix uses
O(V²) storage but answers edge-existence queries in constant
time and is appropriate for dense graphs or Floyd–Warshall.
| State | Meaning | Common use |
|---|---|---|
| Boolean visited | Vertex has been discovered | Undirected traversal and component counting |
| Three colors | Unseen, active recursion path, finished | Directed cycle detection |
| Distance initialized to −1 | Unvisited and distance in one array | Unweighted BFS |
| Parent vertex or edge | How the traversal reached this state | Path reconstruction and undirected DFS |
| Best-known distance | Upper bound that can still improve | Dijkstra and Bellman–Ford |
Depth-first search
Explore a complete path, aggregate a subtree, enumerate a connected component, or maintain state along the active recursion path.
Tree recursion is structural: solve each child, then combine their answers. No visited set is needed because a tree node has one parent and no cycles. Maximum depth is postorder because the parent answer depends on completed child answers.
tree_depth.cppint max_depth(const TreeNode* node) {
if (node == nullptr) return 0;
return 1 + std::max(
max_depth(node->left),
max_depth(node->right)
);
}Grid components use the same search over implicit neighbors. Mutating a disposable grid from land to water combines the visited set with the input. Mark before recursing. Marking afterward permits neighbors to recurse back into the current cell.
Every cell changed to '0' belongs to the current component and will never enter the recursion again.
count_islands.cppint count_islands(std::vector<std::string> grid) {
if (grid.empty()) return 0;
const int rows = static_cast<int>(grid.size());
const int columns = static_cast<int>(grid.front().size());
int islands = 0;
const auto sink = [&](const auto& self, int row, int column) -> void {
if (row < 0 || row >= rows || column < 0 || column >= columns ||
grid[static_cast<std::size_t>(row)]
[static_cast<std::size_t>(column)] != '1') return;
grid[static_cast<std::size_t>(row)]
[static_cast<std::size_t>(column)] = '0';
self(self, row + 1, column);
self(self, row - 1, column);
self(self, row, column + 1);
self(self, row, column - 1);
};
for (int row = 0; row < rows; ++row)
for (int column = 0; column < columns; ++column)
if (grid[static_cast<std::size_t>(row)]
[static_cast<std::size_t>(column)] == '1') {
++islands;
sink(sink, row, column);
}
return islands;
}
Recursive DFS can overflow the call stack on a path-shaped graph with
hundreds of thousands of vertices. Replace it with
vector<int> stack when depth is not bounded. To
reproduce recursive postorder, store an “enter/exit” flag or an iterator
position with each stack frame.
Maximum Depth · Path Sum · Diameter · Lowest Common Ancestor · Validate BST · Number of Islands · Surrounded Regions · Clone Graph · Pacific Atlantic · Evaluate Division
Breadth-first search
Find the minimum number of equal-cost edges or operations, process a structure level by level, or propagate simultaneously from multiple sources.
The queue processes vertices in discovery order. All vertices at
distance d are removed before any vertex at
d + 1. Mark a vertex when enqueuing it, not when dequeuing
it. Otherwise several parents can enqueue the same vertex and inflate
both time and memory.
shortest_unweighted.cppint shortest_unweighted(
std::span<const std::vector<int>> graph,
int start,
int goal
) {
std::queue<int> frontier;
std::vector<int> distance(graph.size(), -1);
frontier.push(start);
distance[static_cast<std::size_t>(start)] = 0;
while (!frontier.empty()) {
const int node = frontier.front();
frontier.pop();
if (node == goal) return distance[static_cast<std::size_t>(node)];
for (const int next : graph[static_cast<std::size_t>(node)]) {
auto& next_distance = distance[static_cast<std::size_t>(next)];
if (next_distance != -1) continue;
next_distance = distance[static_cast<std::size_t>(node)] + 1;
frontier.push(next);
}
}
return -1;
}
Multi-source BFS initializes the queue with every source at distance
zero. Rotting Oranges starts from every rotten orange. 01 Matrix starts
from every zero. Bidirectional BFS starts from both ends and expands the
smaller frontier, reducing a branching search from roughly
b^d states to two searches near b^(d/2).
Level Order Traversal · Rotting Oranges · 01 Matrix · Word Ladder · Open the Lock · Shortest Path in Binary Matrix · Minimum Knight Moves · Bus Routes
Topological order
Directed dependencies, prerequisites, build order, or a request to detect whether all work can be completed.
Kahn’s algorithm stores the number of unremoved incoming edges. Vertices
with indegree zero are ready because no remaining dependency precedes
them. Removing a vertex decrements its outgoing neighbors. If fewer than
V vertices are removed, the remaining subgraph contains a
directed cycle.
indegree[v] counts edges into v from vertices not yet placed in the output.
topological_order.cppstd::optional<std::vector<int>> topological_order(
std::size_t vertex_count,
std::span<const std::pair<int, int>> edges
) {
std::vector<std::vector<int>> graph(vertex_count);
std::vector<int> indegree(vertex_count, 0);
for (const auto& [before, after] : edges) {
graph[static_cast<std::size_t>(before)].push_back(after);
++indegree[static_cast<std::size_t>(after)];
}
std::queue<int> ready;
for (std::size_t v = 0; v < vertex_count; ++v)
if (indegree[v] == 0) ready.push(static_cast<int>(v));
std::vector<int> order;
while (!ready.empty()) {
const int node = ready.front();
ready.pop();
order.push_back(node);
for (const int next : graph[static_cast<std::size_t>(node)])
if (--indegree[static_cast<std::size_t>(next)] == 0)
ready.push(next);
}
if (order.size() != vertex_count) return std::nullopt;
return order;
}DFS can also produce a topological order by appending each vertex on exit and reversing the result. A back edge to an active gray vertex detects a cycle. Kahn’s form is preferable when the problem exposes indegrees, needs lexicographically smallest order through a min-heap, or processes work in dependency waves.
Course Schedule I/II · Alien Dictionary · Build Order · Find Eventual Safe States · Parallel Courses · Minimum Height Trees
Disjoint-set union
Edges arrive incrementally, groups merge, connectivity is queried repeatedly, or an undirected edge should be accepted only when it connects two components.
Each component is represented by a root. Path halving makes every find
skip a generation. Union by size attaches the smaller tree beneath the
larger. Together they give nearly constant amortized operations, more
precisely O(α(n)).
disjoint_set.cppclass DisjointSet {
public:
explicit DisjointSet(std::size_t size)
: parent_(size), component_size_(size, 1) {
std::iota(parent_.begin(), parent_.end(), std::size_t{0});
}
std::size_t find(std::size_t node) {
while (node != parent_[node]) {
parent_[node] = parent_[parent_[node]];
node = parent_[node];
}
return node;
}
bool unite(std::size_t left, std::size_t right) {
left = find(left);
right = find(right);
if (left == right) return false;
if (component_size_[left] < component_size_[right])
std::swap(left, right);
parent_[right] = left;
component_size_[left] += component_size_[right];
return true;
}
private:
std::vector<std::size_t> parent_;
std::vector<std::size_t> component_size_;
};
A failed unite means the endpoints were already connected,
so adding that undirected edge closes a cycle. DSU cannot answer
arbitrary deletions or reconstruct paths without additional machinery.
Use traversal when the graph is static and you also need component
contents or path data.
Redundant Connection · Number of Components · Accounts Merge · Number of Islands II · Graph Valid Tree · Smallest String With Swaps · Kruskal MST
Dijkstra’s shortest paths
Edges have nonnegative weights and the answer is a minimum total cost from one source or a small set of sources.
The priority queue can contain stale entries because C++’s
priority_queue has no decrease-key operation. Push the
improved pair and discard an entry when its distance no longer matches
the current best. With nonnegative weights, the smallest non-stale
distance cannot later improve through an unprocessed vertex.
Every popped non-stale entry has the smallest unsettled distance. Relaxing its outgoing edges preserves upper bounds for all other vertices.
dijkstra.cppusing WeightedEdge = std::pair<int, int>; // {neighbor, weight}
std::vector<std::int64_t> dijkstra(
std::span<const std::vector<WeightedEdge>> graph,
int source
) {
constexpr auto infinity = std::numeric_limits<std::int64_t>::max();
using Entry = std::pair<std::int64_t, int>;
std::vector<std::int64_t> distance(graph.size(), infinity);
std::priority_queue<Entry, std::vector<Entry>, std::greater<>> frontier;
distance[static_cast<std::size_t>(source)] = 0;
frontier.push({0, source});
while (!frontier.empty()) {
const auto [known, node] = frontier.top();
frontier.pop();
if (known != distance[static_cast<std::size_t>(node)]) continue;
for (const auto& [next, weight] : graph[static_cast<std::size_t>(node)]) {
const auto candidate = known + weight;
auto& best = distance[static_cast<std::size_t>(next)];
if (candidate < best) {
best = candidate;
frontier.push({candidate, next});
}
}
}
return distance;
}
Do not use Dijkstra with a negative edge. The greedy finalization
argument depends on extending paths without reducing their cost. For
edge weights only zero or one, a deque-based 0–1 BFS pushes zero-cost
edges to the front and one-cost edges to the back in
O(V + E).
Network Delay Time · Path With Minimum Effort · Swim in Rising Water · Cheapest Flights with a stop-state extension · 0–1 Matrix variants · Minimum Cost Grid Path
Bellman–Ford and Floyd–Warshall
Bellman–Ford handles negative edges. After iteration k,
every shortest path using at most k edges has been
considered. A shortest simple path uses at most V - 1
edges. A relaxation on the next pass proves that a reachable negative
cycle exists.
bellman_ford.cppstruct Edge { int from, to, weight; };
bool bellman_ford(
int vertex_count,
std::span<const Edge> edges,
int source,
std::vector<long long>& distance
) {
const long long inf = std::numeric_limits<long long>::max() / 4;
distance.assign(static_cast<std::size_t>(vertex_count), inf);
distance[static_cast<std::size_t>(source)] = 0;
for (int pass = 1; pass < vertex_count; ++pass) {
bool changed = false;
for (const auto& edge : edges) {
const auto from = static_cast<std::size_t>(edge.from);
const auto to = static_cast<std::size_t>(edge.to);
if (distance[from] != inf &&
distance[from] + edge.weight < distance[to]) {
distance[to] = distance[from] + edge.weight;
changed = true;
}
}
if (!changed) break;
}
for (const auto& edge : edges)
if (distance[static_cast<std::size_t>(edge.from)] != inf &&
distance[static_cast<std::size_t>(edge.from)] + edge.weight <
distance[static_cast<std::size_t>(edge.to)])
return false;
return true;
}
Floyd–Warshall computes every pair in O(V³). The
k loop must be outermost: after completing it,
distance[i][j] is optimal using only vertices
0..k as intermediates.
floyd_warshall.cppfor (std::size_t k = 0; k < n; ++k)
for (std::size_t i = 0; i < n; ++i) {
if (distance[i][k] == infinity) continue;
for (std::size_t j = 0; j < n; ++j) {
if (distance[k][j] == infinity) continue;
distance[i][j] = std::min(
distance[i][j],
distance[i][k] + distance[k][j]
);
}
}Minimum spanning tree
A spanning tree connects every vertex with V - 1 edges.
Kruskal sorts edges by weight and accepts an edge exactly when DSU says
it connects different components. The cut property proves safety: the
lightest edge crossing any component boundary can belong to an MST.
kruskal.cppstd::optional<std::int64_t> kruskal(
std::size_t vertex_count,
std::vector<MstEdge> edges
) {
std::sort(edges.begin(), edges.end(),
[](const auto& a, const auto& b) { return a.weight < b.weight; });
DisjointSet components(vertex_count);
std::size_t used = 0;
std::int64_t total = 0;
for (const auto edge : edges) {
if (!components.unite(edge.from, edge.to)) continue;
total += edge.weight;
if (++used + 1 == vertex_count) break;
}
if (vertex_count > 0 && used + 1 != vertex_count) return std::nullopt;
return total;
}Prim instead grows one connected tree using the cheapest outgoing edge. Kruskal fits a sparse edge list. Prim fits an adjacency list or dense matrix. An MST minimizes total connection cost, not the distance from a source to each vertex.
Bridges, articulation points, and SCCs
In an undirected DFS, entered[u] is the discovery time and
low[u] is the earliest discovery reachable from
u’s subtree using tree edges plus at most one back edge. A
tree edge u → v is a bridge when
low[v] > entered[u]: the child subtree cannot reach
u or any ancestor without that edge.
bridges_dfs.cppvoid dfs(int node, int parent_edge) {
const auto u = static_cast<std::size_t>(node);
entered[u] = low[u] = timer++;
for (const auto& [next, edge_id] : graph[u]) {
if (edge_id == parent_edge) continue; // skip the edge, not the vertex
const auto v = static_cast<std::size_t>(next);
if (entered[v] != -1) {
low[u] = std::min(low[u], entered[v]);
continue;
}
dfs(next, edge_id);
low[u] = std::min(low[u], low[v]);
if (low[v] > entered[u]) bridges.push_back(edge_id);
}
}
Skip the incoming edge ID rather than the parent vertex. Parallel edges
make the second edge a valid back edge. Articulation points use
low[v] ≥ entered[u] for non-root vertices, while a root is
an articulation point only with at least two DFS children.
Strongly connected components apply to directed graphs. Tarjan keeps
active vertices on a stack and emits an SCC when
low[u] == entered[u]. Kosaraju is often easier to reproduce:
DFS to obtain finish order, transpose every edge, then DFS in reverse
finish order. Contracting each SCC produces a DAG.
Critical Connections · Articulation Points · Network Reliability · Strongly Connected Components · Mother Vertex · Minimum edges after SCC condensation
Graph decision table
| Problem | Algorithm | Time |
|---|---|---|
| Reachability, components, tree aggregation | DFS | O(V + E) |
| Equal-cost shortest path | BFS | O(V + E) |
| Dependency order or directed cycle | Kahn or color DFS | O(V + E) |
| Incremental undirected connectivity | DSU | O((V + E) α(V)) |
| Nonnegative single-source shortest paths | Dijkstra + heap | O((V + E) log V) |
| Negative edges / reachable negative cycle | Bellman–Ford | O(VE) |
| All-pairs shortest paths, moderate V | Floyd–Warshall | O(V³) |
| Minimum total connection cost | Kruskal or Prim | O(E log E) |
| Critical undirected edges/vertices | Low-link DFS | O(V + E) |
| Mutual reachability in a directed graph | Tarjan or Kosaraju SCC | O(V + E) |