Senior LevelData Structures & Algorithms
How do you find Articulation Points and Bridges in a graph?
ā Interview Prompt: Explain Articulation Points (cut vertices) and Bridges (cut edges) using Tarjan's DFS algorithm with discovery and low values.
An Articulation Point is a vertex whose removal disconnects the graph. A Bridge is an edge whose removal disconnects the graph.
Tarjan's Algorithm ā $O(V + E)$:
Maintains:
ā¢
disc[u]: Discovery time of vertex $u$.ā¢
low[u]: Lowest discovery time reachable from the subtree of $u$ via back edges.Articulation Point Conditions:
1
Root of DFS tree with ā„ 2 children.
2
Non-root node $u$ where
low[v] >= disc[u] for some child $v$.Bridge Condition:
Edge $(u, v)$ is a bridge if low[v] > disc[u].
Code Implementation Example
typescript
function findBridges(n: number, edges: [number, number][]): [number, number][] {
const adj: number[][] = Array.from({ length: n }, () => []);
for (const [u, v] of edges) { adj[u].push(v); adj[v].push(u); }
const disc = new Array(n).fill(-1), low = new Array(n).fill(0);
const bridges: [number, number][] = [];
let timer = 0;
function dfs(u: number, parent: number): void {
disc[u] = low[u] = timer++;
for (const v of adj[u]) {
if (disc[v] === -1) {
dfs(v, u);
low[u] = Math.min(low[u], low[v]);
if (low[v] > disc[u]) bridges.push([u, v]); // bridge!
} else if (v !== parent) {
low[u] = Math.min(low[u], disc[v]); // back edge
}
}
}
for (let i = 0; i < n; i++) if (disc[i] === -1) dfs(i, -1);
return bridges;
}š”Tarjan's bridge-finding algorithm using discovery and low values ā O(V+E).
šÆ Interview Key Takeaway
Articulation points and bridges identify critical infrastructure in networks (single point of failure). Tarjan's DFS finds them in O(V+E) using low-link values.
#DSA#Articulation Points#Bridges#Tarjan#Senior
Back to all Data Structures & Algorithms Questionsā