Why it matters
Some parts of a network are fragile. In a city, one bridge may be the only road between two districts. In a computer network, one cable or one router may be the only path between two office floors. If that road or router fails, the two sides can no longer reach each other. Engineers want to find these weak points before they fail.
This lesson finds two kinds of weak points in an undirected graph. An undirected graph has edges that go both ways, like a two-way road. A bridge is an edge whose removal splits the graph into more pieces than before. An articulation point, also called a cut vertex, is a vertex whose removal does the same thing. Both can be found in one depth-first search (DFS), the search that goes as deep as it can before it backs up. The trick is to record two numbers for each vertex and compare them.
This lesson assumes you know how DFS walks a graph and how a seen mark stops the walk from going in circles. The strongly connected components lesson in this module deals with directed graphs, which is a different problem. This lesson only deals with undirected graphs.
Words you need
A connected component is a group of vertices where you can walk from any one to any other. An undirected graph can have several components. Removing a bridge or a cut vertex increases the number of components, or splits one component into two.
The DFS tree is the set of edges the DFS used to reach new vertices. Each vertex except the start has exactly one tree edge leading to it, from the vertex that discovered it. The other edges of the graph are back edges. A back edge connects a vertex to one of its ancestors in the tree, which is a vertex that the DFS entered earlier and that is still on the walk.
The discovery time of a vertex, written disc, is a counter value. The counter goes up by one each time the DFS enters a new vertex. The first vertex gets 1, the next gets 2, and so on.
The low value of a vertex, written low, is the smallest discovery time that the vertex can reach by going down the tree and then using at most one back edge from anywhere below it. In plain words, low tells you how far back up the tree you can get from the vertex's subtree, which is the vertex and everything the DFS entered below it.
A small example first
Take three vertices in a line, A - B - C. There are two edges, A-B and B-C. If you remove A-B, then A is alone and B-C remains. The graph splits in two. So A-B is a bridge. Removing B-C also splits the graph, so B-C is also a bridge. Removing B splits A from C, so B is an articulation point. Removing A or C does not split anything that is still connected, so they are not articulation points.
Now add an edge A-C, which makes a triangle. No edge is a bridge any more, because removing any one edge leaves a path that still connects all three. No vertex is an articulation point either. The extra edge gave the graph a way around each vertex.
The question the algorithm answers is simple: is there a way around this edge or this vertex? The low values answer it by checking whether a back edge jumps over the part of the tree below the vertex.
The idea with discovery and low times
Run one DFS from any vertex. Give each vertex a discovery time when the DFS first enters it. Set its low value to the same number at first. Then update the low value as the search goes on.
When the DFS is at vertex v and looks at a neighbour w, there are two cases.
If w has not been seen, it becomes a child of v in the DFS tree. Run the search on w. When that returns, w has a low value. If low[w] is smaller than low[v], then v can also reach that earlier time, so update low[v] to low[w].
If w has already been seen, then the edge v-w is a back edge (or the edge we came in on, which we skip). Then v can reach the discovery time of w. Update low[v] to the smaller of low[v] and disc[w].
Once a child w is finished, compare its low value with the discovery time of v.
If low[w] is greater than disc[v], then no back edge from the subtree of w reaches v or anything above v. So the only connection from w's side to the rest of the graph is the tree edge v-w. That makes v-w a bridge.
If low[w] is greater than or equal to disc[v], then nothing in w's subtree reaches above v. Removing v would cut w's subtree off from the part of the tree above v. So v is an articulation point, unless v is the start vertex. The start vertex needs its own rule, covered below.
Worked example 1: a path
Use the path 0 - 1 - 2 - 3, with edges 0-1, 1-2 and 2-3. Start the DFS at 0. The table below shows the values once each vertex is finished.
vertex: 0 1 2 3
disc: 1 2 3 4
low: 1 2 3 4The DFS goes straight down the path, so there are no back edges and every low value equals its own discovery time.
The search backs up. At vertex 2, the child 3 has low[3] equal to 4. That is greater than disc[2], which is 3. So 2-3 is a bridge, and vertex 2 is an articulation point, because it is not the start and its child's low value is at least its own discovery time. Then at vertex 1, the child 2 has low[2] equal to 3, which is greater than disc[1], which is 2. So 1-2 is a bridge and vertex 1 is an articulation point. Finally at vertex 0, the child 1 has low[1] equal to 2, greater than disc[0], which is 1. So 0-1 is a bridge. Vertex 0 is the start, and it has only one child, so it is not an articulation point.
The three bridges are the three edges. The two articulation points are vertices 1 and 2. The ends, 0 and 3, are not articulation points, because removing an end of a path does not split it.
The program below prints the same answer. Its order of bridges is the order in which the search finishes each tree edge, so it lists 2-3 first.
Worked example 2: a triangle with a tail
Now add a triangle at the start. The graph has vertices 0 to 4 and edges 0-1, 1-2, 2-0, 2-3 and 3-4. The first three form a triangle, and the tail 2-3-4 hangs off vertex 2.
Start the DFS at 0. It goes to 1, then to 2. At vertex 2, the neighbours are 1, 0 and 3, in that order. Vertex 1 is the parent, so skip it. Vertex 0 is already seen, so it is a back edge, and low[2] becomes the smaller of its current value and disc[0], which is 1. So low[2] is 1. Then vertex 3 is new. The DFS goes to 3 and then to 4.
At vertex 3, the child 4 has no back edges, so low[4] is 5, the discovery time of 4. That is greater than disc[3], which is 4. So 3-4 is a bridge. Vertex 3 is an articulation point, because its child's low value is at least its own discovery time.
Back at vertex 2, the child 3 has low[3] equal to 4. That is greater than disc[2], which is 3. So 2-3 is a bridge, and vertex 2 is an articulation point.
Back at vertex 1, the child 2 has low[2] equal to 1. That is not greater than disc[1], which is 2. So 1-2 is not a bridge. Vertex 1 does not become an articulation point from this child. Back at vertex 0, the child 1 has low[1] equal to 1, which is not greater than disc[0], which is also 1. So 0-1 is not a bridge.
The two bridges are 2-3 and 3-4. The two articulation points are vertices 2 and 3. The triangle contributes nothing, because each of its edges has a way around. The rule low[w] >= disc[v] decides the articulation points, and the strict rule low[w] > disc[v] decides the bridges. The mistakes section shows what goes wrong when the two are swapped.
Worked example 3: two triangles, a bridge and a small star
The graph below has nine vertices. Vertices 0, 1 and 2 form a triangle. Vertices 3, 4 and 5 form another triangle. The edges 2-3 and 5-6 join the two triangles to a small star. Vertex 6 has two leaves, 7 and 8.
0-1, 1-2, 2-0, 2-3, 3-4, 4-5, 5-3, 5-6, 6-7, 6-8The program prints these results:
3. two triangles, a bridge and a small star
bridges: 6-7 6-8 5-6 2-3
cut vertices: 2 3 5 6The four bridges are 6-7 and 6-8, which each lead to a single leaf, 5-6, which separates vertex 6 from the second triangle, and 2-3, which separates the two triangles. None of the six edges inside the two triangles is a bridge.
The cut vertices are 2, 3, 5 and 6. Vertex 2 is the only connection from the first triangle to the rest. Vertex 3 is the only connection from the second triangle back toward vertex 2. Vertex 5 is the only connection from the second triangle to vertex 6. Vertex 6 separates its two leaves from everything else. Vertices 0, 1, 4, 7 and 8 are not cut vertices. Removing vertex 4 leaves 3 and 5 connected through the other edge of the triangle.
Worked example 4: the root of the search
The start vertex follows a different rule. Its discovery time is the smallest of all, so the low value of every child is at least that number. The test low[w] >= disc[v] would be true for every child of the start vertex, so it cannot tell whether the start is a cut vertex.
Instead, the start vertex is a cut vertex only if it has at least two children in the DFS tree. Two children mean two separate subtrees. Each subtree can only connect to the other through the start vertex, so removing the start disconnects them.
The star below shows the rule. The centre is vertex 0, and it has three leaves 1, 2 and 3.
3 leaves on vertex 0: 0-1, 0-2, 0-3Starting the DFS at 0 gives three children. The program prints these results:
4. star with centre 0
bridges: 0-1 0-2 0-3
cut vertices: 0Vertex 0 is a cut vertex because it has three children. Each leaf is a bridge, because each leaf is only attached by one edge.
Compare that with a start vertex that has only one child. The start of the path example, vertex 0, has one child, so it is not a cut vertex. Removing it leaves the rest of the path connected.
The parent mistake
The most common mistake in this algorithm is how the code skips the edge it came in on. When the DFS is at a vertex v that was entered from p, it must not treat the edge v-p as a back edge. If it did, low[v] would become disc[p], which would make the tree edge look like a way around itself.
There are two ways to skip the parent. The first skips the neighbour whose vertex number equals the parent's number. The second skips the edge whose index in the edge list equals the edge used to arrive. The second is correct when the graph can have parallel edges, which means two edges between the same pair of vertices.
Here is a graph with two edges between 0 and 1, and one edge from 1 to 2: 0-1, 0-1 and 1-2. The first 0-1 edge is not a bridge, because the second 0-1 edge still connects them. Only 1-2 is a bridge.
Skipping by vertex number removes both 0-1 edges from the search. Then vertex 1 never sees the second edge as a way back to 0, and the first 0-1 edge is wrongly reported as a bridge. Skipping by edge number removes only the edge used to arrive, and the second edge is seen as a back edge.
To check this, I made a separate test copy of the program that skips by vertex number. It printed:
parallel, skip by vertex (wrong): bridges: 1-2 0-1
parallel, skip by edge id (right): bridges: 1-2The same test copy also compared the two tests for bridges on a triangle with a tail. With low > disc the answer is right. With low >= disc, the edge 0-1 in the triangle is wrongly reported:
triangle, low > disc (right): bridges: 3-4 2-3
triangle, low >= disc (wrong): bridges: 3-4 2-3 0-1In the triangle, low[1] equals disc[0], which is 1. The non-strict test asks 1 >= 1, which is true, so the edge is wrongly reported. The strict test asks whether the child reaches strictly above its parent, which is the right question for an edge.
The program
The program below stores each undirected edge once in a list. Each edge gets an index, its edge id. The adjacency list stores the neighbour and the edge id, so the skip check can compare ids. The class runs the DFS from every vertex that has not been seen, so disconnected graphs also work.
#include <algorithm>
#include <cstddef>
#include <iostream>
#include <limits>
#include <string>
#include <utility>
#include <vector>
using Vertex = std::size_t;
using EdgeList = std::vector<std::pair<Vertex, Vertex>>;
constexpr std::size_t no_edge = std::numeric_limits<std::size_t>::max();
struct Neighbour {
Vertex to;
std::size_t edge; // index of the undirected edge in the edge list
};
class CriticalFinder {
public:
CriticalFinder(Vertex n, const EdgeList& edges)
: edges_(edges), adj_(n), disc_(n, 0), low_(n, 0), is_cut_(n, false) {
for (std::size_t id = 0; id < edges.size(); ++id) {
auto [a, b] = edges[id];
adj_[a].push_back({b, id});
adj_[b].push_back({a, id});
}
for (Vertex v = 0; v < n; ++v) {
if (disc_[v] == 0) {
dfs(v, no_edge);
}
}
}
std::vector<std::size_t> bridges() const { return bridges_; }
std::vector<Vertex> cut_vertices() const {
std::vector<Vertex> result;
for (Vertex v = 0; v < is_cut_.size(); ++v) {
if (is_cut_[v]) {
result.push_back(v);
}
}
return result;
}
const EdgeList& edges() const { return edges_; }
private:
void dfs(Vertex v, std::size_t parent_edge) {
disc_[v] = low_[v] = ++timer_;
int children = 0;
for (Neighbour nb : adj_[v]) {
if (nb.edge == parent_edge) {
continue; // skip the one edge we came in on, by its id
}
if (disc_[nb.to] == 0) {
++children;
dfs(nb.to, nb.edge);
low_[v] = std::min(low_[v], low_[nb.to]);
if (low_[nb.to] > disc_[v]) {
bridges_.push_back(nb.edge);
}
if (parent_edge != no_edge && low_[nb.to] >= disc_[v]) {
is_cut_[v] = true;
}
} else {
low_[v] = std::min(low_[v], disc_[nb.to]);
}
}
if (parent_edge == no_edge && children >= 2) {
is_cut_[v] = true; // the root is a cut vertex only with two or more children
}
}
EdgeList edges_;
std::vector<std::vector<Neighbour>> adj_;
std::vector<int> disc_;
std::vector<int> low_;
std::vector<bool> is_cut_;
std::vector<std::size_t> bridges_;
int timer_ = 0;
};
void report(const std::string& name, Vertex n, const EdgeList& edges) {
CriticalFinder f(n, edges);
std::cout << name << "\n";
std::cout << " bridges:";
for (std::size_t id : f.bridges()) {
std::cout << " " << f.edges()[id].first << "-" << f.edges()[id].second;
}
std::cout << "\n cut vertices:";
for (Vertex v : f.cut_vertices()) {
std::cout << " " << v;
}
std::cout << "\n";
}
int main() {
report("1. path 0-1-2-3", 4, {{0, 1}, {1, 2}, {2, 3}});
report("2. triangle with a tail", 5, {{0, 1}, {1, 2}, {2, 0}, {2, 3}, {3, 4}});
report("3. two triangles, a bridge and a small star", 9,
{{0, 1}, {1, 2}, {2, 0}, {2, 3}, {3, 4}, {4, 5}, {5, 3}, {5, 6}, {6, 7}, {6, 8}});
report("4. star with centre 0", 4, {{0, 1}, {0, 2}, {0, 3}});
report("5. two parallel edges 0-1 and one edge 1-2", 3, {{0, 1}, {0, 1}, {1, 2}});
}Compile and run it with the warning flags turned on:
g++ -std=c++20 -Wall -o bridges bridges.cpp && ./bridgesThe output is:
1. path 0-1-2-3
bridges: 2-3 1-2 0-1
cut vertices: 1 2
2. triangle with a tail
bridges: 3-4 2-3
cut vertices: 2 3
3. two triangles, a bridge and a small star
bridges: 6-7 6-8 5-6 2-3
cut vertices: 2 3 5 6
4. star with centre 0
bridges: 0-1 0-2 0-3
cut vertices: 0
5. two parallel edges 0-1 and one edge 1-2
bridges: 1-2
cut vertices: 1The program uses Vertex (a std::size_t) for vertex numbers and int for the discovery counter. Mixing those two types in a comparison produces a warning, which is covered in the mistakes section.
Cost
The search visits each vertex once and each edge twice, once from each end. The total time is proportional to the number of vertices plus the number of edges. The extra memory is one array of discovery times, one of low values, and one of cut flags, with one entry per vertex, plus the adjacency list.
The same recursion warning as in the strongly connected components lesson applies here. A very long path can make the recursion deeper than the call stack allows.
Common mistakes
Skipping the parent by vertex number. This gives wrong bridges when two parallel edges join the same pair of vertices. Skip by edge id instead, as the program does. The output above shows the wrong answer, 1-2 0-1, next to the right answer, 1-2.
Using >= for bridges. The test for a bridge is low[w] > disc[v], strictly greater. With >=, the edge 0-1 in a triangle is reported as a bridge, even though the triangle gives a way around it. The output above shows this with bridges: 3-4 2-3 0-1.
Using > for articulation points. The test for a non-root cut vertex is low[w] >= disc[v]. Take the graph 0-1, 1-2, 2-3 and 3-1. Vertex 1 is a cut vertex, because removing it separates 0 from the triangle 1-2-3. The DFS from 0 gives low[3] equal to 2, which is disc[1], and low[2] also becomes 2. The strict test asks 2 > 2, which is false, so it misses vertex 1. The program with >= prints cut vertices: 1 for this graph, as the check run showed for the same graph.
Treating the root like any other vertex. The root is a cut vertex only when it has at least two children. Applying low[w] >= disc[v] to the root makes every root a cut vertex, which is wrong for the triangle with a tail. The program keeps the root in a separate branch of the code.
Updating from a child's discovery time instead of its low value. When a child finishes, the parent must take the child's low value, low[w], not its discovery time disc[w]. Using the discovery time misses back edges that reach above the child.
Forgetting to start the search from every vertex. A graph can have several components. If the outer loop starts only at vertex 0, the vertices in other components are never visited, and their bridges and cut vertices are missing. The program starts a new search from each unseen vertex.
Comparing a signed counter with an unsigned index. The discovery counter is an int, and Vertex is a std::size_t. Writing for (int i = 0; i < is_cut_.size(); ++i) produces the same kind of -Wsign-compare warning shown in the strongly connected components lesson. Keep vertex numbers as std::size_t and loop with that type.
Practice
Exercise 1. A graph is a path with two edges, 0-1 and 1-2. List its bridges and its cut vertices.
Show the answer
Both edges are bridges, 0-1 and 1-2. Vertex 1 is the only cut vertex, because removing it separates 0 from 2. Vertices 0 and 2 are not cut vertices, because removing either one leaves a path that is still connected.
Exercise 2. A graph is a cycle of four vertices, with edges 0-1, 1-2, 2-3 and 3-0. List its bridges and its cut vertices.
Show the answer
There are no bridges and no cut vertices. Removing any one edge leaves a path that still connects all four vertices. Removing any one vertex leaves three vertices in a path, which is still connected.
Exercise 3. A graph has two vertices and two parallel edges between them, both joining 0 and 1. List its bridges and its cut vertices.
Show the answer
There are no bridges and no cut vertices. Removing either edge leaves the other edge, so the two vertices stay connected. Removing either vertex leaves a single vertex, which is still one component.
Exercise 4. Two triangles share one vertex. The triangles are 0-1-2-0 and 2-3-4-2. List the bridges and the cut vertices. Then explain why vertex 2 is a cut vertex and no edge is a bridge.
Show the answer
There are no bridges, because every edge is part of a triangle. The only cut vertex is 2. Removing 2 separates {0, 1} from {3, 4}. Vertex 2 is the only point the two triangles share, so removing it cuts both sides off from each other. Each edge in a triangle has a way around it, so no edge is a bridge.
Exercise 5. Run the DFS by hand on the path 0-1-2, starting at 0, and write the discovery and low values of each vertex. Then say which vertices are cut vertices.
Show the answer
Vertex 0 gets disc 1, vertex 1 gets disc 2, and vertex 2 gets disc 3. There are no back edges, so each low value equals its discovery time: low 1, 2 and 3. At vertex 1, the child 2 has low 3, which is greater than disc 2, so vertex 1 is a cut vertex. Vertex 0 is the root with one child, so it is not. Vertex 2 is a leaf, so it is not. The only cut vertex is 1.
Summary
- A bridge is an edge whose removal splits an undirected graph into more pieces, and an articulation point is a vertex whose removal does the same.
- One DFS records a discovery time and a low value for each vertex, and comparing a child's low value with its parent's discovery time finds both kinds of weak point.
- The test for a bridge is strictly greater, and the test for a non-root cut vertex is greater than or equal.
- The start vertex is a cut vertex only when it has at least two children in the DFS tree.
- Skip the parent edge by its edge id, not by the parent's vertex number, so that parallel edges count as a way around.