Pebellslearn by building
0%
RoadmapsMatrixCoursesSandboxSign in
Graph Structure & Decomposition  ›  Lesson

Bridges & Articulation Points

Bridges & Articulation Points 32 minRoads and junctions whose loss splits the city
You're building a piece ofMeridian — the network model
This piece — critical_roads(): Lists the roads whose closure would split the city in two.
Scenario When a Meridian road closes for repairs, most of the time vans just take another way. But a few roads are the only link to a whole neighbourhood, and closing one strands every van on the far side. The critical-roads report lists them, so planners know which closures need a detour plan before the cones go out.
Your task
Build critical_roads(junctions, roads). Each [a, b] in `roads` is a two-way road (no road joins a junction to itself, and no two roads join the same pair). A road is critical if closing it leaves some pair of junctions that were connected with no route between them. Return every critical road as [a, b] with a before b alphabetically, the list sorted. Example: critical_roads(["a", "b", "c", "d"], [["a", "b"], ["b", "c"], ["c", "a"], ["c", "d"]]) → [["c", "d"]].

Bridges & Articulation Points

In short: a bridge is a road whose closure splits the network, and both come out of one DFS and one number per junction, the low-link — the smallest discovery number reachable from a junction's subtree by one back road. A tree road parent–child is a bridge exactly when low[child] > disc[parent]: nothing below child can climb back to parent or above. Junctions use the same idea with >= instead of >, since a back road landing exactly on a junction doesn't help once that junction itself is gone.

Two triangles, central-harbor-mill and north-quarry-yard, joined only by the road mill-north, with disc/low badges 0/0, 1/1, 2/0, 3/3, 4/3, 5/3 and mill-north marked red as the one bridge

Roads close. A burst water main, a parade, a resurfacing crew: every week some of Meridian's roads are shut for a day. Usually the vans just go another way. But the road from the mill up to the north side is the only way up there, and the day it closed, three depots' worth of parcels sat undelivered while the planners worked out what had happened.

This lesson finds those roads ahead of time. A road whose closure disconnects the network is a bridge. A junction whose closure disconnects it is an articulation point, also called a cut vertex. Both come from one depth-first search and one number per junction, the low-link.

The obvious way, and why it's slow

The definition gives an algorithm straight away: close each road in turn and check whether the network is still in one piece.

What does this print?
roads = [("a", "b"), ("b", "c"), ("c", "a"), ("c", "d"), ("d", "e")]

def pieces(kept):
    parent = {j: j for j in "abcde"}
    def find(x):
        while parent[x] != x:
            x = parent[x]
        return x
    for a, b in kept:
        parent[find(a)] = find(b)
    return len({find(j) for j in parent})

print(sum(pieces([r for r in roads if r != cut]) > 1 for cut in roads))

It's correct, but every closure means a full pass over the network: O(E × (V + E)). Street networks have about 1.5 roads per junction, so for n junctions one connectivity check costs about 2.5n steps, and closing every road in turn about 3.75n². That passes ten million steps at about 1,600 junctions, which is a small town. A real city has hundreds of thousands, where closing each road costs hundreds of billions of steps. The low-link method below does it in one pass of about 2.5n.

A back road is a way round

Run DFS over the two-way roads. The roads it travels along to discover new junctions form the DFS tree. Every other road is a back road, and in an undirected DFS a back road always joins a junction to one of its own ancestors in the tree. There are no "cross" roads between separate branches, because DFS would have taken such a road to discover the other branch.

A back road is a way round. If some junction below a tree road has a back road climbing above that tree road, the tree road can close and traffic can use the back road instead. So a tree road parent–child is a bridge exactly when nothing in the child's subtree has a back road climbing to the parent or higher.

Discovery numbers and low-links

To make "climbs to the parent or higher" something you can compute, number the junctions 0, 1, 2… in the order DFS discovers them. Ancestors always have smaller numbers. Then give each junction a low-link:

low[j] = the smallest discovery number reachable from j's subtree by going down tree roads and then taking one back road (never the tree road straight back to its parent).

Two updates build it:

  • a back road from j to an earlier junction a: low[j] = min(low[j], disc[a]);
  • a child c finishing: low[j] = min(low[j], low[c]), because whatever c can climb to, j can too.

