AlgoScope

Bridges

One DFS with discovery times and low-links. A tree edge u-v is a bridge when low[v] > disc[u].

Connectivity and topological order, algorithm, advanced
Back edge 2 to 0, low of 2 is 0.0011203456u
Back edge 2 to 0, low of 2 is 0.0011203456u

Bridges and Components: Two triangles and a pendant

Decision, step 5 of 19

Edge 2-0 leads to a vertex seen at time 0, an ancestor on the current path. That is earlier than low[2] = 2, so low[2] becomes 0: 2 can climb to 0.

Cost

Best
O(V + E)
Average
O(V + E)
Worst
O(V + E)
Space
O(V)

Leads to

Topics that need this one first.

Taught by the same lesson

Bridges and Components covers these too, in the same run.