Graphs and Graph Algorithms Questions
Graph representations (adjacency list and adjacency matrix) and the traversal algorithms applied to general, non-tree structures: BFS, DFS, topological sort (Kahn's algorithm and DFS-based), shortest paths (Dijkstra, Bellman-Ford, A*), minimum spanning trees, cycle detection, connected components, and union-find. Covers modeling a problem as a graph even when the underlying data is not obviously graph-shaped, such as state-space search, an implicit graph over strings or grid cells (for example Word Ladder), or a task-dependency graph, and implementing these traversals with a hash map or hash set as the storage vehicle (adjacency map, visited set, memoization table), not the subject being tested. The graded skill is traversal, ordering, connectivity, or shortest-path reasoning over nodes and edges. This topic does not own: traversal, reconstruction, or serialization of a single-rooted binary tree (preorder, inorder, postorder, or level-order implementation, rebuilding a tree from traversal arrays, lowest common ancestor, binary search tree validation), which belongs to binary trees and binary search trees even though a tree is technically a graph; hash table internals such as hash function design, collision resolution, and load factor and resizing, which belong to hashing and hash tables; and deriving or comparing algorithmic complexity across graph algorithms without implementing them, such as comparing the time complexity of BFS, DFS, Dijkstra, and A*, which belongs to time and space complexity analysis. One of the highest-signal areas in senior coding interviews.
Explain the Bellman-Ford algorithm and how it detects negative-weight cycles. Discuss the algorithm's complexity and scenarios where Bellman-Ford is preferred over Dijkstra in ML systems or feature computations.
Sample Answer
Direct answer
Bellman-Ford detects a negative-weight cycle by relaxing every edge V−1 times and then running one more pass: if any edge still improves a distance after V−1 passes have already had enough rounds to propagate every legitimate shortest simple path, that improvement can only be coming from a cycle that keeps paying off each time it is traversed, which is exactly what a negative cycle is. The algorithm costs O(V⋅E), strictly worse than Dijkstra's O((V+E)logV), but it is the tool of choice whenever negative edge weights (not just non-negative ones) must be supported, since Dijkstra's greedy finalize-and-never-revisit strategy is provably wrong once weights can be negative.
Structured elaboration
Why V−1 passes suffice, and why a V-th exposes a cycle. Any shortest path that does not repeat a vertex (a simple path) has at most V−1 edges, since a path with V or more edges on a graph with only V vertices must revisit one. Each full relaxation pass propagates a shortest-path value at least one edge further along its optimal path (in the worst case), so V−1 passes are enough to fully propagate every simple shortest path. If a negative cycle is reachable from the source, however, there is no shortest SIMPLE path at all: the "shortest path" can always be made cheaper by looping the cycle one more time, so the distance is not well-defined (it is −∞ in the limit), and relaxation never stops improving, which is exactly what the V-th pass is checking for.
Complexity. O(V⋅E): V−1 (or fewer, with early termination when a pass makes no change) full passes over all E edges, plus a final detection pass.
When Bellman-Ford is preferred over Dijkstra. The deciding factor is whether negative weights are possible at all, not performance: Dijkstra is asymptotically faster whenever it is legal to use, so Bellman-Ford's only justification is a graph where some edge genuinely can be negative. Two scenarios where this shows up specifically in machine learning (ML) systems or feature computations: a feature store's derived-feature dependency graph where an edge's weight is the marginal COST of computing one feature from an upstream one, and a caching or precomputation transformation legitimately REDUCES that downstream cost (a negative-weight edge), so finding the cheapest chain of transformations to materialize a target feature needs Bellman-Ford precisely because some of those cost-reducing edges are negative; and reward-shaping in a reinforcement learning (RL) pipeline, where a state-transition graph's edge weight is a change in loss or cost and some transitions are explicitly loss-reducing by design (a shaped reward bonus), so a "cheapest path" query over that graph again requires an algorithm that tolerates negative weights. Beyond ML specifically, the same need for negative-weight tolerance appears in a currency arbitrage graph modeling exchange-rate log-ratios, or a dependency graph with penalty and bonus edges that can legitimately be negative. Once negative weights are possible, there is no faster correct alternative for general graphs, only Bellman-Ford (or, if the graph happens to also be acyclic, a topological-order relaxation pass in O(V+E), which sidesteps the need for repeated passes entirely because acyclicity alone, independent of weight sign, guarantees a safe processing order).
The ∣E∣≫∣V∣ scale consideration. Bellman-Ford's cost is O(V⋅E), which grows linearly with E for a fixed V, so on a graph where edges vastly outnumber vertices (a dense graph, or a multigraph with many parallel edges between the same pairs), the constant-factor gap between Bellman-Ford's O(VE) and Dijkstra's O((V+E)logV) widens further, since V⋅E grows much faster than (V+E)logV as E increases with V fixed. This sharpens the earlier point: if there is any way to confirm the graph has no negative weights (even at ingestion time, by validating every edge as it is added), switching to Dijkstra on a dense graph is not a marginal win, it can be a large one.
Worked example
Take the 4-node cycle 1→2 (weight -3), 2→3 (weight 1), 3→1 (weight 1), reachable from source 0 via 0→1 (weight 1). The cycle's total weight is −3+1+1=−1, negative.
After 3 relaxation passes (V−1=3 for this 4-node graph), the distances to nodes on the cycle keep decreasing each additional pass rather than stabilizing (each additional loop around the cycle subtracts another 1 from the achievable distance), so the 4th pass still finds an edge to relax, correctly signaling a negative cycle.
Verification. Rather than leave that as an unsupported claim, here is the actual implementation and its real output on this exact graph:
def bellman_ford(graph, source):
dist = {u: float("inf") for u in graph}
pred = {u: None for u in graph}
dist[source] = 0
V = len(graph)
for _ in range(V - 1):
changed = False
for u in graph:
if dist[u] == float("inf"):
continue
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
pred[v] = u
changed = True
if not changed:
break
culprit = None
for u in graph:
if dist[u] == float("inf"):
continue
for v, w in graph[u]:
if dist[u] + w < dist[v]:
culprit = v
pred[v] = u
break
if culprit is not None:
break
if culprit is None:
return {"has_negative_cycle": False, "distances": dist, "predecessors": pred}
node = culprit
for _ in range(V):
node = pred[node]
cycle = [node]
cur = pred[node]
while cur != node:
cycle.append(cur)
cur = pred[cur]
cycle.append(node)
cycle.reverse()
return {"has_negative_cycle": True, "cycle": cycle}
g = {0: [(1, 1)], 1: [(2, -3)], 2: [(3, 1)], 3: [(1, 1)]}
r = bellman_ford(g, 0)
print("result:", r)
def cycle_weight(graph, cycle):
total = 0
for i in range(len(cycle) - 1):
u, v = cycle[i], cycle[i + 1]
w = next(w for vv, w in graph[u] if vv == v)
total += w
return total
print("cycle weight:", cycle_weight(g, r["cycle"]))
Output (actually executed with python3):
result: {'has_negative_cycle': True, 'cycle': [1, 2, 3, 1]}
cycle weight: -1
Confirms the algorithm flags has_negative_cycle: True and reconstructs the cycle [1, 2, 3, 1], whose own edge weights independently re-sum to −1.
Trade-offs and pitfalls
- Common mistake: treating "the graph has a negative edge" and "the graph has a negative cycle" as the same warning sign. A single negative edge with no cycle is completely fine for Bellman-Ford and produces a well-defined, correct shortest-path answer; only a negative CYCLE (a way to keep re-visiting and re-paying a net-negative loop) breaks the notion of "shortest path" itself.
- Common mistake: running only V−1 passes and stopping, without the extra detection pass, on data that has not been validated to be cycle-free. Silently returning distances that are secretly still decreasing (had one more pass been run) reports numbers that are not the true shortest distances, without any signal that something is wrong.
- The early-termination optimization (stop as soon as one full pass makes no change) is safe and commonly implemented, but does not remove the need for the dedicated detection pass on the FIRST run through the loop that would otherwise have kept changing; it only shortens how many of the V−1 passes actually execute when the graph converges early.
- If the domain genuinely never has negative weights, defaulting to Bellman-Ford anyway "to be safe" trades away real performance for a guarantee that costs nothing to instead enforce at the input-validation layer (reject or flag any negative edge on ingestion, then use Dijkstra with confidence).
Explain cycle detection in directed graphs using DFS with node color states (white/gray/black). Describe how back edges are identified and why this method reliably detects cycles even in complex pipeline dependency graphs. Also explain how you would return the actual nodes involved in the detected cycle.
Sample Answer
Direct answer
Depth-first search (DFS) with three color states, white (undiscovered), gray (discovered, still being explored on the current path), black (fully finished), detects a directed cycle by recognizing a BACK EDGE: an edge from the node currently being explored into a node that is still gray, meaning still an ancestor on the active exploration path. A back edge means that ancestor depends, directly or transitively, on the very node now trying to reach it, a genuine circular dependency. This is reliable regardless of graph size or shape, including complex, many-branched pipeline dependency graphs, because the gray marker tracks exactly "currently on my path back to the root," which is precisely the condition a cycle requires.
Structured elaboration
The traversal. Start DFS from every white node (covering disconnected components). On visiting a node, mark it gray, then examine each outgoing edge: if the neighbor is white, recurse into it; if the neighbor is gray, a back edge has been found, a cycle; if the neighbor is black, that edge leads to an already-fully-explored subtree reachable some other way, not a cycle. After all of a node's neighbors are processed, mark it black.
Why gray specifically, and not just "visited." A plain boolean visited flag cannot distinguish "still in progress on my current path" from "finished via some completely unrelated path." Consider a diamond shape, 0→1, 0→2, 1→3, 2→3: node 3 is reached twice, once via 1 and once via 2, and neither visit is a cycle, since 3 is never an ANCESTOR of either 1 or 2. A boolean visited check alone cannot tell this apart from a genuine cycle case; the three-state color scheme can, because by the time the second path reaches node 3, node 3 has already gone gray to black (fully finished) rather than still being gray, so the algorithm correctly recognizes it as a shared descendant, not a back edge.
Why this is reliable for complex pipeline dependency graphs specifically. A pipeline dependency graph typically has many jobs sharing common upstream stages (many downstream jobs all reading from one shared ingestion stage, for example), which is exactly the diamond shape above at scale. The gray/black distinction is what makes the algorithm correctly ignore all that legitimate sharing while still catching a genuine cycle wherever one exists, independent of how tangled or branching the rest of the graph is, since the check only ever depends on the CURRENT recursion path's gray set, never on the graph's overall shape.
Returning the actual nodes in the detected cycle. Track a parent pointer for every node, set the moment it is first discovered from its immediate predecessor. The instant a back edge u→v is found (v is gray), walk parent backward starting from u until reaching v itself; that walk, plus v appended again at the end to close the loop, is exactly the cycle, reported as a concrete list of node names rather than a bare "yes, a cycle exists" boolean.
Worked example
def find_cycle(graph):
color = {v: "white" for v in graph}
parent = {v: None for v in graph}
def dfs(u):
color[u] = "gray"
for v in graph[u]:
if color[v] == "white":
parent[v] = u
found = dfs(v)
if found is not None:
return found
elif color[v] == "gray":
cycle = [v]
cur = u
while cur != v:
cycle.append(cur)
cur = parent[cur]
cycle.append(v)
cycle.reverse()
return cycle
color[u] = "black"
return None
for node in graph:
if color[node] == "white":
result = dfs(node)
if result is not None:
return result
return None
if __name__ == "__main__":
dag = {0: [1, 2], 1: [3], 2: [3], 3: []}
print("DAG cycle:", find_cycle(dag))
pipeline = {"ingest": ["clean"], "clean": ["enrich"], "enrich": ["load"], "load": ["clean"]}
cyc = find_cycle(pipeline)
print("Pipeline cycle:", cyc)
def is_real_cycle(graph, cycle):
if not cycle or len(cycle) < 2:
return False
return all(cycle[i+1] in graph[cycle[i]] for i in range(len(cycle)-1))
print("Reported pipeline cycle uses only real edges:", is_real_cycle(pipeline, cyc))
diamond = {0: [1, 2], 1: [3], 2: [3], 3: []}
print("Diamond (shared descendant, no cycle):", find_cycle(diamond))
Output (actually executed with python3):
DAG cycle: None
Pipeline cycle: ['clean', 'enrich', 'load', 'clean']
Reported pipeline cycle uses only real edges: True
Diamond (shared descendant, no cycle): None
The pipeline example (ingest feeds clean, clean feeds enrich, enrich feeds load, and load mistakenly feeds back into clean) correctly reports the exact cycle ['clean', 'enrich', 'load', 'clean'], verified by an independent edge-by-edge check that every consecutive pair in the reported cycle is a real edge in the original graph, not a fabricated list. The diamond case, structurally similar to the shared-ingestion-stage shape common in real pipelines, correctly reports no cycle at all.
Trade-offs and pitfalls
- Common mistake: returning just the back-edge's two endpoints (u and v) as "the cycle," rather than the full path between them. This under-reports the problem: an operator debugging a circular dependency needs to see every job in the loop, not just the two that happened to trigger detection, especially in a pipeline graph where the cycle might span many stages.
- Common mistake: using a plain visited set instead of the three-state scheme and expecting the diamond shape (shared descendant, no actual cycle) to be handled correctly; as shown above, this specific shape is exactly what a boolean check gets wrong, making it a strong test case to include in any cycle-detector's own test suite.
- Multiple independent cycles. This algorithm returns the FIRST cycle it happens to find during its traversal order, not necessarily the "worst" one or all of them; a pipeline validation tool that wants to report every cycle in one pass needs to continue searching after finding one (removing or logging it, then resuming), rather than stopping at the first.
- Self-loops are the degenerate one-node case of exactly the same mechanism: a node pointing to itself is immediately gray when its own edge is examined, correctly detected as a cycle of length one without any special-casing needed.
Implement breadth-first search (BFS) in Python to find the shortest path between two nodes in an unweighted graph. Function signature: def shortest_path(adj: Dict[int, List[int]], start: int, target: int) -> List[int]. Return the list of nodes forming the shortest path from start to target inclusive, or an empty list if no path exists. The adjacency input is an adjacency list mapping node ids to neighbor lists. Aim for O(V+E) time and O(V) memory.
Sample Answer
Direct answer
Breadth-first search (BFS) finds the shortest path between two nodes in an unweighted graph because it explores the graph in strict distance order: it fully visits every node at distance 1 from the start before touching any node at distance 2, and so on. The first time any node is reached, that is necessarily via the fewest possible edges, so recording each node's discoverer (its parent) as it is first visited, then walking those parent pointers backward from the target, reconstructs a shortest path in O(V+E) time and O(V) space.
Structured elaboration
Two pieces of state drive the algorithm: a visited set (or equivalently, a parent dict whose keys double as the visited set) to guarantee each node is processed once, and the parent map itself to allow path reconstruction. A first-in-first-out (FIFO) queue guarantees the "distance order" property: the queue always contains nodes from at most two contiguous distance layers at a time, and everything from the current layer is dequeued before anything from the next layer is examined.
Worked example
from collections import deque
from typing import Dict, List
def shortest_path(adj: Dict[int, List[int]], start: int, target: int) -> List[int]:
# BFS shortest path in an unweighted graph. Returns the node list from
# start to target inclusive, or [] if target is unreachable.
if start == target:
return [start]
if start not in adj:
return []
visited = {start}
parent = {start: None}
q = deque([start])
while q:
u = q.popleft()
for v in adj.get(u, []):
if v not in visited:
visited.add(v)
parent[v] = u
if v == target:
q.clear()
break
q.append(v)
if target not in parent:
return []
path = []
node = target
while node is not None:
path.append(node)
node = parent[node]
path.reverse()
return path
if __name__ == "__main__":
adj = {
0: [1, 2],
1: [0, 3],
2: [0, 3],
3: [1, 2, 4],
4: [3],
5: [6], # disconnected component
6: [5],
}
print("0 -> 4:", shortest_path(adj, 0, 4))
print("0 -> 5 (unreachable):", shortest_path(adj, 0, 5))
print("0 -> 0 (same node):", shortest_path(adj, 0, 0))
print("7 -> 1 (start not in graph):", shortest_path(adj, 7, 1))
def bfs_distance(adj, start, target):
dist = {start: 0}
q = deque([start])
while q:
u = q.popleft()
for v in adj.get(u, []):
if v not in dist:
dist[v] = dist[u] + 1
q.append(v)
return dist.get(target)
p = shortest_path(adj, 0, 4)
ref_dist = bfs_distance(adj, 0, 4)
print("Path edges match independently computed BFS distance:", len(p) - 1 == ref_dist, f"(path edges={len(p)-1}, ref_dist={ref_dist})")
Output (actually executed with python3):
0 -> 4: [0, 1, 3, 4]
0 -> 5 (unreachable): []
0 -> 0 (same node): [0]
7 -> 1 (start not in graph): []
Path edges match independently computed BFS distance: True (path edges=3, ref_dist=3)
The bfs_distance helper is a separate, minimal BFS that only ever tracks distances, never a path; it exists purely to cross-check the path-returning function's length against an independently computed ground truth, and the two agree.
Complexity
Time O(V+E): each node is enqueued and dequeued at most once, and each edge is examined at most once from each of its endpoints (twice total for an undirected graph, once for a directed graph). Space O(V) for visited and parent, plus the queue, which never holds more nodes than exist at the two frontier layers being processed.
Edge cases
start == target: returns[start]immediately, a path of length zero (no edges), handled as a special case up front rather than relying on the traversal to "discover" the start node as its own neighbor.startnot present inadj: returns[]rather than raising, treating an unknown start node the same as "no path exists."- Disconnected
target: the BFS frontier exhausts without ever reachingtarget;target not in parentcatches this and returns[]. - Multiple shortest paths of equal length: BFS returns one of them, determined by adjacency-list iteration order, not necessarily a "canonical" one; if a caller needs a specific tie-break (lexicographically smallest node sequence, for example), that requires sorting each node's neighbor list before traversal.
- Early exit on discovering the target: the
q.clear(); breakpair stops further expansion the instant the target is first discovered, since BFS guarantees that first discovery is already a shortest path; continuing to explore further nodes would waste work without changing the answer.
Trade-offs and pitfalls
- Common mistake: marking a node visited when it is dequeued rather than when it is first enqueued (discovered). If two different frontier nodes both point to the same not-yet-visited neighbor before either is dequeued, dequeue-time marking lets that neighbor be enqueued twice, wasting work and, worse, letting the second enqueue silently overwrite
parentwith a different, equally-short but different, predecessor, which is harmless for path length but can produce a different (still valid) path than intended if the caller expects determinism. - Common mistake: using depth-first search (DFS) instead of BFS for this task. DFS also visits every reachable node, but it does not explore in non-decreasing distance order, so the first path DFS finds to
targetis not guaranteed to be shortest; DFS proves reachability, not shortest distance, in an unweighted graph. - A commonly asked variant of this same archetype returns a distance MAP (
{node: distance}for every reachable node) instead of a single path. That variant is a strict generalization: thebfs_distancehelper above is essentially that function with the path-reconstruction machinery stripped out, and a caller who needs distances to many targets from one source should prefer running that once rather than callingshortest_pathrepeatedly, which would redundantly re-traverse shared prefixes of the graph on every call. - For a WEIGHTED graph, none of this generalizes directly. BFS's correctness depends entirely on every edge costing exactly one step; the moment edges have different costs, this becomes Dijkstra's algorithm territory (or 0-1 BFS specifically for
{0,1}-weighted edges), not a variant of plain BFS.
Implement BFS on an implicit graph (state space) where each state's neighbors are generated by a function produce_neighbors(state). Write find_shortest_sequence(start, goal, produce_neighbors) in Python to return the shortest move sequence. Discuss pruning strategies, heuristics, and how to guarantee shortest path (when allowed to prune). Suggest bidirectional search when applicable.
Sample Answer
Direct answer
An implicit graph never materializes its full node or edge set up front: neighbors are computed on demand by calling produce_neighbors(state), and breadth-first search (BFS) still applies unmodified, since BFS only ever needs "give me the neighbors of this node right now," never the whole graph at once. This is exactly what a state-space search (a puzzle, a game position, an abstract configuration space) needs, since materializing every reachable state ahead of time is often impossible or wasteful.
Structured elaboration
Why BFS still guarantees shortest path here. BFS's core guarantee, the first time a state is discovered it is at its true minimum distance, depends only on exploring states in non-decreasing distance order, never on knowing the graph's shape in advance. Calling produce_neighbors lazily, one node at a time, preserves this exactly: each call happens precisely when that node is dequeued, in the same layer-by-layer order BFS always uses.
Pruning strategies. A visited set is the baseline prune (never re-expand a state already discovered), but implicit graphs often support domain-specific pruning too: reject a neighbor immediately if it violates an invariant (an illegal board position, a state outside a known-safe region) before it is ever added to the queue, saving both the memory to store it and the future work of expanding it. Pruning by domain invariant must never prune a state that could still be on SOME shortest path, or the "shortest" guarantee breaks; a prune based purely on redundancy (already visited) is always safe, a prune based on heuristic judgment is not automatically safe unless proven admissible.
Heuristics. If a heuristic estimate of remaining distance to the goal is available, switching from plain BFS to A* (using the heuristic to prioritize which state to expand next via a priority queue instead of a FIFO queue) can dramatically reduce the number of states visited, at the cost of losing BFS's simplicity and requiring the heuristic to be admissible (never overestimate the true remaining distance) to keep the shortest-path guarantee.
Bidirectional search. When both start and goal are known in advance (not always true in state-space search, but common), growing frontiers from both ends and stopping when they meet bounds the search to roughly the square root of the single-direction node count for a typical branching factor, the same principle as bidirectional BFS on any explicit graph.
Worked example
from collections import deque
from typing import Callable, Iterable, List, Optional, TypeVar
State = TypeVar("State")
def find_shortest_sequence(start: State, goal: State,
produce_neighbors: Callable[[State], Iterable[State]]) -> Optional[List[State]]:
if start == goal:
return [start]
parent = {start: None}
q = deque([start])
while q:
s = q.popleft()
for nxt in produce_neighbors(s):
if nxt in parent:
continue
parent[nxt] = s
if nxt == goal:
path = [nxt]
cur = nxt
while parent[cur] is not None:
cur = parent[cur]
path.append(cur)
return list(reversed(path))
q.append(nxt)
return None
if __name__ == "__main__":
# Abstract 12-state space: from state s, neighbors are s+1, s-1, s+5 (mod 12).
# Deliberately not a literal grid or puzzle, to make the point that BFS
# does not care what a "state" actually represents.
N = 12
def produce_neighbors(state):
return [(state + 1) % N, (state - 1) % N, (state + 5) % N]
path = find_shortest_sequence(0, 7, produce_neighbors)
print("Shortest sequence 0 -> 7:", path)
print("Steps:", len(path) - 1 if path else None)
def is_valid(path, produce_neighbors):
return all(path[i+1] in set(produce_neighbors(path[i])) for i in range(len(path)-1))
print("Path uses only real transitions:", is_valid(path, produce_neighbors))
def full_bfs_dist(start, produce_neighbors):
dist = {start: 0}
q = deque([start])
while q:
u = q.popleft()
for v in produce_neighbors(u):
if v not in dist:
dist[v] = dist[u] + 1
q.append(v)
return dist
ref = full_bfs_dist(0, produce_neighbors)
print("Matches independent full-BFS distance table:", ref[7] == len(path) - 1)
print("No path from a state that only transitions to itself:", find_shortest_sequence(100, 200, lambda s: [s]))
Output (actually executed with python3):
Shortest sequence 0 -> 7: [0, 1, 2, 7]
Steps: 3
Path uses only real transitions: True
Matches independent full-BFS distance table: True
No path from a state that only transitions to itself: None
The independent full_bfs_dist helper computes distances to every reachable state from scratch, without reusing the path-returning function's logic, and its distance to state 7 (3) matches len(path) - 1 exactly, confirming the lazily-called produce_neighbors version is genuinely finding a true shortest sequence, not just any sequence.
Complexity
Time O(N+E) where N is the number of reachable states and E is the number of transitions actually explored (both unknown in advance for a true implicit graph, unlike an explicit one where V and E are given). Space O(N) for parent and the queue. Each call to produce_neighbors is charged whatever it costs to compute (in the example above, O(1); in a real puzzle, it might be proportional to board size).
Edge cases
start == goal: returns[start]immediately, a zero-move sequence, without ever callingproduce_neighbors.- No path exists (as demonstrated by the self-loop-only state 100 in the worked example): the queue drains completely,
parentnever gains an entry forgoal, and the function returnsNone. produce_neighborsyielding a state already on the current path (a state with a transition back to itself, or a cycle in the state graph): handled the same as any other implicit-graph cycle, since theparentdict doubles as the visited set, a state already discovered is never re-enqueued.produce_neighborsraising an exception mid-search (a real risk if computing a state's neighbors can fail, for example an invalid board configuration): not handled by the implementation above, and worth flagging explicitly as something a production version would need to decide on: abort the whole search, or treat that state as having no valid neighbors and continue.
Trade-offs and pitfalls
- Common mistake: calling
produce_neighborsmore than once for the same state (for example, once to check if any neighbor is the goal, and again to actually enqueue them). Since neighbor generation can be expensive in a real state space, the implementation above calls it exactly once per dequeued state and processes each yielded neighbor as it arrives. - Common mistake: pruning by a heuristic that is not admissible (can overestimate true remaining distance), which silently breaks BFS's shortest-path guarantee; a state that gets pruned because it "looks unpromising" might still sit on the actual shortest path.
- Infinite or unbounded state spaces. Unlike a finite explicit graph, an implicit state space can be infinite (an unbounded counter, an open-ended configuration). Plain BFS on such a space either runs forever if
goalis unreachable, or needs an explicit depth cap or iterative-deepening strategy layered on top to guarantee termination even on a "no path exists" input. - When to reach for A instead.* If a genuinely admissible heuristic exists (an under-estimate of remaining distance that is cheap to compute), A* dominates plain BFS by visiting fewer states while preserving the same shortest-path guarantee; if no such heuristic is available or trustworthy, plain BFS remains the safe default.
Write Python code to find all articulation points (cut vertices) and bridges (cut edges) in an undirected network graph represented as adjacency list Dict[int, List[int]]. Use a DFS lowlink algorithm and explain how articulation points and bridges indicate single points of failure in a network topology.
Sample Answer
Direct answer
An articulation point (cut vertex) is a node whose removal increases the number of connected components in the graph; a bridge (cut edge) is an edge whose removal does the same. Both are found in a single depth-first search (DFS) pass using the "low-link" technique: track each node's discovery time and its low-link value (the earliest discovery time reachable from that node's DFS subtree via at most one back edge), and a node/edge is flagged as critical based on how a child's low-link compares to the current node's own discovery time. In a network topology, these are exactly the single points of failure: an articulation point is a device whose failure partitions the network, and a bridge is a link whose failure does the same, both directly actionable signals for where redundancy is most needed.
Structured elaboration
Discovery time and low-link, defined precisely. disc[u] is the order in which DFS first visits u (a simple counter incremented on each new visit). low[u] starts equal to disc[u] and is then lowered to the minimum discovery time reachable from u's subtree by following tree edges down and at most one back edge up past u itself; concretely, low[u] = min(low[u], disc[v]) for every back edge to an already-visited (non-parent) node v, and low[u] = min(low[u], low[v]) after fully exploring each tree-edge child v.
Articulation point condition. For a non-root node u with DFS-tree child v: u is an articulation point if low[v] >= disc[u], meaning v's entire subtree cannot reach back to any ancestor of u (not even u itself, in the strict inequality case) without going back through u, so removing u would strand that subtree. The ROOT of a DFS tree is a special case, handled separately: it is an articulation point exactly when it has more than one child in the DFS tree, since each such child's subtree is only connected to the rest of the tree through the root.
Bridge condition. For a tree edge (u, v) where v is u's child: (u,v) is a bridge if low[v] > disc[u] (strict inequality, unlike the articulation-point condition), meaning v's subtree has NO way back to u or any ancestor of u at all, not even to u itself via some other path, so this specific edge is the only connection.
Why single points of failure matter operationally. In a network topology, both articulation points and bridges directly identify where a SINGLE failure (one device down, or one link down) causes a partition, not merely a slowdown; this is qualitatively different from and more urgent than general redundancy planning, since it names the EXACT minimal set of failures that would split the network, which is the natural prioritization list for where to add redundant links or failover devices first.
Worked example
from typing import Dict, List, Set, Tuple
def find_articulation_points_and_bridges(graph: Dict[int, List[int]]):
disc, low = {}, {}
visited = set()
timer = [0]
articulation_points: Set[int] = set()
bridges: List[Tuple[int, int]] = []
def dfs(u, parent):
visited.add(u)
disc[u] = low[u] = timer[0]
timer[0] += 1
children = 0
for v in graph.get(u, []):
if v == parent:
continue
if v in visited:
low[u] = min(low[u], disc[v])
else:
children += 1
dfs(v, u)
low[u] = min(low[u], low[v])
if parent is not None and low[v] >= disc[u]:
articulation_points.add(u)
if low[v] > disc[u]:
bridges.append((min(u, v), max(u, v)))
return children
for start in graph:
if start not in visited:
root_children = dfs(start, None)
if root_children > 1:
articulation_points.add(start)
return sorted(articulation_points), sorted(bridges)
if __name__ == "__main__":
# Network: two triangles (0-1-2) and (3-4-5) joined by a single bridge edge 2-3,
# plus a pendant node 6 hanging off node 5.
graph = {
0: [1, 2], 1: [0, 2], 2: [0, 1, 3],
3: [2, 4, 5], 4: [3, 5], 5: [3, 4, 6], 6: [5],
}
ap, bridges = find_articulation_points_and_bridges(graph)
print("articulation points:", ap)
print("bridges:", bridges)
Output:
articulation points: [2, 3, 5]
bridges: [(2, 3), (5, 6)]
By inspection: removing node 2 disconnects {0,1} from the rest, so it is an articulation point; removing node 3 disconnects {0,1,2} from {4,5,6}; removing node 5 disconnects {6}; the edges (2,3) and (5,6) are each the sole connection to a piece of the graph and so are bridges. All four match the executed output exactly.
Trade-offs and pitfalls
- The articulation-point and bridge CONDITIONS differ by a single inequality (
>=versus>), and mixing them up is the single most common implementation bug: using>for the articulation-point check would wrongly excludeuwhenlow[v] == disc[u](a case wherev's subtree CAN reach back exactly tou, but no further, meaning removingustill strands the subtree, sougenuinely is an articulation point despite the border case). - The root of the DFS tree needs separate handling entirely, since the general non-root formula (
low[v] >= disc[u]) does not apply to a node with no parent to be "cut off from"; a root is only critical if it has more than one DFS-tree child, since those children's subtrees are then only interconnected THROUGH the root. - A node can be an articulation point without any single INCIDENT edge being a bridge, and vice versa is also possible; the two concepts overlap but are not equivalent, and a network engineer reading these results needs both lists, not just one, to fully understand the topology's fragility.
- This algorithm assumes an undirected, simple graph (the
if v == parent: continuecheck specifically handles the back-and-forth of a single tree edge, but does not correctly handle true parallel/multi-edges between the same pair of nodes); a network topology with genuine redundant parallel links between two devices needs the algorithm adjusted to track edge identity, not just endpoint identity, or a duplicate parallel edge would be incorrectly treated as a back edge to the immediate parent and silently ignored.
Unlock Full Question Bank
Get access to all Graphs and Graph Algorithms interview questions and detailed answers.
Sign in to ContinueJoin thousands of developers preparing for their dream job.