Chapter 6 · Graphs¶
A graph is a set of states and legal transitions. Many problems never use the word “graph”: grids, word transformations, lock combinations, schedules, and game positions all qualify.
Choose by edge meaning¶
flowchart TD
accTitle: Choosing a graph traversal or shortest-path algorithm
accDescr: First choose the required result. For traversal, use BFS when levels or minimum edge count matter and DFS when any complete reachability exploration is enough. For shortest paths, choose BFS, zero-one BFS, Dijkstra, or Bellman-Ford from the edge costs. Use topological sort for dependency order.
A{"What result is required?"}
A -->|"reachability / traversal"| B{"Do levels or minimum<br/>edge count matter?"}
B -->|yes| H["BFS<br/>queue: oldest first"]
B -->|no| I["DFS or BFS<br/>stack vs queue order"]
A -->|"shortest path"| C{"Edge costs"}
C -->|"all equal"| D["BFS"]
C -->|"0 or 1"| E["0–1 BFS"]
C -->|"nonnegative"| F["Dijkstra"]
C -->|"negative allowed"| G["Bellman–Ford"]
A -->|"dependency order"| J["Topological sort"]
A -->|"global connection, capacity,<br/>components, or critical links"| K["Chapter 10<br/>advanced graph chooser"]DFS and BFS visit the same reachable vertices. Their order is the distinction: DFS commits down one branch using a call stack or explicit stack; BFS expands one distance layer at a time using a queue.
Use the Advanced Graphs chooser when the requested result is a minimum spanning tree, maximum flow, strongly connected components, all-pairs paths, bridges/articulation points, or repeated ancestor query rather than ordinary traversal.
BFS distances¶
Invariant: vertices leave the queue in nondecreasing distance from the source. The first discovery of a vertex gives its shortest unweighted distance.
def bfs_distances(graph: Sequence[Sequence[int]], source: int) -> list[int]:
"""Return unweighted distances from ``source``; unreachable is ``-1``."""
_validate_vertex(source, len(graph), "source")
_validate_unweighted_graph(graph)
distance = [-1] * len(graph)
# Mark on enqueue so each vertex enters the queue once.
distance[source] = 0
queue = deque([source])
while queue:
node = queue.popleft()
for neighbor in graph[node]:
if distance[neighbor] == -1:
# Queue order guarantees this first distance is shortest.
distance[neighbor] = distance[node] + 1
queue.append(neighbor)
return distance
inline std::vector<int> bfs_distances(
const std::vector<std::vector<int>>& graph, int source) {
validate_vertex(source, graph.size(), "source");
for (const auto& neighbors : graph) {
for (const int neighbor : neighbors) {
validate_vertex(neighbor, graph.size(), "neighbor");
}
}
std::vector<int> distance(graph.size(), -1);
std::queue<int> frontier;
// Mark on enqueue so every vertex enters the queue once.
distance[source] = 0;
frontier.push(source);
while (!frontier.empty()) {
const int node = frontier.front();
frontier.pop();
for (const int neighbor : graph[node]) {
if (distance[neighbor] == -1) {
// Queue order makes this first distance the shortest.
distance[neighbor] = distance[node] + 1;
frontier.push(neighbor);
}
}
}
return distance;
}
inline std::vector<int> bfs_distances(
const std::vector<std::vector<int>>& graph, int source) {
validate_vertex(source, graph.size(), "source");
for (const auto& neighbors : graph) {
for (const int neighbor : neighbors) {
validate_vertex(neighbor, graph.size(), "neighbor");
}
}
std::vector<int> distance(graph.size(), -1);
std::queue<int> frontier;
// Mark on enqueue so every vertex enters the queue once.
distance[source] = 0;
frontier.push(source);
while (!frontier.empty()) {
const int node = frontier.front();
frontier.pop();
for (const int neighbor : graph[node]) {
if (distance[neighbor] == -1) {
// Queue order makes this first distance the shortest.
distance[neighbor] = distance[node] + 1;
frontier.push(neighbor);
}
}
}
return distance;
}
Mark a vertex when enqueuing, not when dequeuing, or the queue may contain many duplicates.
Dijkstra¶
Dijkstra requires nonnegative edge weights.
Invariant: when a non-stale (distance, vertex) pair leaves the min-heap,
that distance is final.
def dijkstra(
graph: Sequence[Sequence[tuple[int, int]]], source: int
) -> list[float | int]:
"""Return shortest distances for a graph with nonnegative weights."""
_validate_vertex(source, len(graph), "source")
for edges in graph:
for neighbor, weight in edges:
_validate_vertex(neighbor, len(graph), "neighbor")
if weight < 0:
raise ValueError("Dijkstra requires nonnegative weights")
distance: list[float | int] = [inf] * len(graph)
distance[source] = 0
frontier: list[tuple[int, int]] = [(0, source)]
while frontier:
current, node = heappop(frontier)
# Ignore heap entries superseded by a shorter route.
if current != distance[node]:
continue
for neighbor, weight in graph[node]:
candidate = current + weight
if candidate < distance[neighbor]:
# Relax the edge and schedule the improved state.
distance[neighbor] = candidate
heappush(frontier, (candidate, neighbor))
return distance
inline std::vector<long long> dijkstra(
const WeightedGraph& graph, int source) {
validate_vertex(source, graph.size(), "source");
for (const auto& edges : graph) {
for (const auto& edge : edges) {
const int neighbor = edge.first;
const long long weight = edge.second;
validate_vertex(neighbor, graph.size(), "neighbor");
if (weight < 0) {
throw std::invalid_argument("Dijkstra requires nonnegative weights");
}
}
}
constexpr long long infinity = std::numeric_limits<long long>::max();
using State = std::pair<long long, int>;
std::priority_queue<State, std::vector<State>, std::greater<State>> frontier;
std::vector<long long> distance(graph.size(), infinity);
distance[source] = 0;
frontier.push({0, source});
while (!frontier.empty()) {
const State state = frontier.top();
const long long current = state.first;
const int node = state.second;
frontier.pop();
// Ignore heap entries superseded by a shorter route.
if (current != distance[node]) {
continue;
}
for (const auto& edge : graph[node]) {
const int neighbor = edge.first;
const long long weight = edge.second;
if (current > infinity - weight) {
continue;
}
const long long candidate = current + weight;
if (candidate < distance[neighbor]) {
// Relax the edge and schedule the improved state.
distance[neighbor] = candidate;
frontier.push({candidate, neighbor});
}
}
}
return distance;
}
inline std::vector<long long> dijkstra(
const WeightedGraph& graph, int source) {
validate_vertex(source, graph.size(), "source");
for (const auto& edges : graph) {
for (const auto& edge : edges) {
const int neighbor = edge.first;
const long long weight = edge.second;
validate_vertex(neighbor, graph.size(), "neighbor");
if (weight < 0) {
throw std::invalid_argument("Dijkstra requires nonnegative weights");
}
}
}
constexpr long long infinity = std::numeric_limits<long long>::max();
using State = std::pair<long long, int>;
std::priority_queue<State, std::vector<State>, std::greater<State>> frontier;
std::vector<long long> distance(graph.size(), infinity);
distance[source] = 0;
frontier.push({0, source});
while (!frontier.empty()) {
const State state = frontier.top();
const long long current = state.first;
const int node = state.second;
frontier.pop();
// Ignore heap entries superseded by a shorter route.
if (current != distance[node]) {
continue;
}
for (const auto& edge : graph[node]) {
const int neighbor = edge.first;
const long long weight = edge.second;
if (current > infinity - weight) {
continue;
}
const long long candidate = current + weight;
if (candidate < distance[neighbor]) {
// Relax the edge and schedule the improved state.
distance[neighbor] = candidate;
frontier.push({candidate, neighbor});
}
}
}
return distance;
}
Multiple heap entries for one vertex are normal. Skip an entry whose distance no longer equals the best known distance.
Topological order¶
Kahn's algorithm repeatedly removes zero-indegree vertices. If fewer than n
vertices are removed, the graph contains a directed cycle; returning the
partial list as a valid order is a correctness bug.
def topological_order(graph: Sequence[Sequence[int]]) -> list[int]:
"""Return a topological order or raise when the directed graph is cyclic."""
_validate_unweighted_graph(graph)
indegree = [0] * len(graph)
for neighbors in graph:
for neighbor in neighbors:
indegree[neighbor] += 1
# Only vertices with no unmet prerequisite are ready.
queue = deque(index for index, degree in enumerate(indegree) if degree == 0)
order: list[int] = []
while queue:
node = queue.popleft()
order.append(node)
for neighbor in graph[node]:
indegree[neighbor] -= 1
if indegree[neighbor] == 0:
# Its final prerequisite has just been removed.
queue.append(neighbor)
if len(order) != len(graph):
raise ValueError("directed graph contains a cycle")
return order
inline std::vector<int> topological_order(
const std::vector<std::vector<int>>& graph) {
for (const auto& neighbors : graph) {
for (const int neighbor : neighbors) {
validate_vertex(neighbor, graph.size(), "neighbor");
}
}
std::vector<int> indegree(graph.size(), 0);
for (const auto& neighbors : graph) {
for (const int neighbor : neighbors) {
++indegree[neighbor];
}
}
std::queue<int> ready;
for (int node = 0; node < static_cast<int>(graph.size()); ++node) {
if (indegree[node] == 0) {
// Only vertices with no unmet prerequisite are ready.
ready.push(node);
}
}
std::vector<int> order;
while (!ready.empty()) {
const int node = ready.front();
ready.pop();
order.push_back(node);
for (const int neighbor : graph[node]) {
if (--indegree[neighbor] == 0) {
// Its final prerequisite has just been removed.
ready.push(neighbor);
}
}
}
if (order.size() != graph.size()) {
throw std::invalid_argument("directed graph contains a cycle");
}
return order;
}
inline std::vector<int> topological_order(
const std::vector<std::vector<int>>& graph) {
for (const auto& neighbors : graph) {
for (const int neighbor : neighbors) {
validate_vertex(neighbor, graph.size(), "neighbor");
}
}
std::vector<int> indegree(graph.size(), 0);
for (const auto& neighbors : graph) {
for (const int neighbor : neighbors) {
++indegree[neighbor];
}
}
std::queue<int> ready;
for (int node = 0; node < static_cast<int>(graph.size()); ++node) {
if (indegree[node] == 0) {
// Only vertices with no unmet prerequisite are ready.
ready.push(node);
}
}
std::vector<int> order;
while (!ready.empty()) {
const int node = ready.front();
ready.pop();
order.push_back(node);
for (const int neighbor : graph[node]) {
if (--indegree[neighbor] == 0) {
// Its final prerequisite has just been removed.
ready.push(neighbor);
}
}
}
if (order.size() != graph.size()) {
throw std::invalid_argument("directed graph contains a cycle");
}
return order;
}
Bridge edges¶
An undirected edge is a bridge when its child subtree cannot reach the parent or any ancestor without using that same edge. Parallel edges require edge IDs: skipping every edge to the parent vertex incorrectly reports a bridge.
The tested library implementation tracks the exact parent edge and includes a parallel-edge regression case.
def find_bridges(vertex_count: int, edges: Sequence[tuple[int, int]]) -> list[tuple[int, int]]:
"""Return bridge edges in an undirected multigraph."""
if vertex_count < 0:
raise ValueError("vertex_count must be nonnegative")
graph: list[list[tuple[int, int]]] = [[] for _ in range(vertex_count)]
for edge_id, (left, right) in enumerate(edges):
_validate_vertex(left, vertex_count, "edge endpoint")
_validate_vertex(right, vertex_count, "edge endpoint")
# Edge IDs distinguish parallel edges from the exact parent edge.
graph[left].append((right, edge_id))
graph[right].append((left, edge_id))
entered = [-1] * vertex_count
low = [0] * vertex_count
timer = 0
bridges: list[tuple[int, int]] = []
def search(node: int, parent_edge: int = -1) -> None:
nonlocal timer
entered[node] = low[node] = timer
timer += 1
for neighbor, edge_id in graph[node]:
if edge_id == parent_edge:
continue
if entered[neighbor] >= 0:
# A back edge may connect this subtree to an ancestor.
low[node] = min(low[node], entered[neighbor])
continue
search(neighbor, edge_id)
low[node] = min(low[node], low[neighbor])
if low[neighbor] > entered[node]:
# The child subtree has no route around this tree edge.
bridges.append((min(node, neighbor), max(node, neighbor)))
for vertex in range(vertex_count):
if entered[vertex] < 0:
search(vertex)
return sorted(bridges)
inline std::vector<std::pair<int, int>> find_bridges(
int vertex_count, const std::vector<std::pair<int, int>>& edges) {
if (vertex_count < 0) {
throw std::invalid_argument("vertex_count must be nonnegative");
}
std::vector<std::vector<std::pair<int, int>>> graph(
static_cast<std::size_t>(vertex_count));
for (int id = 0; id < static_cast<int>(edges.size()); ++id) {
const int left = edges[id].first;
const int right = edges[id].second;
validate_vertex(left, graph.size(), "edge endpoint");
validate_vertex(right, graph.size(), "edge endpoint");
// Edge IDs distinguish parallel edges from the exact parent edge.
graph[left].push_back({right, id});
graph[right].push_back({left, id});
}
std::vector<int> entered(vertex_count, -1);
std::vector<int> low(vertex_count);
std::vector<std::pair<int, int>> bridges;
int timer = 0;
std::function<void(int, int)> search = [&](int node, int parent_edge) {
entered[node] = low[node] = timer++;
for (const auto& edge : graph[node]) {
const int neighbor = edge.first;
const int edge_id = edge.second;
if (edge_id == parent_edge) {
continue;
}
if (entered[neighbor] >= 0) {
// A back edge may connect this subtree to an ancestor.
low[node] = std::min(low[node], entered[neighbor]);
continue;
}
search(neighbor, edge_id);
low[node] = std::min(low[node], low[neighbor]);
if (low[neighbor] > entered[node]) {
// The child subtree has no route around this tree edge.
bridges.push_back(std::minmax(node, neighbor));
}
}
};
for (int node = 0; node < vertex_count; ++node) {
if (entered[node] < 0) {
search(node, -1);
}
}
std::sort(bridges.begin(), bridges.end());
return bridges;
}
Practice ladder · model vertices and edges first¶
| Rung | Problem | Thinking prompt |
|---|---|---|
| 1 | Number of Islands | What creates an edge between two cells? |
| 2 | Rotting Oranges | Which sources enter BFS at distance zero? |
| 3 | Course Schedule | Is the request an order, or only proof of a cycle? |
| 4 | Network Delay Time | Which weight property licenses Dijkstra? |
Before coding, write vertex = ... and edge = ...; this catches modeling
mistakes earlier than traversal debugging.
inline std::vector<std::pair<int, int>> find_bridges(
int vertex_count, const std::vector<std::pair<int, int>>& edges) {
if (vertex_count < 0) {
throw std::invalid_argument("vertex_count must be nonnegative");
}
std::vector<std::vector<std::pair<int, int>>> graph(
static_cast<std::size_t>(vertex_count));
for (int id = 0; id < static_cast<int>(edges.size()); ++id) {
const int left = edges[id].first;
const int right = edges[id].second;
validate_vertex(left, graph.size(), "edge endpoint");
validate_vertex(right, graph.size(), "edge endpoint");
// Edge IDs distinguish parallel edges from the exact parent edge.
graph[left].push_back({right, id});
graph[right].push_back({left, id});
}
std::vector<int> entered(vertex_count, -1);
std::vector<int> low(vertex_count);
std::vector<std::pair<int, int>> bridges;
int timer = 0;
std::function<void(int, int)> search = [&](int node, int parent_edge) {
entered[node] = low[node] = timer++;
for (const auto& edge : graph[node]) {
const int neighbor = edge.first;
const int edge_id = edge.second;
if (edge_id == parent_edge) {
continue;
}
if (entered[neighbor] >= 0) {
// A back edge may connect this subtree to an ancestor.
low[node] = std::min(low[node], entered[neighbor]);
continue;
}
search(neighbor, edge_id);
low[node] = std::min(low[node], low[neighbor]);
if (low[neighbor] > entered[node]) {
// The child subtree has no route around this tree edge.
bridges.push_back(std::minmax(node, neighbor));
}
}
};
for (int node = 0; node < vertex_count; ++node) {
if (entered[node] < 0) {
search(node, -1);
}
}
std::sort(bridges.begin(), bridges.end());
return bridges;
}