What are Articulation Points and Bridges in a Graph?
Learn articulation points and bridges in graphs, the DFS low-link technique, and how to answer this graph algorithms interview question.
Expected Interview Answer
An articulation point (or cut vertex) is a vertex in an undirected graph whose removal increases the number of connected components, and a bridge is an edge whose removal does the same — both are found in a single O(V + E) DFS using discovery times and low-link values.
During DFS, every vertex gets a discovery time and a low-link value, the lowest discovery time reachable from that vertex's subtree using at most one back edge. A non-root vertex u is an articulation point if it has a child v in the DFS tree where low[v] >= disc[u], meaning v's subtree cannot reach back above u without going through u. The root of the DFS tree is a special case: it is an articulation point only if it has two or more independent DFS-tree children. A bridge is even simpler to detect: edge (u, v) is a bridge if low[v] > disc[u] strictly, meaning v's subtree has no back edge reaching u or higher at all. Both concepts identify structural weak points — single vertices or edges whose failure fragments the network — which is why they matter for network reliability, circuit design, and social network analysis.
- Finds single points of failure in one linear DFS pass
- Bridges reveal edges with no redundant back-path
- Directly informs network reliability and redundancy planning
- Low-link technique reused across SCC and 2-edge-connectivity algorithms
AI Mentor Explanation
An articulation point is like a single all-rounder in a squad whose absence would split the team's tactical options into disconnected groups — bowlers who can no longer combine with certain batsmen without that all-rounder bridging the gap. A bridge is like one specific fielding-rotation link between two specialists that, if broken, leaves no other rotation path connecting them at all. Coaches identify these weak points by tracking, for every player, how far back up the squad's dependency chain their absence could still be covered by someone else. A squad with no articulation points has real depth — losing any one player still leaves every combination reachable through someone else.
Step-by-Step Explanation
Step 1
Run DFS tracking discovery time and low-link
For each vertex u, disc[u] is its DFS visit order; low[u] starts equal to disc[u] and is lowered via back edges.
Step 2
Update low-link through tree and back edges
For a DFS-tree child v of u, low[u] = min(low[u], low[v]); for a back edge to an ancestor w, low[u] = min(low[u], disc[w]).
Step 3
Test the articulation point condition
A non-root u is an articulation point if some child v has low[v] >= disc[u]; the root is one only if it has 2+ DFS-tree children.
Step 4
Test the bridge condition
Edge (u, v) is a bridge if low[v] > disc[u] strictly, meaning no back edge from v's subtree reaches u or higher.
What Interviewer Expects
- Define articulation point and bridge precisely, with the distinction between vertex and edge removal
- Explain discovery time vs low-link value clearly
- State the special-case root rule for articulation points
- Give a real use case: network reliability, single points of failure
Common Mistakes
- Using >= instead of > for the bridge condition (off-by-one on strictness)
- Forgetting the special root-of-DFS-tree rule for articulation points
- Confusing a back edge to the immediate parent with a genuine back edge to an ancestor
- Assuming these concepts apply directly to directed graphs without modification
Best Answer (HR Friendly)
“An articulation point is a single node whose removal would break the network into disconnected pieces, and a bridge is the same idea but for a single edge. I find both with one DFS pass by tracking how far back up the traversal each node can reach — I think of it as finding the network's single points of failure.”
Code Example
def find_articulation_and_bridges(graph, num_vertices):
disc = [-1] * num_vertices
low = [-1] * num_vertices
timer = [0]
articulation_points = set()
bridges = []
def dfs(u, parent):
disc[u] = low[u] = timer[0]
timer[0] += 1
children = 0
for v in graph.get(u, []):
if v == parent:
continue
if disc[v] == -1:
children += 1
dfs(v, u)
low[u] = min(low[u], low[v])
if parent != -1 and low[v] >= disc[u]:
articulation_points.add(u)
if low[v] > disc[u]:
bridges.append((u, v))
else:
low[u] = min(low[u], disc[v])
if parent == -1 and children >= 2:
articulation_points.add(u)
for vertex in range(num_vertices):
if disc[vertex] == -1:
dfs(vertex, -1)
return articulation_points, bridgesFollow-up Questions
- How would you find all biconnected components using the same low-link technique?
- Why is the DFS root treated as a special case for articulation points?
- How would you adapt this to find 2-edge-connected components?
- How do articulation points relate to designing redundant network topologies?
MCQ Practice
1. What condition identifies a non-root vertex u as an articulation point, for a DFS-tree child v?
If low[v] >= disc[u], v's subtree has no back edge reaching above u, so removing u disconnects that subtree.
2. When is the root of the DFS tree considered an articulation point?
With two or more independent DFS-tree children, removing the root disconnects those subtrees from each other.
3. What is the strict condition for edge (u, v) to be a bridge?
A strict low[v] > disc[u] means no back edge from v's subtree reaches u or higher, so the edge is the only connection.
Flash Cards
What is an articulation point? — A vertex whose removal increases the number of connected components in the graph.
What is a bridge? — An edge whose removal increases the number of connected components in the graph.
What two values does the DFS track per vertex to find these? — Discovery time (disc) and low-link value (low), the lowest discovery time reachable via a back edge.
What is the special rule for the DFS root as an articulation point? — The root is an articulation point only if it has two or more independent DFS-tree children.