Graphs¶
A graph \(G = (V, E)\) is a set of vertices together with a set of edges connecting pairs of them. That's all — and that's exactly why graphs are so powerful. Road networks, social networks, the web, circuits, course prerequisites, the moves of a puzzle, the states of a game, the pixels of an image: all of them are graphs once you decide what the vertices and edges are.
This chapter has two goals. The first is to master a small toolkit of classical algorithms — breadth-first search, depth-first search, topological sort, minimum spanning trees, shortest paths — each of which runs in (nearly) linear time. The second, and more important, is to learn to model: to look at a problem that doesn't mention graphs at all and see which graph, and which classical question about it, the problem is secretly asking.
Take-Home Lesson
Designing novel graph algorithms is very hard, so don't do it. Instead, design graphs that let you use classical algorithms. Most graph interview problems are one of a dozen standard algorithms applied to a cleverly chosen graph.
Flavors of Graphs¶
The first step in any graph problem is to identify what kind of graph you have, because it determines which algorithms apply.
| Property | Question to ask | Why it matters |
|---|---|---|
| Directed vs. undirected | Does an edge \((x, y)\) imply \((y, x)\)? | Prerequisites, one-way streets, and "follows" relations are directed. Cycle detection and connectivity work differently. |
| Weighted vs. unweighted | Do edges have costs? | Unweighted shortest paths: BFS. Weighted: Dijkstra and friends. |
| Sparse vs. dense | Is \(E\) closer to \(V\) or to \(V^2\)? | Chooses the representation, and between some algorithms. |
| Cyclic vs. acyclic | Can you return to where you started? | Directed acyclic graphs (DAGs) admit topological order, which makes many hard problems easy. Trees are connected acyclic undirected graphs. |
| Implicit vs. explicit | Is the graph given, or generated by rules? | Grids, puzzle states, and word ladders are graphs you never build in full; you generate neighbors on demand. |
| Simple vs. non-simple | Self-loops \((x, x)\)? Repeated edges? | Many implementations quietly assume a simple graph. |
Representations¶
| Adjacency list | Adjacency matrix | Edge list | |
|---|---|---|---|
| Space | \(O(V + E)\) | \(O(V^2)\) | \(O(E)\) |
| Is \((x, y)\) an edge? | \(O(\deg x)\) | \(O(1)\) | \(O(E)\) |
| Iterate over neighbors of \(x\) | \(O(\deg x)\) | \(O(V)\) | \(O(E)\) |
| Best for | Almost everything | Dense graphs, Floyd–Warshall | Kruskal, Bellman–Ford |
Take-Home Lesson
Adjacency lists are the right data structure for most applications of graphs. Traversal algorithms spend their time iterating over neighbors, and adjacency lists make that proportional to the number of edges that actually exist.
In Python, an adjacency list is a list of lists (vertices numbered \(0 \dots n - 1\)) or a defaultdict(list) (arbitrary hashable labels):
from collections import defaultdict
def build_adjacency_list(n: int, edges: list[list[int]], directed: bool = False) -> list[list[int]]:
graph: list[list[int]] = [[] for _ in range(n)]
for u, v in edges:
graph[u].append(v)
if not directed:
graph[v].append(u)
return graph
def build_weighted(edges: list[tuple[str, str, int]]) -> dict[str, list[tuple[str, int]]]:
graph: dict[str, list[tuple[str, int]]] = defaultdict(list)
for u, v, w in edges:
graph[u].append((v, w))
return graph
A grid is an implicit graph: each cell is a vertex, and its neighbors are computed from coordinates, never stored.
DIRECTIONS = [(0, 1), (1, 0), (0, -1), (-1, 0)]
def grid_neighbors(r: int, c: int, rows: int, cols: int):
for dr, dc in DIRECTIONS:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols:
yield nr, nc
Traversal: The Master Algorithm¶
Visiting every vertex and edge systematically is the foundation of nearly every graph algorithm. The key idea is to mark vertices so that we never get lost going around in circles. Each vertex passes through three states:
- Undiscovered — not yet seen.
- Discovered — seen, but its edges haven't all been explored.
- Processed — all its edges have been explored.
Keep the discovered-but-unprocessed vertices in a container. Repeatedly take a vertex out, and for each edge leading to an undiscovered vertex, mark that vertex discovered and add it to the container.
Why does this visit everything reachable? Suppose some reachable vertex is never visited, and let \(u\) be the first unvisited vertex on a path from the start. Its predecessor \(v\) on that path was visited — but when \(v\) was processed, it would have discovered \(u\). Contradiction.
Every traversal takes \(O(V + E)\) time: each vertex enters the container once, and each edge is examined once from each endpoint. That's optimal — you can't even read the graph faster. Anything you can do with one or two traversals is linear time.
The remarkable thing is that the order of exploration is decided entirely by the container:
- A queue (FIFO) explores the oldest discoveries first. Exploration radiates outward in rings from the start: breadth-first search.
- A stack (LIFO) explores the newest discoveries first. Exploration plunges down a path and backs up only when stuck: depth-first search.
For some problems the choice doesn't matter (reachability, counting components). For others it's everything: BFS finds shortest paths; DFS reveals cycles and dependency order.
Breadth-First Search¶
from collections import deque
def bfs(graph: list[list[int]], start: int) -> tuple[list[int], list[int]]:
"""Return (dist, parent): hop distance from start and the BFS tree (-1 = none)."""
n = len(graph)
dist = [-1] * n
parent = [-1] * n
dist[start] = 0
queue = deque([start])
while queue:
u = queue.popleft()
for v in graph[u]:
if dist[v] == -1: # undiscovered
dist[v] = dist[u] + 1
parent[v] = u
queue.append(v)
return dist, parent
def reconstruct_path(parent: list[int], target: int) -> list[int]:
path = []
while target != -1:
path.append(target)
target = parent[target]
return path[::-1]
Mark when you enqueue, not when you dequeue
Marking a vertex as seen only when it's popped lets the same vertex be enqueued many times — once from each neighbor that discovers it before it's processed. On dense graphs and grids, this can blow up both time and memory.
Shortest paths in unweighted graphs¶
BFS discovers vertices in order of increasing distance: all vertices at distance 1, then all at distance 2, and so on. So the first time a vertex is discovered, it's by a shortest path, and the parent pointers form a shortest-path tree rooted at the start. Two caveats: the tree gives shortest paths from the start vertex only, and only when all edges have equal weight.
Shortest Path in Binary Matrix (LC 1091) is BFS on an 8-connected grid; Minimum Knight Moves (LC 1197) is BFS on the implicit graph of knight moves.
Multi-source BFS¶
To compute each vertex's distance to the nearest of several sources, put all the sources in the queue at distance 0 and run a single BFS. It's as if a super-source were connected to all of them with zero-length edges. Rotting Oranges (LC 994), Walls and Gates (LC 286), and 01 Matrix (LC 542) all work this way.
def oranges_rotting(grid: list[list[int]]) -> int:
rows, cols = len(grid), len(grid[0])
queue = deque((r, c) for r in range(rows) for c in range(cols) if grid[r][c] == 2)
fresh = sum(row.count(1) for row in grid)
minutes = 0
while queue and fresh:
minutes += 1
for _ in range(len(queue)): # one ring = one minute
r, c = queue.popleft()
for nr, nc in grid_neighbors(r, c, rows, cols):
if grid[nr][nc] == 1:
grid[nr][nc] = 2
fresh -= 1
queue.append((nr, nc))
return -1 if fresh else minutes
Two-coloring: is the graph bipartite? (LC 785)¶
A graph is bipartite if its vertices can be colored with two colors so that every edge joins different colors. Color the start vertex arbitrarily; every neighbor is then forced to take the other color, and so on outward. BFS propagates the forced colors; if some edge ever joins two vertices of the same color, no two-coloring exists. (Equivalently: a graph is bipartite iff it has no odd-length cycle.)
def is_bipartite(graph: list[list[int]]) -> bool:
color = [-1] * len(graph)
for start in range(len(graph)): # the graph may be disconnected
if color[start] != -1:
continue
color[start] = 0
queue = deque([start])
while queue:
u = queue.popleft()
for v in graph[u]:
if color[v] == -1:
color[v] = 1 - color[u]
queue.append(v)
elif color[v] == color[u]:
return False
return True
Implicit graphs: searching a state space¶
Many puzzles are shortest-path problems on a graph that's never written down. The vertices are states, the edges are moves, and BFS generates neighbors on the fly.
Open the Lock (LC 752): a state is a 4-digit combination; each move turns one wheel up or down, giving 8 neighbors. The whole graph has \(10^4\) vertices — small enough for BFS, though no one would build it explicitly.
def open_lock(deadends: list[str], target: str) -> int:
dead = set(deadends)
if "0000" in dead:
return -1
seen = {"0000"}
queue = deque([("0000", 0)])
while queue:
state, moves = queue.popleft()
if state == target:
return moves
for i in range(4):
d = int(state[i])
for step in (1, -1):
nxt = state[:i] + str((d + step) % 10) + state[i + 1:]
if nxt not in seen and nxt not in dead:
seen.add(nxt)
queue.append((nxt, moves + 1))
return -1
Word Ladder (LC 127) is the same idea with words as states and single-letter changes as moves. When the state space is large, bidirectional BFS — searching from both ends and stopping when the frontiers meet — explores roughly \(2 b^{d/2}\) states instead of \(b^d\).
Depth-First Search¶
DFS is BFS with a stack instead of a queue — and since recursion is a stack, DFS has a beautifully short recursive form:
def dfs_order(graph: list[list[int]], start: int) -> list[int]:
visited: set[int] = set()
order: list[int] = []
def dfs(u: int) -> None:
visited.add(u)
order.append(u) # "process vertex early": pre-order
for v in graph[u]:
if v not in visited:
dfs(v)
# "process vertex late" would go here: post-order
dfs(start)
return order
DFS is essentially the same procedure as backtracking (see Combinatorial Search): advance whenever possible, back up only when every option is exhausted.
Recursion depth
Recursive DFS on a long path of \(10^5\) vertices exceeds Python's recursion limit. For large graphs, either use an explicit stack or sys.setrecursionlimit (and be aware that very deep recursion can still crash the interpreter).
Why DFS is special: entry/exit times and edge classes¶
Give DFS a clock that ticks each time a vertex is entered or exited. If \(x\) is an ancestor of \(y\) in the DFS tree, then \(x\) is entered before \(y\) and exited after \(y\) — the intervals \([\text{entry}, \text{exit}]\) nest like parentheses.
More importantly, DFS sorts the edges of an undirected graph into just two classes:
- Tree edges, which discover new vertices.
- Back edges, which lead to an ancestor in the DFS tree.
There are no "cross edges" between unrelated branches. Why? If \(u\) has an edge to \(v\) and \(v\) is still undiscovered when \(u\) is explored, DFS will discover \(v\) from \(u\) — making it a tree edge. By the time DFS leaves \(u\), everything reachable from \(u\) has been explored.
Take-Home Lesson
DFS organizes vertices by entry and exit times, and edges into tree and back edges. That organization — not the traversal itself — is where DFS gets its power: cycle detection, topological sorting, articulation points, and strongly connected components all come from it.
Connected components and flood fill¶
Starting a traversal from each still-unvisited vertex partitions the graph into its connected components. A surprising number of problems reduce to counting or labeling components. Number of Islands (LC 200) is exactly this on a grid:
def num_islands(grid: list[list[str]]) -> int:
rows, cols = len(grid), len(grid[0])
def sink(r: int, c: int) -> None:
stack = [(r, c)] # iterative: islands can be large
grid[r][c] = "0"
while stack:
r, c = stack.pop()
for nr, nc in grid_neighbors(r, c, rows, cols):
if grid[nr][nc] == "1":
grid[nr][nc] = "0" # mark on discovery
stack.append((nr, nc))
islands = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == "1":
islands += 1
sink(r, c)
return islands
Reverse the question. In Surrounded Regions (LC 130), rather than asking "is this region surrounded?", flood-fill from every border O and mark what's reachable; everything unmarked is surrounded. In Pacific Atlantic Water Flow (LC 417), rather than simulating water flowing downhill from every cell, flow uphill from each ocean's border and intersect the two reachable sets. Starting from the targets is often dramatically simpler than starting from every source.
Cycle detection¶
A lot depends on whether a graph has cycles. A topological order exists only in a DAG, a tree is a connected graph with no cycle, and a cycle in a "waits for" graph is a deadlock. Directed and undirected graphs use the same test: a graph has a cycle iff DFS finds a back edge. The only difference is how you recognize a back edge.
Undirected graphs. An undirected DFS has no cross edges (see above), so every edge that doesn't discover a new vertex leads to an ancestor. A cycle therefore exists iff DFS reaches an already-visited vertex other than its parent. The parent is excluded because every undirected edge appears in both adjacency lists. From \(v\) you always see the edge back to the \(u\) that discovered it, but that's the tree edge you just walked, not a cycle. The test is correct in both directions:
- Back edge ⇒ cycle. If \((u, v)\) is a back edge, \(v\) is an ancestor of \(u\). The tree path \(v \to \dots \to u\) plus the edge \((u, v)\) forms a cycle.
- No back edge ⇒ no cycle. If every edge is a tree edge, the graph is a forest.
def has_cycle_undirected(graph: list[list[int]]) -> bool:
visited = [False] * len(graph)
def dfs(current: int, parent: int) -> bool:
visited[current] = True
for neighbor in graph[current]:
if neighbor == parent:
continue # the tree edge we arrived on
if visited[neighbor]:
return True # back edge to an ancestor
if dfs(neighbor, current):
return True
return False
for start in range(len(graph)): # the graph may be disconnected
if not visited[start] and dfs(start, -1):
return True
return False
The test skips the parent by vertex, which assumes a simple graph. In a multigraph, two parallel edges between \(u\) and \(v\) form a cycle of length 2, but neighbor == parent skips both copies. If the input can contain duplicate edges, skip the parent only once, or identify edges by index instead of by endpoint. Self-loops are caught: \(u\) is visited and isn't its own parent.
Two shortcuts avoid writing a DFS at all:
- Counting. A forest with \(V\) vertices and \(C\) components has exactly \(V - C\) edges, and any additional edge closes a cycle. So a simple undirected graph has a cycle iff \(E > V - C\). Graph Valid Tree (LC 261) reduces to "\(E = V - 1\) and the graph is connected."
- Union-find. When edges arrive one at a time, an edge closes a cycle iff its endpoints are already in the same component. Kruskal's algorithm uses this test to reject edges, and Redundant Connection (LC 684) asks for exactly the edge that closes the first cycle. See Trie & Union Find.
Directed graphs. The undirected test fails here: in the graph \(a \to b\), \(a \to c\), \(c \to b\), DFS reaches \(b\) a second time, but there's no cycle. A directed DFS sorts edges into four classes, not two. Each edge current → neighbor is classified by the state of neighbor at the moment DFS explores the edge:
State of neighbor |
Edge class | Meaning |
|---|---|---|
| White: undiscovered | Tree edge | DFS discovers neighbor from current |
| Gray: discovered, not finished | Back edge | neighbor is an ancestor, still on the recursion stack |
| Black: finished | Forward or cross edge | neighbor is a finished descendant, or belongs to a finished branch |
Only back edges signal a cycle:
- Back edge ⇒ cycle. A gray
neighboris an ancestor ofcurrent. The tree pathneighbor → … → currentplus the edgecurrent → neighborforms a cycle. - Cycle ⇒ back edge. Let \(v\) be the first vertex of the cycle that DFS discovers. At that moment, every other vertex on the cycle is white and reachable from \(v\), so DFS discovers all of them before it finishes \(v\). That includes the vertex \(u\) whose edge closes the cycle, \(u \to v\). When DFS explores that edge, \(v\) is still gray, so it's a back edge.
- Edges to black vertices are harmless. A finished vertex has already explored everything reachable from it. If it could reach back into the current path, that exploration would already have found a back edge.
Three colors are the minimum needed to tell these classes apart. A single visited set merges gray and black, and so reports forward and cross edges as cycles. Gray vertices are exactly the current DFS path, so keeping that path on a list makes it easy to return the cycle itself rather than just a yes or no:
WHITE, GRAY, BLACK = 0, 1, 2 # undiscovered, on the current path, finished
def find_cycle_directed(graph: list[list[int]]) -> list[int] | None:
"""Return the vertices of a directed cycle in order, or None if the graph is a DAG."""
color = [WHITE] * len(graph)
path: list[int] = [] # the gray vertices, from the DFS root down
def dfs(current: int) -> list[int] | None:
color[current] = GRAY
path.append(current)
for neighbor in graph[current]:
if color[neighbor] == GRAY: # back edge: the cycle runs from neighbor to current
return path[path.index(neighbor):]
if color[neighbor] == WHITE:
cycle = dfs(neighbor)
if cycle is not None:
return cycle
# BLACK: forward or cross edge, harmless
path.pop()
color[current] = BLACK
return None
for start in range(len(graph)): # the graph may be disconnected
if color[start] == WHITE:
cycle = dfs(start)
if cycle is not None:
return cycle
return None
If you only need a yes or no, drop path and return booleans. The same DFS also gives you a topological order for free: record each vertex as it turns black, then reverse the list (see Via DFS: reverse post-order). The colors also answer Find Eventual Safe States (LC 802), which asks for the vertices from which no cycle can be reached. A vertex is safe iff its DFS turns it black without ever meeting a gray vertex.
Without recursion, Kahn's algorithm detects directed cycles too: a cycle exists iff some vertices never reach in-degree zero (see Via in-degrees: Kahn's algorithm). Not every leftover vertex is on a cycle, though; some are only downstream of one. Course Schedule (LC 207) is solved either way.
| Situation | Method | Example |
|---|---|---|
| Undirected, whole graph given | DFS that skips the parent, or \(E > V - C\) | Graph Valid Tree (LC 261) |
| Undirected, edges arrive one at a time | Union-find | Redundant Connection (LC 684) |
| Directed, yes/no or a topological order | Three-color DFS, or Kahn's algorithm | Course Schedule (LC 207) |
| Directed, which vertices can reach a cycle | Three-color DFS | Find Eventual Safe States (LC 802) |
| Every vertex has out-degree 1 (linked list, functional graph) | Floyd's tortoise and hare, \(O(1)\) space | Linked List Cycle (LC 141), Find the Duplicate Number (LC 287) |
| Is there an odd cycle? | Two-coloring | Is Graph Bipartite? (LC 785) |
Weak points: bridges and articulation vertices¶
An articulation vertex is one whose removal disconnects the graph; a bridge is such an edge. They are single points of failure in a network. DFS finds all of them in one pass, tracking two numbers per vertex:
- \(\text{discovery\_order}(v)\): when DFS first reaches \(v\).
- \(\text{low}(v)\): the smallest discovery order reachable from \(v\)'s subtree by going down tree edges and then up at most one back edge. It measures how high \(v\)'s subtree can climb without using the edge to \(v\)'s parent.
Because an undirected DFS has no cross edges, deleting a vertex \(u\) can only cut off subtrees of its children: a child's subtree stays attached only if one of its back edges climbs above \(u\). Leaves of the DFS tree are never articulation vertices, since deleting one leaves the rest of the tree intact. For every other vertex, one of three cases applies:
- Root case. The root is an articulation vertex iff it has two or more children in the DFS tree. With no cross edges, the only connection between its subtrees is the root itself. A root with one child can be deleted safely. The
lowtest below doesn't work at the root: nothing sits above it, so \(\text{low}(v) \ge \text{discovery\_order}(\text{root})\) always holds. - Parent case. If \(\text{low}(v) = \text{discovery\_order}(u)\) for some child \(v\), then \(v\)'s subtree can climb back to \(u\) but no higher. Deleting \(u\) strands that subtree, so \(u\) is an articulation vertex (unless it's the root, which case 1 handles).
- Bridge case. If \(\text{low}(v) = \text{discovery\_order}(v)\), then nothing below \(v\) even reaches \(u\), so \((u, v)\) is a bridge. Both of its endpoints are articulation vertices, except for one that is a leaf (\(v\) with no children) or a root with only this child (\(u\)).
Cases 2 and 3 combine into one test: a non-root \(u\) is an articulation vertex iff some child \(v\) has \(\text{low}(v) \ge \text{discovery\_order}(u)\). That covers \(v\) in case 3 too, since \(v\)'s own children satisfy the test against \(v\). A vertex can pass the test for several children, so record the results in a boolean array and not a list:
def articulation_vertices(n: int, edges: list[list[int]]) -> list[int]:
graph = build_adjacency_list(n, edges)
discovery_order = [-1] * n # -1 = unvisited
low = [0] * n # min discovery_order reachable with ≤ 1 back edge
is_articulation = [False] * n
discovery_time = 0
def dfs(current: int, parent: int) -> None:
nonlocal discovery_time
discovery_order[current] = low[current] = discovery_time
discovery_time += 1
children = 0
for neighbor in graph[current]:
if neighbor == parent:
continue
if discovery_order[neighbor] == -1: # tree edge
children += 1
dfs(neighbor, current)
low[current] = min(low[current], low[neighbor])
if parent != -1 and low[neighbor] >= discovery_order[current]:
is_articulation[current] = True # parent or bridge case
else: # back edge
low[current] = min(low[current], discovery_order[neighbor])
if parent == -1 and children >= 2:
is_articulation[current] = True # root case
for s in range(n):
if discovery_order[s] == -1:
dfs(s, -1)
return [vertex for vertex in range(n) if is_articulation[vertex]]
Bridges come from the same DFS with a stricter test: a tree edge \((u, v)\) is a bridge iff \(\text{low}(v) > \text{discovery\_order}(u)\), meaning no back edge from \(v\)'s subtree reaches \(u\) or any of its ancestors. Critical Connections (LC 1192) asks for exactly these:
def critical_connections(n: int, connections: list[list[int]]) -> list[list[int]]:
graph = build_adjacency_list(n, connections)
discovery_order = [-1] * n # -1 = unvisited
low = [0] * n # min discovery_order reachable with ≤ 1 back edge
bridges = []
discovery_time = 0
def dfs(current: int, parent: int) -> None:
nonlocal discovery_time
discovery_order[current] = low[current] = discovery_time
discovery_time += 1
for neighbor in graph[current]:
if neighbor == parent:
continue
if discovery_order[neighbor] == -1: # tree edge
dfs(neighbor, current)
low[current] = min(low[current], low[neighbor])
if low[neighbor] > discovery_order[current]:
bridges.append([current, neighbor])
else: # back edge
low[current] = min(low[current], discovery_order[neighbor])
for s in range(n):
if discovery_order[s] == -1:
dfs(s, -1)
return bridges
LC 1192 allows \(10^5\) vertices, so on a long chain this recursion exceeds Python's default limit (see the recursion-depth warning above).
Topological Sorting¶
A topological order of a directed graph lists its vertices so that every edge points forward, from earlier to later. If edges mean "must happen before," a topological order is a valid schedule. It exists iff the graph is a DAG: a cycle would require going forward forever and still returning to the start.
Topological sorting is the most important operation on DAGs, because it lets you process each vertex after everything that points to it. Shortest paths, longest paths, and counting paths in a DAG all become a single left-to-right pass in topological order — even with negative weights.
Via DFS: reverse post-order¶
List the vertices in the order DFS finishes them, then reverse. Why is that a topological order? Consider any edge \((x, y)\) at the moment DFS explores it from \(x\):
- If \(y\) is undiscovered, DFS finishes \(y\) before returning to finish \(x\). ✓
- If \(y\) is already finished, it finished before \(x\) will. ✓
- If \(y\) is discovered but unfinished, it's an ancestor on the stack — a back edge, which means a cycle, which is impossible in a DAG.
In every legal case, \(y\) finishes before \(x\), so after reversing, \(x\) comes before \(y\). In code, it's a plain DFS that records each vertex as it finishes:
def topological_sort_dfs(graph: list[list[int]]) -> list[int]:
"""Assumes a DAG; use the three-color DFS from Cycle detection if it may not be one."""
visited = [False] * len(graph)
finished: list[int] = []
def dfs(current: int) -> None:
visited[current] = True
for neighbor in graph[current]:
if not visited[neighbor]:
dfs(neighbor)
finished.append(current) # post-order: every successor is already in
for start in range(len(graph)):
if not visited[start]:
dfs(start)
return finished[::-1]
Via in-degrees: Kahn's algorithm¶
A vertex with no incoming edges can safely go first. Remove it, which may free up others, and repeat. If vertices remain but none has in-degree zero, they contain a cycle.
def topological_sort(n: int, edges: list[list[int]]) -> list[int] | None:
"""Kahn's algorithm. edges[i] = [u, v] means u must come before v."""
graph: list[list[int]] = [[] for _ in range(n)]
indegree = [0] * n
for u, v in edges:
graph[u].append(v)
indegree[v] += 1
queue = deque(u for u in range(n) if indegree[u] == 0)
order = []
while queue:
u = queue.popleft()
order.append(u)
for v in graph[u]:
indegree[v] -= 1
if indegree[v] == 0:
queue.append(v)
return order if len(order) == n else None # None: there's a cycle
Course Schedule (LC 207) asks whether the order exists; Course Schedule II (LC 210) asks for it. Kahn's algorithm also answers "what's the minimum number of semesters?" (process the queue level by level, as in BFS) and "is the order unique?" (the queue never holds more than one vertex).
Stop and Think: Ordering the fragments
Problem: A DNA sequencing experiment produces fragments. For some pairs you know that fragment \(a\) must lie to the left of fragment \(b\). Find a left-to-right ordering consistent with all the constraints.
Solution: Make each fragment a vertex, and add a directed edge \(a \to b\) for each "left of" constraint. A consistent ordering is exactly a topological sort of this graph; if the graph has a cycle, the constraints are contradictory. Alien Dictionary (LC 269) is the same problem: compare adjacent words to extract "letter \(x\) comes before letter \(y\)" edges, then topologically sort the letters.
Strongly connected components¶
A directed graph is strongly connected if every vertex can reach every other. Its strongly connected components (SCCs) are the maximal strongly connected pieces. Contracting each SCC to a single vertex gives the condensation, which is always a DAG: a cycle through two components would make them one component.
Key idea: a DFS started in a sink component visits exactly that component. A sink component has no edges leaving it, so the DFS cannot escape, and strong connectivity means it reaches every vertex inside. Starting each DFS in a sink component therefore produces one SCC per search tree. Once a component is marked, the DFS ignores it, so another component becomes a sink, and the process repeats. The only problem is finding a vertex in a sink component without already knowing the components. Finish times solve it.
Finish-time lemma. Write \(f(C)\) for the latest finish time of any vertex in component \(C\). If the condensation has an edge \(C \to C'\), then \(f(C) > f(C')\).
Proof: consider which of the two components DFS enters first.
- \(C\) first, at vertex \(x\). At that moment every vertex of \(C\) and \(C'\) is undiscovered and reachable from \(x\), so all of them become descendants of \(x\) and finish before \(x\).
- \(C'\) first. \(C\) is not reachable from \(C'\): together with the edge \(C \to C'\), that would put both on a cycle. So DFS finishes all of \(C'\) before it discovers any vertex of \(C\).
So the vertex that finishes last lies in a source component, one with no incoming edges. We need a sink, and reversing every edge provides one. The reversed graph \(G^R\) has the same SCCs (a reversed cycle is still a cycle), but every condensation edge points the other way, so sources of \(G\) are sinks of \(G^R\).
Kosaraju's algorithm therefore makes two passes:
- DFS on \(G\), recording vertices in the order they finish.
- DFS on \(G^R\), starting from unassigned vertices in decreasing finish order. Each search tree is one SCC.
Pass 2 stays correct after the first component. Let \(x\) be the unassigned vertex with the latest finish, and let \(C\) be its component. In \(G^R\), the edges leaving \(C\) lead to components \(C'\) that have an edge \(C' \to C\) in \(G\). By the lemma, \(f(C') > f(C)\), so \(C'\) has already been assigned. The search from \(x\) therefore reaches only \(C\), plus already-assigned vertices that it skips. Both passes and building \(G^R\) take \(O(V + E)\).
Stop and Think: Why not skip the reversal?
Problem: The lemma says the last vertex to finish lies in a source component. Doesn't that make the vertex that finishes first lie in a sink component? Then pass 2 could run on \(G\) itself, in increasing finish order.
Solution: No. The lemma compares only the latest finish time of each component; it says nothing about the earliest. Take the edges \(0 \to 1\), \(1 \to 0\), \(0 \to 2\), and run DFS from \(0\), visiting \(1\) first. The finish order is \(1, 2, 0\). Vertex \(1\) finishes first, but its component \(\{0, 1\}\) is a source: a DFS from \(1\) on \(G\) reaches \(2\) as well and merges two SCCs. Only the latest finish is reliable, which is why the algorithm reverses the graph rather than the order.
def strongly_connected_components(graph: list[list[int]]) -> list[list[int]]:
n = len(graph)
finished: list[int] = []
seen = [False] * n
for s in range(n): # pass 1: finish order on G
if seen[s]:
continue
seen[s] = True
stack = [(s, iter(graph[s]))]
while stack:
u, it = stack[-1]
v = next(it, None)
if v is None: # all neighbors explored: u finishes
stack.pop()
finished.append(u)
elif not seen[v]:
seen[v] = True
stack.append((v, iter(graph[v])))
reverse: list[list[int]] = [[] for _ in range(n)]
for u in range(n):
for v in graph[u]:
reverse[v].append(u)
comp = [-1] * n
components = []
for s in reversed(finished): # pass 2: DFS on reversed G
if comp[s] != -1:
continue
comp[s] = len(components)
members, stack = [], [s]
while stack:
u = stack.pop()
members.append(u)
for v in reverse[u]:
if comp[v] == -1:
comp[v] = comp[s]
stack.append(v)
components.append(members)
return components
Pass 1 needs true finish times, so it cannot use the plain stack from flood fill: popping a vertex there says nothing about whether its descendants are done. Instead, each stack entry holds a vertex together with an iterator over its unexplored neighbors. A vertex finishes when its iterator runs out, which is exactly when the recursive call would return. Pass 2 only collects reachable vertices, so the plain stack is enough there.
Tarjan's algorithm finds the same components in a single DFS, using low-link values like those in Weak points. Kosaraju's two passes are easier to get right in an interview.
Minimum Spanning Trees¶
A spanning tree of a connected graph is a subset of \(V - 1\) edges connecting all the vertices without a cycle. The minimum spanning tree (MST) is the one of least total weight: the cheapest way to connect everything — cities with roads, houses with cable, points with wire.
Two greedy algorithms find it. Greedy algorithms are usually suspect (see Intervals), so both come with a proof. The key fact behind both:
Cut property. Split the vertices into two groups. The lightest edge crossing between them belongs to some MST.
Proof by exchange: take an MST that doesn't contain the lightest crossing edge \(e\). Adding \(e\) creates a cycle, and that cycle must cross the split a second time through some edge \(f\). Since \(e\) is the lightest crossing edge, \(w(e) \le w(f)\). Swapping \(f\) for \(e\) gives a spanning tree no heavier than before — so an MST containing \(e\) exists.
Prim's algorithm¶
Grow a single tree from any start vertex. Repeatedly add the cheapest edge leaving the tree — the lightest edge across the cut (tree, everything else). A heap holds the candidate edges; stale entries for vertices already in the tree are skipped.
import heapq
def prim_mst_weight(n: int, graph: list[list[tuple[int, int]]]) -> int:
"""graph[u] = [(v, w), ...] for an undirected connected graph."""
in_tree = [False] * n
heap = [(0, 0)] # (edge weight, vertex)
total = 0
while heap:
w, u = heapq.heappop(heap)
if in_tree[u]:
continue # stale entry
in_tree[u] = True
total += w
for v, wv in graph[u]:
if not in_tree[v]:
heapq.heappush(heap, (wv, v))
return total
\(O(E \log E)\): this is the lazy variant, which pushes every edge leaving the tree instead of decreasing keys, so the heap can hold \(O(E)\) entries. Since \(E < V^2\), \(\log E < 2 \log V\), so this matches the \(O(E \log V)\) of the decrease-key version.
For dense graphs — such as Min Cost to Connect All Points (LC 1584), where every pair of points is an edge — \(E \approx V^2 / 2\), and the heap only adds overhead. Drop it: keep, for every vertex outside the tree, the cheapest edge connecting it to the tree, and find the next vertex with a linear scan.
from typing import Callable
def prim_dense(n: int, cost: Callable[[int, int], int]) -> int:
"""MST weight of the complete graph on n vertices, with edge weights cost(u, v)."""
in_tree = [False] * n
cheapest = [float("inf")] * n # lightest edge from the tree to each vertex
cheapest[0] = 0
total = 0
for _ in range(n):
u = min((v for v in range(n) if not in_tree[v]), key=lambda v: cheapest[v])
in_tree[u] = True
total += cheapest[u]
for v in range(n): # u joined the tree: update the other vertices
if not in_tree[v]:
cheapest[v] = min(cheapest[v], cost(u, v))
return total
\(V\) rounds of \(O(V)\) work: \(O(V^2)\) time and \(O(V)\) space, with edge weights computed on demand rather than stored. For LC 1584, cost is the Manhattan distance between points[u] and points[v].
Kruskal's algorithm¶
Sort all edges by weight. Take each edge in order, unless it would close a cycle. Each accepted edge is the lightest one leaving its endpoint's component, so the cut property applies. To check "would this close a cycle?" — are the endpoints already in the same component? — use a union-find structure (see Trie & Union Find), which answers it in nearly constant time.
def kruskal_mst_weight(n: int, edges: list[tuple[int, int, int]]) -> int:
"""edges = [(u, v, w), ...] for an undirected connected graph."""
parent = list(range(n))
def find(x: int) -> int:
while parent[x] != x:
parent[x] = parent[parent[x]] # path halving
x = parent[x]
return x
total = used = 0
for u, v, w in sorted(edges, key=lambda edge: edge[2]):
ru, rv = find(u), find(v)
if ru != rv:
parent[ru] = rv
total += w
used += 1
if used == n - 1:
break
return total
\(O(E \log E)\), dominated by the sort. Kruskal is usually the simpler choice for sparse graphs given as an edge list.
Variations fall out of the same algorithms: a maximum spanning tree is an MST on negated weights; the minimax path (minimize the heaviest edge on a path) follows the MST; and stopping Kruskal early at \(k\) components gives single-linkage clustering.
Shortest Paths¶
BFS finds shortest paths only when every edge costs the same. With weights, the shortest path might use many cheap edges rather than a few expensive ones.
Dijkstra's algorithm¶
Dijkstra's algorithm is Prim's algorithm with a different notion of "cheapest." Prim adds the vertex attached by the lightest edge; Dijkstra adds the vertex with the smallest total distance from the source. It maintains tentative distances and repeatedly finalizes the closest unfinalized vertex, relaxing its outgoing edges.
def dijkstra(graph: list[list[tuple[int, int]]], source: int) -> list[float]:
dist = [float("inf")] * len(graph)
dist[source] = 0
heap = [(0, source)]
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]:
continue # stale entry: u already finalized with a shorter d
for v, w in graph[u]:
if d + w < dist[v]: # relax edge (u, v)
dist[v] = d + w
heapq.heappush(heap, (dist[v], v))
return dist
Time: \(O((V + E) \log E)\), which is \(O((V + E) \log V)\) since \(\log E < 2 \log V\). Python's heapq can't decrease a key, so this uses lazy deletion: push a new entry on every improvement and skip entries that are out of date when popped. The heap can therefore hold up to \(O(E)\) entries rather than \(V\).
Why it's correct: when \(u\) is popped with distance \(d\), every other path to \(u\) must leave the set of finalized vertices through some vertex whose tentative distance is already \(\ge d\) (otherwise it would have been popped first), and continuing from there can only add more. That argument needs one assumption: no negative edges. A negative edge could make a longer-looking detour cheaper after \(u\) was already finalized. (If the bank paid you to walk through its lobby, the shortest way to your neighbor's house might involve walking through it forever.)
Dijkstra adapts to many "shortest" notions, as long as extending a path never makes it better:
- Path With Minimum Effort (LC 1631): the cost of a path is its maximum step, so relax with
max(d, w)instead ofd + w. - Path with Maximum Probability (LC 1514): maximize a product of probabilities — use a max-heap, or Dijkstra on \(-\log p\).
- Swim in Rising Water (LC 778): minimize the maximum elevation along a path.
Stop and Think: Costs on vertices instead of edges
Problem: In a directed graph, each vertex has a cost, and a path's cost is the sum of the costs of the vertices on it. Find the cheapest path from \(s\) to \(t\).
Solution: You could modify Dijkstra's code to add vertex costs. But it's cleaner to leave the algorithm alone and change the graph: give each directed edge \((u, v)\) the weight \(\text{cost}(v)\). Every path's edge weight now equals the sum of its vertex costs (plus \(\text{cost}(s)\), a constant). Plain Dijkstra does the job. This is "design graphs, not algorithms" in miniature.
Negative edges and limited hops: Bellman–Ford¶
Bellman–Ford relaxes every edge, \(V - 1\) times. After round \(k\), every shortest path using at most \(k\) edges has been found; since shortest paths (without negative cycles) use at most \(V - 1\) edges, that's enough. If a \(V\)-th round still improves something, there's a negative cycle. \(O(VE)\).
The round structure is useful in its own right. Cheapest Flights Within K Stops (LC 787) wants the cheapest path with at most \(k + 1\) edges — exactly \(k + 1\) rounds of Bellman–Ford, relaxing from a snapshot of the previous round so that each round extends paths by only one edge:
def find_cheapest_price(n: int, flights: list[list[int]], src: int, dst: int, k: int) -> int:
dist = [float("inf")] * n
dist[src] = 0
for _ in range(k + 1):
prev = dist[:] # distances using one fewer edge
for u, v, w in flights:
if prev[u] + w < dist[v]:
dist[v] = prev[u] + w
return -1 if dist[dst] == float("inf") else int(dist[dst])
All pairs: Floyd–Warshall¶
To get the distance between every pair of vertices, number the vertices and let \(D_k[i][j]\) be the shortest path from \(i\) to \(j\) whose intermediate vertices all come from \(\{0, \dots, k\}\). Allowing vertex \(k\) as a new intermediate either helps or it doesn't:
This is dynamic programming (see Dynamic Programming). The full table would be 3-D, one \(V \times V\) layer per \(k\). But a single 2-D table updated in place is enough. Round \(k\) reads only row \(k\) and column \(k\), and those don't change during round \(k\): \(D[i][k] = \min(D[i][k],\ D[i][k] + D[k][k])\), and \(D[k][k] = 0\). So the code is three nested loops over one table:
def floyd_warshall(n: int, edges: list[tuple[int, int, int]]) -> list[list[float]]:
INF = float("inf")
dist = [[0 if i == j else INF for j in range(n)] for i in range(n)]
for u, v, w in edges:
dist[u][v] = min(dist[u][v], w) # parallel edges: keep the lightest
for k in range(n): # k MUST be the outermost loop
for i in range(n):
for j in range(n):
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
return dist
\(O(V^3)\). On sparse graphs, running Dijkstra from every vertex is asymptotically faster (\(O(VE \log V)\)), but on dense graphs that becomes \(O(V^3 \log V)\), and Floyd–Warshall's tight loops win for \(V\) up to a few hundred. It handles negative edges, and detects negative cycles: one exists iff some \(D[i][i] < 0\) at the end. It also computes transitive closure — which vertices can reach which — as a byproduct: \(i\) reaches \(j\) iff \(D[i][j] < \infty\).
Which shortest-path algorithm?¶
| Situation | Algorithm | Time |
|---|---|---|
| Unweighted (or all weights equal) | BFS | \(O(V + E)\) |
| Weights 0 or 1 | 0-1 BFS (deque: push 0-edges front, 1-edges back) | \(O(V + E)\) |
| DAG, any weights | Relax edges in topological order | \(O(V + E)\) |
| Non-negative weights | Dijkstra | \(O(E \log V)\) |
| Negative edges, or at most \(k\) edges | Bellman–Ford | \(O(VE)\) or \(O(kE)\) |
| All pairs, \(V \lesssim 400\) | Floyd–Warshall | \(O(V^3)\) |
Network Flow and Matching (Briefly)¶
The problem. You're given a directed graph in which each edge \((u, v)\) is a pipe with a capacity \(c(u, v)\), plus a source \(s\) and a sink \(t\). A flow assigns each edge an amount \(f(u, v)\) subject to two rules:
- Capacity: \(0 \le f(u, v) \le c(u, v)\). No pipe carries more than it can hold.
- Conservation: at every vertex except \(s\) and \(t\), flow in equals flow out. Material is neither created nor stored along the way.
The value of the flow is the net amount leaving \(s\), which equals the amount arriving at \(t\). The maximum flow problem asks for the largest possible value: how much can be shipped from \(s\) to \(t\) per unit of time?
Why greedy fails. The natural idea is to find any path from \(s\) to \(t\) with spare capacity, push as much as it allows, and repeat. Take four unit-capacity edges \(s \to a\), \(s \to b\), \(a \to t\), \(b \to t\), plus a unit edge \(a \to b\). If the first path found is \(s \to a \to b \to t\), it uses up \(s \to a\) and \(b \to t\), and no other path remains: flow 1. The answer is 2, using \(s \to a \to t\) and \(s \to b \to t\). The first path routed its flow badly, and greedy can't take that back.
The fix: allow undoing. Search for paths in the residual graph. It has a forward edge wherever capacity is left, and a reverse edge \(v \to u\) wherever \((u, v)\) carries flow. Following a reverse edge cancels flow already sent. In the example, the residual graph contains \(s \to b \to a \to t\). Pushing one unit along it cancels the flow on \(a \to b\) and reroutes both units correctly. Such a path is an augmenting path, and repeating "find one, push along it" until none is left is the Ford–Fulkerson method. Finding each path with BFS (the shortest one) is Edmonds–Karp, which runs in \(O(VE^2)\).
def max_flow(n: int, edges: list[tuple[int, int, int]], source: int, sink: int) -> int:
"""Edmonds–Karp. edges = [(u, v, capacity), ...], directed."""
residual = [defaultdict(int) for _ in range(n)] # residual[u][v] = capacity left on u → v
for u, v, capacity in edges:
residual[u][v] += capacity
residual[v][u] += 0 # make sure the reverse edge exists
flow = 0
while True:
parent = [-1] * n # BFS for a shortest augmenting path
parent[source] = source
queue = deque([source])
while queue and parent[sink] == -1:
current = queue.popleft()
for neighbor, left in residual[current].items():
if left > 0 and parent[neighbor] == -1:
parent[neighbor] = current
queue.append(neighbor)
if parent[sink] == -1:
return flow # no augmenting path: flow is maximum
bottleneck, v = float("inf"), sink # the smallest capacity left on the path
while v != source:
bottleneck = min(bottleneck, residual[parent[v]][v])
v = parent[v]
v = sink # push it: forward edges shrink, reverse edges grow
while v != source:
residual[parent[v]][v] -= bottleneck
residual[v][parent[v]] += bottleneck
v = parent[v]
flow += bottleneck
The reverse entry residual[v][u] starts at 0 and grows by however much flow crosses \(u \to v\). That's what lets a later BFS find a path through it and cancel that flow.
Why the result is optimal: max-flow = min-cut. A cut splits the vertices into a side containing \(s\) and a side containing \(t\). Its capacity is the total capacity of the edges crossing from the \(s\) side to the \(t\) side. Every unit of flow has to cross every cut, so any flow ≤ any cut. When no augmenting path is left, the vertices still reachable from \(s\) in the residual graph form a cut whose edges are all saturated, so the flow equals that cut's capacity. Both are therefore optimal. The same computation answers "what is the cheapest set of edges whose removal disconnects \(s\) from \(t\)?"
Where it shows up: bipartite matching. To pair workers with jobs they're qualified for, as many pairs as possible: add a source with an edge to every worker, an edge from each worker to each job they can do, and an edge from every job to a sink, all with capacity 1. Each unit of flow is one worker–job pair, and capacity 1 stops anyone from being used twice. So the maximum flow is the maximum matching, and augmenting paths here become the "try to reassign someone" step of matching algorithms. Flow problems are uncommon in interviews, but they're worth recognizing in "assign X to Y" and "how many edges or vertices must be cut" problems, because spotting the reduction is usually the whole solution.
Design Graphs, Not Algorithms¶
The hardest part of most graph problems is noticing that they are graph problems, and choosing the vertices and edges so that a standard algorithm answers the question. Some examples:
| Problem | Vertices | Edges | Algorithm |
|---|---|---|---|
| Word Ladder (LC 127) | Words | Differ by one letter | BFS |
| Open the Lock (LC 752) | 4-digit combinations | One wheel turn | BFS |
| Bus Routes (LC 815) | Routes (not stops!) | Routes sharing a stop | BFS from routes containing the source |
| Evaluate Division (LC 399) | Variables | \(a \xrightarrow{a/b} b\), \(b \xrightarrow{b/a} a\) | DFS multiplying weights |
| Cheapest Flights Within K Stops (LC 787) | (city, stops used) | Flights | Dijkstra / Bellman–Ford |
| Shortest Path to Get All Keys (LC 864) | (cell, keys held as a bitmask) | Grid moves | BFS |
| Reconstruct Itinerary (LC 332) | Airports | Tickets | Eulerian path (Hierholzer) |
| Course Schedule (LC 207) | Courses | Prerequisites | Topological sort |
Two recurring tricks stand out. First, the obvious vertices are not always the right ones: in Bus Routes, making each route a vertex turns "fewest buses" into plain BFS. Second, when a constraint depends on history, put the history into the state: "at most \(k\) stops" or "holding these keys" become part of the vertex, and the enlarged graph is searched with the ordinary algorithm.
Eulerian paths: Reconstruct Itinerary (LC 332)¶
An Eulerian path uses every edge exactly once. In a directed graph whose edges are all connected, one exists iff every vertex has in-degree equal to out-degree, except possibly a start with one extra outgoing edge and an end with one extra incoming edge. LC 332 guarantees that a path exists and asks for the lexicographically smallest one.
Walking greedily (always the smallest unused ticket) can get stuck early. From JFK with tickets to KUL and NRT, and NRT → JFK, greedy flies to KUL and dead-ends with tickets left. Hierholzer's algorithm fixes this by emitting airports in post-order. An airport is added to the route only once it has no unused tickets left, so it must come after everything still to be visited. Dead-end branches are therefore emitted first and end up at the end of the reversed route:
def find_itinerary(tickets: list[list[str]]) -> list[str]:
graph: dict[str, list[str]] = defaultdict(list)
for src, dst in sorted(tickets, reverse=True):
graph[src].append(dst) # reverse-sorted, so pop() gives the smallest
route, stack = [], ["JFK"]
while stack:
if graph[stack[-1]]:
stack.append(graph[stack[-1]].pop()) # use the smallest unused ticket
else:
route.append(stack.pop()) # stuck: this airport goes last among what's left
return route[::-1]
Each ticket is pushed and popped once: \(O(E \log E)\) for the sort, \(O(E)\) for the walk.
Common Mistakes¶
-
Marking visited on dequeue in BFS. Vertices get enqueued repeatedly; mark them when first discovered.
-
Using a plain visited set for directed cycle detection. An edge to a finished vertex is not a cycle. Track "on the current DFS path" separately (gray vs. black).
-
Using BFS on weighted graphs. BFS minimizes the number of edges, not their total weight.
-
Dijkstra with negative edges. It silently returns wrong answers. Use Bellman–Ford, or topological order if the graph is a DAG.
-
Forgetting disconnected graphs. A single traversal only covers one component. Loop over all vertices when you need the whole graph (components, bipartiteness, cycle detection, topological sort).
-
Building huge implicit graphs explicitly. Generate neighbors on demand. For grids, check bounds instead of storing edges.
-
Deep recursion. Recursive DFS on large graphs hits Python's recursion limit. Use an explicit stack when depth can reach the thousands.
-
Wrong loop order in Floyd–Warshall. The intermediate vertex \(k\) must be the outer loop.
Practice Problems¶
| Problem | Technique |
|---|---|
| Number of Islands (LC 200) | Flood fill / components |
| Clone Graph (LC 133) | DFS/BFS with old → new map |
| Max Area of Island (LC 695) | Flood fill with size |
| Pacific Atlantic Water Flow (LC 417) | Reverse flood fill from both oceans |
| Surrounded Regions (LC 130) | Flood fill from the border |
| Rotting Oranges (LC 994) | Multi-source BFS |
| Shortest Path in Binary Matrix (LC 1091) | BFS on a grid |
| Is Graph Bipartite? (LC 785) | BFS two-coloring |
| Open the Lock (LC 752) | BFS on an implicit state graph |
| Word Ladder (LC 127) | BFS, bidirectional BFS |
| Course Schedule I & II (LC 207, 210) | Topological sort |
| Find Eventual Safe States (LC 802) | Three-color DFS cycle detection |
| Alien Dictionary (LC 269) | Build the graph, then topological sort |
| Redundant Connection (LC 684) | Union-find cycle detection |
| Critical Connections in a Network (LC 1192) | Bridges via low-link |
| Min Cost to Connect All Points (LC 1584) | Prim's MST |
| Network Delay Time (LC 743) | Dijkstra |
| Path With Minimum Effort (LC 1631) | Dijkstra with max instead of sum |
| Cheapest Flights Within K Stops (LC 787) | Bellman–Ford with \(k + 1\) rounds |
| Find the City With the Smallest Number of Neighbors (LC 1334) | Floyd–Warshall |
| Bus Routes (LC 815) | BFS over routes |
| Reconstruct Itinerary (LC 332) | Eulerian path |