And the bridge test is one comparison:

Tree road parent–child is a bridge when low[child] > disc[parent].

Watch it on six junctions: two triangles joined by the road from mill to north. Tree roads are marked done, back roads compared, and badges read disc/low:

watch it move · graph

A tree road is a bridge when nothing below it has a back road climbing past it. The low-links carry that fact up the tree.

DFS starts at central and gives it discovery number 0. 6 nodes, 7 edges, undirected. At central. central: 0/0.

1 / 11

The code

Iterative again, with a stack of (junction, parent, roads left). The one subtle line is skipping the parent. The road you arrived on shows up in your own neighbour list, and treating it as a back road would make every low-link climb to its parent, so nothing would ever look like a bridge.

python

One DFS, constant work per road: O(V + E). Space is O(V + E) too: near holds every road twice (once from each end), and disc, low and the stack hold at most one entry per junction.

Trace the low-links on a triangle with a tail:

step through it
1near = {"a": ["b", "c"], "b": ["a", "c"], "c": ["a", "b", "d"], "d": ["c"]}
2disc = {"a": 0}
3low = {"a": 0}
4stack = [("a", None, iter(near["a"]))]
5while stack:
6 j, parent, rest = stack[-1]
7 nxt = next(rest, None)
8 if nxt is None:
9 stack.pop()
10 if parent is not None:
11 low[parent] = min(low[parent], low[j])
12 elif nxt == parent:
13 continue
14 elif nxt in disc:
15 low[j] = min(low[j], disc[nxt])
16 else:
17 disc[nxt] = low[nxt] = len(disc)
18 stack.append((nxt, j, iter(near[nxt])))
19print(disc, low)

Greater than, or greater-or-equal?

The bridge test is strict. If the child's subtree can climb exactly to the parent, the back road lands on the parent itself, which is a way round the tree road. This version uses >=, and gets it wrong:

broken — fix it

Only the tail road c to d is a bridge, but this also reports a to b, which sits on the triangle. Fix the comparison.

>= isn't useless, though. It's the right test for junctions.

Articulation points: the junctions you can't close

Closing a junction closes every road into it. A non-root junction p is an articulation point when some DFS child c has

low[c] >= disc[p]: c's subtree can climb to p but not above it, so without p it's stranded.

That's >= because a back road landing on p doesn't help once p itself is gone. The DFS root needs its own rule, since there's nothing above it: it's critical exactly when it has two or more DFS children. Critical junctions and critical roads are different things:

What does this print?
roads = [("a", "b"), ("b", "c"), ("c", "a"), ("c", "d"), ("d", "e"), ("e", "c")]

def pieces(junctions, kept):
    parent = {j: j for j in junctions}
    def find(x):
        while parent[x] != x:
            x = parent[x]
        return x
    for a, b in kept:
        parent[find(a)] = find(b)
    return len({find(j) for j in junctions})

print(pieces("abde", [r for r in roads if "c" not in r]))

A bridge's endpoints are usually articulation points. The exception is an endpoint with no other roads, like the last house on a dead-end street.

Your turn to drive it

Here's the low-link DFS on the six junctions, badging disc/low and turning every bridge red. Add the road ["harbor", "north"] and run it again. The bridge disappears, because the north side now has a way round.

your code, drawn · graph

Your low-link DFS. Badges read disc/low, and a road turns red when nothing below it can climb past it.

❓ Cross-question: "Does it matter where DFS starts?" Not for the answer. Discovery numbers and low-links change with the starting junction and the neighbour order, but the set of bridges and articulation points is a property of the network itself. What changes is only which junction is the root and needs the special rule.

Idioms & real-world patterns

Where this matters

Network engineers look for bridges and cut vertices to find single points of failure: the one cable, router or substation whose loss splits the network. Power grids, water mains, supply chains and road maps are audited the same way. Adding a single link that creates a way round removes the bridge, and the capstone of this section prices exactly that.

Two-edge-connected pieces

Delete every bridge and what's left falls into two-edge-connected components: groups that survive any single road closure. Shrink each group to a point and the bridges join them into a tree, the bridge tree. It's the undirected cousin of the condensation from the last lesson.

⚡ Advanced: one-way streets without stranding anyone

