Speed
Step Log
Node State (disc / low)
| Node | disc | low | parent | AP? |
|---|
How It Works
Bridges: Edge
Articulation Points: Vertex
• Root of DFS tree with 2+ children, or
• Non-root where some child
Both are found in a single O(V + E) DFS pass using discovery time and low values.
(u,v) is a bridge if low[v] > disc[u] — removing it disconnects the graph.Articulation Points: Vertex
u is an AP if:• Root of DFS tree with 2+ children, or
• Non-root where some child
v has low[v] ≥ disc[u].Both are found in a single O(V + E) DFS pass using discovery time and low values.
Legend
Unvisited node
Current DFS node
Visited (in DFS tree)
Bridge endpoint
Articulation point
Tree edge
Back edge
Bridge edge