Concept · Graphs
This lesson builds on depth-first search. If the idea of a DFS and its visited set is new, read Depth-First Search first.
A network of servers is joined by links. Some links are a single point of failure: cut one and the network falls into two pieces that cannot talk to each other. Such a link is a bridge. Other links have a backup, because they sit on a loop.
The direct way to find the bridges is to remove each link in turn and check whether the network is still connected. One check is a DFS, which costs O(V + E). Doing it for all E links costs O(E × (V + E)). With 10⁵ links that is around 2 × 10¹⁰ steps.
Almost all of that work is wasted. Each check walks nearly the same graph again. Can a single DFS tell us which links are bridges?
A link is a bridge exactly when it lies on no loop. So we do not need to remove anything. We only need to know, for each link, whether there is another route between its two ends.
Run one DFS and give every node a discovery time disc: the step at which the DFS first reached it. The links the DFS walks form a tree. In an undirected graph every other link joins a node to one of its ancestors or descendants, so each one is a back edge that climbs up the tree.
Now give every node a second number, low: the earliest discovery time its subtree can reach, using the tree below it and at most one back edge. A back edge that jumps above a tree link is exactly a backup route for it.
node down to child is a bridge exactly when low[child] > disc[node]: nothing in the child's subtree climbs back to node or above.The network has seven nodes. Two loops, 1–2–3 and 4–5–6, are joined to each other and to node 0 by single links. The DFS starts at node 0. Each node shows disc/low.
Back edge. At node 3, the neighbour 1 was reached earlier and is not where we came from. That is a back edge, so low[3] drops to disc[1] = 1. The loop 1–2–3 now has a backup, and the number records it.
The pitfall. At node 4 the neighbour 3 is the node we came from. If we counted it, low[4] would become 3 and the link 3–4 would look like it has a backup, when the only "backup" is the link itself. The code skips the parent.
Reporting upward. Node 6 climbs back to node 4, so low[6] = 4. The value travels up: low[5] = 4, low[4] = 4. Back at node 3, the test is low[4] > disc[3], which is 4 > 3. Nothing below 4 climbs above 4, so 3–4 is a bridge.
The loop passes the test. Coming back from node 2 to node 1, the test is low[2] > disc[1], which is 1 > 1 and false. Node 2's side reaches node 1 again, so the link 1–2 has a backup. At node 0 the test is 1 > 0, which is true, so 0–1 is a bridge.
disc[node] = low[node] = timer and move the timer on.nxt:low[node] = min(low[node], low[nxt]), and if low[nxt] > disc[node] the link is a bridgelow[node] = min(low[node], disc[nxt])Take a tree link from node to child. Every route from the child's subtree to the rest of the graph either uses this link or uses a back edge, because tree links only go down and every other link goes up to an ancestor.
If low[child] > disc[node], no back edge from the subtree lands on node or above. This link is the only way out, so it is a bridge. If low[child] ≤ disc[node], some back edge lands on node or above. Together with the tree path, that is a loop through the link, so it is not a bridge.
The comparison is strict (>) because a back edge that lands exactly on node still makes a loop through node.
Pick an input, then press Play or use the arrow keys. The highlighted line is the one running, the number beside each line counts how often it ran, and the dashed box shows the comparison and what it decides. The graph shows disc/low beside each node, and a red link is a bridge.
disc and low hold V numbers each. The recursion goes as deep as the longest DFS path, up to V. The output holds at most V − 1 bridges.>= instead of >. That test finds articulation points, the nodes whose removal splits the graph. For those, the root is special: it is an articulation point only if it has two or more DFS children.Reach for it when:
Problems that use it:
These are the questions that usually come next. Open one to see an answer you could say out loud.
What they are checkingWhether you understood why the test is >, or only memorised it. If you know the reason, changing the question changes one character.
A strong answerA server is critical (an articulation point) when removing it splits the graph. A back edge that lands exactly on node no longer helps, because node is gone, so the test becomes low[child] >= disc[node]. The root needs a separate rule: it is critical only if it has two or more DFS children.
What they are checkingWhether you notice that a correct algorithm can still fail in production, and whether you know the fix.
A strong answerThe recursion would be 10⁶ calls deep. Python's default limit is around 1000, and other languages can overflow the stack too. Replace the recursion with an explicit stack that holds, for each frame, the node, its parent and the index of the next neighbour. The logic and the O(V + E) cost stay the same.
What they are checkingWhether you ask how often the graph changes before designing anything.
A strong answerFor an occasional change, rerunning is fine: O(V + E) is cheap. Say that first, and ask how many changes per second and how large the graph is. If changes are constant, this becomes a different and harder problem, and the answer depends on those numbers.