Robbins' theorem: a connected road network can have every road made one-way so that everyone can still reach everyone exactly when it has no bridges. A bridge made one-way strands one side, and without bridges, DFS gives an orientation that works: tree roads point down, back roads point up. The capstone's boss exercise builds it.

Quick practice

What does this print?
near = {"a": ["b", "d", "e"], "b": ["a", "c"], "c": ["b", "d"], "d": ["c", "a"], "e": ["a"]}
disc, low, found = {}, {}, []

def dfs(v, parent):
    disc[v] = low[v] = len(disc)
    for w in near[v]:
        if w == parent:
            continue
        if w in disc:
            low[v] = min(low[v], disc[w])
        else:
            dfs(w, v)
            low[v] = min(low[v], low[w])
            if low[w] > disc[v]:
                found.append((v, w))

dfs("a", None)
print(found)
broken — fix it

c is the shared junction between two triangles, so closing it splits the network, but this prints []. Fix the comparison.

🎯 Your turn

Write critical_roads(junctions, roads). Return every road whose closure would disconnect junctions that were connected, as [a, b] with a before b alphabetically, the list sorted:

  • critical_roads(["a", "b", "c", "d"], [["a", "b"], ["b", "c"], ["c", "a"], ["c", "d"]]) → [["c", "d"]]
  • a ring of four roads → []

Hint: DFS with discovery numbers and low-links; a tree road is critical when low[child] > disc[parent]. Don't forget junctions in a separate piece of the network.

Then press ▶ Run, tap the Live App try chips to call it with different inputs, and hit ✓ Check. Green = this piece of Meridian is built. ✅

Practice — level up

0/6 solved

Solve each in its own editor — Run to try, Check to grade. Stuck? Reveal a Hint, or the full Solution + walkthrough.

Warm-upClose one road

Write still_connected(junctions, roads, closed) returning True if every junction can still reach every other after the road closed (an [a, b] pair, in either order) is shut. Example: a ring of four roads with one closed → True.

bfsbridge
DrillThe slow way

Write bridges_by_closing(junctions, roads) by brute force: for each road, count the pieces of the network without it; if there are more pieces than with it, that road is critical. Return them as sorted [a, b] pairs, the list sorted. Example: ["a", "b", "c"], [["a", "b"], ["b", "c"]] → [["a", "b"], ["b", "c"]].

bridgeconnected-components
BuildCompute the low-links

Write low_links(junctions, roads) returning {"disc": {...}, "low": {...}}. Run DFS from each undiscovered junction in sorted order, visiting neighbours in sorted order, numbering junctions 0, 1, 2… as they are discovered. A junction's low-link is the smallest discovery number reachable from its DFS subtree using at most one road that is not a tree road (and never the road straight back to its parent). Example: ["a", "b", "c"], [["a", "b"], ["b", "c"], ["c", "a"]] → disc {a: 0, b: 1, c: 2}, low all 0.

low-linkdfs-tree
BossJunctions you can't close

Roadworks sometimes close a whole junction. Write critical_junctions(junctions, roads) returning, sorted, every junction whose closure (with all its roads) would disconnect some other pair of junctions that were connected. Example: ["a", "b", "c"], [["a", "b"], ["b", "c"]] → ["b"].

articulation-pointlow-link
CapstoneWhich closure hurts most?

For a connected network, Meridian ranks critical roads by damage: closing one splits the city into two pieces, and the damage is the number of junctions in the smaller piece. Write worst_closure(junctions, roads) returning [a, b, damage] for the most damaging critical road (a before b alphabetically; on a tie, the smallest [a, b]), or [] if no road is critical. Example: a line a–b–c–d → ["b", "c", 2].

bridgelow-linkdfs-tree
ExplainWhy the root gets its own rule

The test low[child] >= disc[parent] finds critical junctions, except at the DFS root, which is critical only when it has two or more DFS children. Explain why the usual test fails at the root, and why 'two or more children' is exactly right.

critical_roads.py
Call the function you wrote — just like your app's frontend would. Edit the inputs and hit Call.
critical_roads(junctions, roads) → listEvery road whose closure disconnects the network, each [a, b] with a < b, sorted.
try:
returned
Press Run to execute your code.
Press Check to run the tests for this lesson.