Data Structures & AlgorithmsArticulation Points & Bridges

Articulation Points & Bridges

LevelAdvanced

Duration90 mins

TopicArticulation Points & Bridges

3 / 4

Finding Articulation Points and Bridges with DFS

The Elegant Algorithm of Robert Tarjan

In the previous pages, we developed deep conceptual understanding of articulation points and bridges. We saw how the naive approach—removing each vertex or edge and checking connectivity—leads to O(V(V+E)) complexity, far too slow for large networks.

Now we turn to Tarjan's algorithm, an elegant algorithm developed by computer scientist Robert Tarjan in the 1970s. This algorithm finds all articulation points and bridges in a single depth-first search traversal, achieving optimal O(V + E) time complexity.

Tarjan's insight was recognizing that the DFS tree structure, combined with carefully tracked metadata about reachability, contains all the information needed to identify critical vertices and edges without explicitly testing their removal.

What You Will Master

By the end of this page, you will fully understand Tarjan's algorithm: the discovery time and low-link values, the detection conditions for both articulation points and bridges, the complete implementation with proper edge case handling, and complexity analysis. You'll be able to implement this from first principles.

Algorithm Overview: The Key Concepts

Before diving into code, let's establish the conceptual framework. The algorithm relies on three key ideas:

1. DFS Tree Structure

When we perform DFS on a connected undirected graph, we implicitly construct a spanning tree (the DFS tree) where:

Every vertex is visited exactly once
Edges used to discover new vertices become tree edges
Remaining edges connect descendants to ancestors (back edges)

2. Discovery Time (disc)

We assign each vertex a timestamp when DFS first visits it. This creates a linear ordering of vertices that reflects the DFS traversal order:

disc[v] = the step number when v is first visited

3. Low-Link Value (low)

For each vertex, we compute the earliest (lowest) discovery time reachable from its subtree:

low[v] = minimum of:
  - disc[v] (can reach itself)
  - low[u] for all children u in DFS tree (reaches of descendants)
  - disc[w] for all back edges (v, w) (direct reach to ancestors)

Low Value Intuition

Think of low[v] as answering: 'What's the earliest-discovered vertex that v or any of v's descendants can reach by going down tree edges and then up at most one back edge?' This captures how far 'back' the subtree can reach.

Detection Conditions Summary
Element	Condition	Intuition
Articulation Point (non-root)	Has child u where low[u] ≥ disc[v]	Child's subtree can't escape above v
Articulation Point (root)	Has ≥ 2 children in DFS tree	Removing root separates children
Bridge (u→v tree edge)	low[v] > disc[u]	Child's subtree can't even reach u

Why the difference between ≥ and > ?

For articulation points: If low[u] = disc[v], the subtree can reach v itself (via a back edge to v), but not above. Removing v still disconnects the subtree from everything above v.

For bridges: If low[v] = disc[u], there's a back edge from v's subtree to u, creating a cycle that includes edge (u,v). The edge is not a bridge because the cycle provides an alternative path.

Complete Algorithm Implementation

Here's the complete, production-ready implementation that finds both articulation points and bridges in a single DFS traversal.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
interface ArticulationBridgeResult {
    articulationPoints: number[];
    bridges: [number, number][];
}
 
/**
 * Finds all articulation points and bridges in an undirected graph.
 * Uses Tarjan's algorithm with O(V + E) time complexity.
 * 
 * @param graph - Adjacency list representation (vertex -> neighbors)
 * @returns Object containing arrays of articulation points and bridges
 */
function findCriticalElements(
    graph: Map<number, number[]>
): ArticulationBridgeResult {
    const n = graph.size;
    if (n === 0) return { articulationPoints: [], bridges: [] };
    
    // Track discovery time and low values
    const disc: Map<number, number> = new Map();
    const low: Map<number, number> = new Map();
    
    // Track parent for each vertex in DFS tree
    const parent: Map<number, number | null> = new Map();
    
    // Results
    const articulationPoints: Set<number> = new Set();
    const bridges: [number, number][] = [];
    
    // Timer for discovery times
    let timer = 0;
    
    /**
     * DFS function that computes disc and low values
     * while identifying articulation points and bridges.
     */
    function dfs(vertex: number): void {
        // Initialize discovery time and low value
        disc.set(vertex, timer);
        low.set(vertex, timer);
        timer++;
        
        // Count children in DFS tree (for root check)
        let childCount = 0;
        
        for (const neighbor of (graph.get(vertex) || [])) {
            if (!disc.has(neighbor)) {
                // Unvisited vertex: tree edge
                childCount++;
                parent.set(neighbor, vertex);
                
                // Recurse on child
                dfs(neighbor);
                
                // After DFS returns, update low value
                low.set(vertex, Math.min(low.get(vertex)!, low.get(neighbor)!));
                
                // Check for articulation point (non-root case)
                // If child can't reach above this vertex, this vertex is critical
                if (parent.get(vertex) !== null && 
                    low.get(neighbor)! >= disc.get(vertex)!) {
                    articulationPoints.add(vertex);
                }
                
                // Check for bridge
                // If child can't reach this vertex or above, edge is a bridge
                if (low.get(neighbor)! > disc.get(vertex)!) {
                    bridges.push([vertex, neighbor]);
                }
            } else if (neighbor !== parent.get(vertex)) {
                // Already visited and not parent: back edge
                // Update low value with neighbor's discovery time
                low.set(vertex, Math.min(low.get(vertex)!, disc.get(neighbor)!));
            }
            // If neighbor is parent, we ignore (not a back edge)
        }
        
        // Check for articulation point (root case)
        // Root is an articulation point iff it has ≥ 2 children
        if (parent.get(vertex) === null && childCount >= 2) {
            articulationPoints.add(vertex);
        }
    }
    
    // Handle disconnected graphs by running DFS from all unvisited vertices
    for (const vertex of graph.keys()) {
        if (!disc.has(vertex)) {
            parent.set(vertex, null);  // Mark as root of DFS tree
            dfs(vertex);
        }
    }
    
    return {
        articulationPoints: Array.from(articulationPoints),
        bridges: bridges,
    };
}

Critical Detail: Parent Check

When processing neighbors, we must distinguish between back edges (neighbor is ancestor but not parent) and the edge to our parent. If we don't skip the parent, we'd incorrectly treat the tree edge as a back edge, corrupting low values.

Step-by-Step Algorithm Trace

Let's trace through the algorithm on a concrete example to solidify understanding.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Graph Structure:
 
    0 ─── 1 ─── 2
          │ \   │
          │  \  │
          3 ──── 4
          
Adjacency List:
  0: [1]
  1: [0, 2, 3, 4]
  2: [1, 4]
  3: [1, 4]
  4: [1, 2, 3]
 
Starting DFS from vertex 0...

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
STEP 1: dfs(0)
  Visit 0: disc[0] = 0, low[0] = 0, parent[0] = null
  Neighbors of 0: [1]
  
  STEP 2: Process neighbor 1 (unvisited → tree edge)
    childCount for 0 = 1
    parent[1] = 0
    
    STEP 3: dfs(1)
      Visit 1: disc[1] = 1, low[1] = 1, parent[1] = 0
      Neighbors of 1: [0, 2, 3, 4]
      
      Process neighbor 0: visited AND is parent → skip
      
      STEP 4: Process neighbor 2 (unvisited → tree edge)
        childCount for 1 = 1
        parent[2] = 1
        
        STEP 5: dfs(2)
          Visit 2: disc[2] = 2, low[2] = 2, parent[2] = 1
          Neighbors of 2: [1, 4]
          
          Process neighbor 1: visited AND is parent → skip
          
          STEP 6: Process neighbor 4 (unvisited → tree edge)
            childCount for 2 = 1
            parent[4] = 2
            
            STEP 7: dfs(4)
              Visit 4: disc[4] = 3, low[4] = 3, parent[4] = 2
              Neighbors of 4: [1, 2, 3]
              
              Process neighbor 1: visited, not parent (1 ≠ 2)
                → Back edge! low[4] = min(3, disc[1]) = min(3, 1) = 1
              
              Process neighbor 2: visited AND is parent → skip
              
              STEP 8: Process neighbor 3 (unvisited → tree edge)
                childCount for 4 = 1
                parent[3] = 4
                
                STEP 9: dfs(3)
                  Visit 3: disc[3] = 4, low[3] = 4, parent[3] = 4
                  Neighbors of 3: [1, 4]
                  
                  Process neighbor 1: visited, not parent
                    → Back edge! low[3] = min(4, disc[1]) = min(4, 1) = 1
                  
                  Process neighbor 4: visited AND is parent → skip
                  
                  childCount for 3 = 0 (no tree children)
                  parent[3] = 4 ≠ null, not root
                  No articulation point check for root applies
                  
                  Return from dfs(3)
                
                Back in dfs(4):
                Update low[4] = min(low[4], low[3]) = min(1, 1) = 1
                
                Articulation point check: parent[4] = 2 ≠ null
                  low[3] = 1 ≥ disc[4] = 3? NO (1 < 3)
                  → 4 is NOT an articulation point (based on child 3)
                
                Bridge check: low[3] = 1 > disc[4] = 3? NO
                  → (4,3) is NOT a bridge
              
              childCount for 4 = 1
              parent[4] = 2 ≠ null, not root
              
              Return from dfs(4)
            
            Back in dfs(2):
            Update low[2] = min(low[2], low[4]) = min(2, 1) = 1
            
            Articulation point check:
              low[4] = 1 ≥ disc[2] = 2? NO
              → 2 is NOT an articulation point
            
            Bridge check: low[4] = 1 > disc[2] = 2? NO
              → (2,4) is NOT a bridge
          
          childCount for 2 = 1
          Return from dfs(2)
        
        Back in dfs(1):
        Update low[1] = min(low[1], low[2]) = min(1, 1) = 1
        
        Articulation point check:
          low[2] = 1 ≥ disc[1] = 1? YES!
          → 1 IS an articulation point!
        
        Bridge check: low[2] = 1 > disc[1] = 1? NO
          → (1,2) is NOT a bridge
      
      STEP 10: Process neighbor 3 in dfs(1)
        3 is already visited (disc[3] = 4), not parent (parent[1] = 0)
        → Back edge! low[1] = min(1, disc[3]) = min(1, 4) = 1
      
      STEP 11: Process neighbor 4 in dfs(1)  
        4 is already visited, not parent
        → Back edge! low[1] = min(1, disc[4]) = min(1, 3) = 1
      
      childCount for 1 = 1 (only 2 was a tree child)
      parent[1] = 0 ≠ null, not root
      
      Return from dfs(1)
    
    Back in dfs(0):
    Update low[0] = min(low[0], low[1]) = min(0, 1) = 0
    
    Articulation point check:
      low[1] = 1 ≥ disc[0] = 0? YES!
      → 0 IS an articulation point!
    
    Bridge check: low[1] = 1 > disc[0] = 0? YES!
      → (0,1) IS a bridge!
  
  childCount for 0 = 1
  parent[0] = null, is root
  Root articulation point check: childCount = 1 ≥ 2? NO
  
  Return from dfs(0)
 
FINAL VALUES:
  Vertex | disc | low | parent
  -------|------|-----|-------
    0    |  0   |  0  |  null
    1    |  1   |  1  |   0
    2    |  2   |  1  |   1
    3    |  4   |  1  |   4
    4    |  3   |  1  |   2
 
RESULTS:
  Articulation Points: {1} 
  (0 was added but let's verify - wait, we added 0 above!)
  
Let me re-check: In step when we processed (0,1) tree edge...
  parent[0] = null, but we checked parent.get(vertex) !== null
  for the articulation check. So 0 was NOT added via non-root path.
  
  For root check: childCount = 1, not ≥ 2, so 0 NOT added.
  
  Articulation Points: {1}
  Bridges: {(0,1)}

Verification

Let's verify: Remove vertex 1 → components {0} and {2,3,4}. Correct! Remove edge (0,1) → {0} disconnected from {1,2,3,4}. Correct! The cycle 1-2-4-1 and 1-3-4-1 protect those edges from being bridges, but can't save vertex 1.

Edge Cases and Corner Cases

Production implementations must handle various edge cases correctly. Let's examine each.

Edge Cases to Handle

•Empty graph: No vertices → no articulation points or bridges. Return empty results.
•Single vertex: One vertex, no edges → no articulation points, no bridges.
•Two vertices, one edge: The edge is a bridge. Neither vertex is an articulation point (each is a leaf relative to the other).
•Disconnected graph: Must run DFS from all unvisited vertices. Each component analyzed independently.
•Self-loops: Edge (v,v) → not a bridge (removing it doesn't disconnect anything). Implementation should handle gracefully.
•Multiple edges (multigraph): Multiple edges between same vertices → typically none are bridges (parallels provide redundancy).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
function findCriticalElementsRobust(
    graph: Map<number, number[]>
): ArticulationBridgeResult {
    // Edge case: empty graph
    if (graph.size === 0) {
        return { articulationPoints: [], bridges: [] };
    }
    
    // Edge case: single vertex
    if (graph.size === 1) {
        return { articulationPoints: [], bridges: [] };
    }
    
    const disc: Map<number, number> = new Map();
    const low: Map<number, number> = new Map();
    const parent: Map<number, number | null> = new Map();
    const articulationPoints: Set<number> = new Set();
    const bridges: [number, number][] = [];
    let timer = 0;
    
    function dfs(vertex: number): void {
        disc.set(vertex, timer);
        low.set(vertex, timer);
        timer++;
        
        let childCount = 0;
        
        for (const neighbor of (graph.get(vertex) || [])) {
            // Edge case: self-loop (skip)
            if (neighbor === vertex) continue;
            
            if (!disc.has(neighbor)) {
                childCount++;
                parent.set(neighbor, vertex);
                dfs(neighbor);
                
                low.set(vertex, Math.min(
                    low.get(vertex)!, 
                    low.get(neighbor)!
                ));
                
                // Articulation point check (non-root)
                if (parent.get(vertex) !== null && 
                    low.get(neighbor)! >= disc.get(vertex)!) {
                    articulationPoints.add(vertex);
                }
                
                // Bridge check
                if (low.get(neighbor)! > disc.get(vertex)!) {
                    bridges.push([vertex, neighbor]);
                }
            } else if (neighbor !== parent.get(vertex)) {
                // Back edge
                low.set(vertex, Math.min(
                    low.get(vertex)!, 
                    disc.get(neighbor)!
                ));
            }
        }
        
        // Root articulation point check
        if (parent.get(vertex) === null && childCount >= 2) {
            articulationPoints.add(vertex);
        }
    }
    
    // Handle disconnected graphs
    for (const vertex of graph.keys()) {
        if (!disc.has(vertex)) {
            parent.set(vertex, null);
            dfs(vertex);
        }
    }
    
    return {
        articulationPoints: Array.from(articulationPoints),
        bridges: bridges,
    };
}

Multigraph Consideration

For multigraphs with parallel edges, the simple parent check isn't sufficient. We need to track which specific edge we came from, not just which vertex. One approach: use edge indices instead of parent vertices, or count edges to parent and only treat as back edge if we've used all edges to the parent vertex.

The Root Special Case: Deep Explanation

The root of the DFS tree requires special handling for articulation point detection. Understanding why reveals important insights about the algorithm's design.

Why the normal condition fails for the root:

The normal articulation point condition is: vertex v is an articulation point if it has a child u with low[u] ≥ disc[v].

For the root r with disc[r] = 0:

ANY vertex u in the graph has low[u] ≥ 0 (low values are non-negative)
So the condition low[u] ≥ disc[r] = 0 is ALWAYS true!
This would incorrectly mark the root as an articulation point in every graph.

The correct interpretation:

The intuition behind low[u] ≥ disc[v] is: 'No back edges escape u's subtree to above v.'

But for the root, there IS no 'above.' The root has no ancestors. So we need a different criterion: does removing the root disconnect its children from each other?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
CASE 1: Root with 1 DFS child
═══════════════════════════════
 
    1 (root)          If we remove 1:
    │                 The remaining graph is {2,3,4,5}
    2                 Still connected!
   / \                → 1 is NOT an articulation point
  3   4
  │
  5
 
Only 2 is a DFS child of 1 (3,4,5 are descendants but not direct children).
 
 
CASE 2: Root with ≥2 DFS children  
════════════════════════════════════
 
    1 (root)          If we remove 1:
   / \                {2,3} and {4,5} become disconnected!
  2   4               → 1 IS an articulation point
  │   │
  3   5
 
Both 2 and 4 are DFS children of 1.
Removing 1 disconnects their subtrees.
 
 
CASE 3: Root with multiple neighbors but 1 DFS child
═══════════════════════════════════════════════════════
 
    1 (root)          DFS from 1 might go: 1→2→3→4→1(back)→5→1(back)  
   /│\                Only 2 is a tree child! (3,4 via 2; 5 has back edge)
  2 4 5──┐            
  │ │    │            Actually wait, let me redo:
  3─┘    │            DFS: 1→2→3→4(back to 1 or 2?)→5
         │            
If there are edges 1-2, 2-3, 3-4, 4-1, 1-5:
 
Tree edges from 1: to 2, and to 5 (if 5 visited after 4's back edge)
That's 2 DFS children → 1 IS articulation point.
 
Key insight: DFS children ≠ neighbors. It depends on discovery order.

Root Choice Doesn't Matter

The algorithm correctly identifies all articulation points regardless of which vertex we choose as the DFS root. A vertex that's an articulation point will be detected whether it's the root (via the child count check) or a non-root (via the low value check).

Alternative Low-Link Formulations

Different textbooks and implementations define the low value slightly differently. Understanding these variations prevents confusion when comparing implementations.

Low Value Definition Variants
Variant	Definition	Back Edge Update
Standard (disc)	min reachable disc time	low[v] = min(low[v], disc[ancestor])
Alternative (low)	min reachable low time	low[v] = min(low[v], low[ancestor])

Important subtlety for bridges:

With the standard definition (using disc[ancestor] for back edges), the bridge condition low[v] > disc[u] works correctly.

With the alternative definition (using low[ancestor]), we must be more careful. Consider:

Vertex x has disc[x] = 1, low[x] = 0 (due to back edge to disc=0)
Vertex y discovered after x, has back edge to x

With alternative definition: low[y] could become 0 (taking low[x]) With standard definition: low[y] becomes 1 (taking disc[x])

For bridges, the standard definition is typically preferred for correctness.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// STANDARD FORMULATION (Recommended for bridges)
// Back edge update uses discovery time
if (neighbor !== parent.get(vertex)) {
    low.set(vertex, Math.min(
        low.get(vertex)!, 
        disc.get(neighbor)!  // Use disc, not low
    ));
}
 
// Bridge check: works correctly
if (low.get(neighbor)! > disc.get(vertex)!) {
    bridges.push([vertex, neighbor]);
}
 
// ─────────────────────────────────────────────
 
// ALTERNATIVE FORMULATION (Some implementations)
// Back edge update uses low value
if (neighbor !== parent.get(vertex)) {
    low.set(vertex, Math.min(
        low.get(vertex)!, 
        low.get(neighbor)!  // Use low instead
    ));
}
 
// Bridge check: may need adjustment for correctness
// The condition low[v] > disc[u] may incorrectly identify
// some non-bridges as bridges in specific graph configurations.

Best Practice

Use disc[neighbor] (not low[neighbor]) when updating low values via back edges. This is the standard definition and works correctly for both articulation point and bridge detection without modification.

Complexity Analysis

Let's rigorously analyze the time and space complexity of Tarjan's algorithm.

Time Complexity: O(V + E)

•DFS visits each vertex exactly once: O(V) total vertex visits.
•Each edge examined exactly twice: Once from each endpoint, contributing O(E) to neighbor processing.
•Update operations are O(1): Setting disc, low, checking conditions are constant time.
•No nested loops over graph structure: Single pass through adjacency lists.
•Total: O(V + E), which is optimal (we must read the entire graph at minimum).

Space Complexity: O(V)

•Discovery times: O(V) for disc array/map.
•Low values: O(V) for low array/map.
•Parent tracking: O(V) for parent array/map.
•Recursion stack: O(V) in worst case (path graph).
•Result storage: O(V) for articulation points, O(E) for bridges in worst case.

Complexity Comparison with Naive Approach
Aspect	Naive Approach	Tarjan's Algorithm
Time Complexity	O(V × (V + E))	O(V + E)
Space Complexity	O(V + E)	O(V)
of DFS Traversals	V (one per vertex test)	1
For \|V\|=1000, \|E\|=5000	~6 million ops	~6 thousand ops
For \|V\|=1M, \|E\|=10M	~10¹³ ops (years)	~10⁷ ops (seconds)

Why O(V + E) is Optimal

Any algorithm for finding articulation points or bridges must examine every vertex and edge at least once—an edge could be the single bridge, and we can't know without checking. Thus Ω(V + E) is a lower bound, and Tarjan's O(V + E) achieves this optimum.

Iterative Implementation (Stack-Based)

The recursive implementation may cause stack overflow on very deep graphs. Here's an iterative version using explicit stack management.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
interface StackFrame {
    vertex: number;
    neighborIndex: number;  // Which neighbor are we processing?
    childCount: number;     // DFS tree children count
}
 
function findCriticalElementsIterative(
    graph: Map<number, number[]>
): ArticulationBridgeResult {
    if (graph.size === 0) return { articulationPoints: [], bridges: [] };
    
    const disc: Map<number, number> = new Map();
    const low: Map<number, number> = new Map();
    const parent: Map<number, number | null> = new Map();
    const articulationPoints: Set<number> = new Set();
    const bridges: [number, number][] = [];
    let timer = 0;
    
    for (const startVertex of graph.keys()) {
        if (disc.has(startVertex)) continue;
        
        const stack: StackFrame[] = [];
        parent.set(startVertex, null);
        
        // Initialize start vertex
        disc.set(startVertex, timer);
        low.set(startVertex, timer);
        timer++;
        stack.push({ vertex: startVertex, neighborIndex: 0, childCount: 0 });
        
        while (stack.length > 0) {
            const frame = stack[stack.length - 1];
            const vertex = frame.vertex;
            const neighbors = graph.get(vertex) || [];
            
            if (frame.neighborIndex < neighbors.length) {
                const neighbor = neighbors[frame.neighborIndex];
                frame.neighborIndex++;
                
                // Skip self-loops
                if (neighbor === vertex) continue;
                
                if (!disc.has(neighbor)) {
                    // Tree edge: push new frame
                    frame.childCount++;
                    parent.set(neighbor, vertex);
                    
                    disc.set(neighbor, timer);
                    low.set(neighbor, timer);
                    timer++;
                    
                    stack.push({ 
                        vertex: neighbor, 
                        neighborIndex: 0, 
                        childCount: 0 
                    });
                } else if (neighbor !== parent.get(vertex)) {
                    // Back edge
                    low.set(vertex, Math.min(
                        low.get(vertex)!, 
                        disc.get(neighbor)!
                    ));
                }
            } else {
                // Finished processing vertex, pop and update parent
                stack.pop();
                
                if (stack.length > 0) {
                    const parentFrame = stack[stack.length - 1];
                    const parentVertex = parentFrame.vertex;
                    
                    // Update parent's low value
                    low.set(parentVertex, Math.min(
                        low.get(parentVertex)!, 
                        low.get(vertex)!
                    ));
                    
                    // Articulation point check (non-root)
                    if (low.get(vertex)! >= disc.get(parentVertex)!) {
                        articulationPoints.add(parentVertex);
                    }
                    
                    // Bridge check
                    if (low.get(vertex)! > disc.get(parentVertex)!) {
                        bridges.push([parentVertex, vertex]);
                    }
                } else {
                    // Root check
                    if (frame.childCount >= 2) {
                        articulationPoints.add(vertex);
                    }
                }
            }
        }
    }
    
    return {
        articulationPoints: Array.from(articulationPoints),
        bridges: bridges,
    };
}

When to Use Iterative

Use iterative implementation when: (1) Graph depth may exceed recursion limit (typically thousands), (2) Language has expensive function call overhead, (3) You need explicit control over stack memory. For most practical purposes, recursion is cleaner.

Common Implementation Bugs

Even experienced programmers make mistakes implementing this algorithm. Here are the most common bugs and how to avoid them.

Common Bugs and Fixes

•Forgetting the parent check in back edges: Treating the tree edge to parent as a back edge corrupts low values. Always check neighbor !== parent[vertex].
•Using low[ancestor] instead of disc[ancestor] for back edges: This can cause incorrect bridge detection. Use disc[neighbor] in the min update.
•Not handling the root case separately: The normal low check always passes for root (disc=0). Add explicit root child count check.
•Incorrect inequality for bridges vs articulation points: Bridges use > (strictly greater); articulation points use >= (greater or equal). Mixing these up causes wrong results.
•Not handling disconnected graphs: If graph has multiple components, must run DFS from all unvisited vertices, not just one.
•Adding articulation points multiple times: A vertex might satisfy the condition for multiple children. Use a Set to avoid duplicates.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// BUG 1: Missing parent check
// WRONG:
for (const neighbor of graph.get(vertex)!) {
    if (disc.has(neighbor)) {
        low[vertex] = Math.min(low[vertex], disc[neighbor]);
    }
    // This updates low even for parent, corrupting values!
}
 
// CORRECT:
for (const neighbor of graph.get(vertex)!) {
    if (disc.has(neighbor) && neighbor !== parent[vertex]) {
        low[vertex] = Math.min(low[vertex], disc[neighbor]);
    }
}
 
// BUG 2: Wrong low update 
// WRONG (using low for back edge):
low[vertex] = Math.min(low[vertex], low[neighbor]);
 
// CORRECT (using disc for back edge):
low[vertex] = Math.min(low[vertex], disc[neighbor]);
 
// BUG 3: Wrong inequality
// WRONG (using > for articulation points):
if (low[neighbor] > disc[vertex]) articulationPoints.add(vertex);
 
// CORRECT (using >= for articulation points):
if (low[neighbor] >= disc[vertex]) articulationPoints.add(vertex);

Testing Strategy

Test your implementation on: (1) A simple tree (all edges are bridges), (2) A single cycle (no bridges, no articulation points), (3) Two cycles connected by one edge (one bridge), (4) A disconnected graph, (5) A star graph (center is articulation point). Verify against the naive O(V²) algorithm on small inputs.

Summary: The Complete Detection Algorithm

We've covered Tarjan's algorithm in full detail. Let's consolidate the essential points.

Key Takeaways

•Single DFS traversal suffices — Track disc times and low values to identify critical elements without repeated graph traversals.
•Low value captures reachability — low[v] = minimum disc time reachable from v's subtree via tree edges and one back edge.
•Articulation point condition — Non-root: has child u with low[u] ≥ disc[v]. Root: has ≥2 DFS children.
•Bridge condition — Tree edge (u,v) where low[v] > disc[u] (strictly greater, not ≥).
•Use disc (not low) for back edges — Back edge updates should use the ancestor's discovery time.
•Time complexity is optimal O(V + E) — Cannot do better since we must examine the entire graph.

What's next:

The final page explores the practical applications of articulation point and bridge detection: network reliability analysis, infrastructure planning, social network analysis, and more. You'll see how this elegant algorithm solves real-world problems.

Page Complete

You now fully understand Tarjan's algorithm for finding articulation points and bridges. You can implement it from scratch, handle edge cases, analyze its complexity, and debug common issues. Next, we'll apply this to real-world network reliability problems.

3 / 4

Loading learning content...

Data Structures & AlgorithmsArticulation Points & Bridges

Articulation Points & Bridges

LevelAdvanced

Duration90 mins

TopicArticulation Points & Bridges

3 / 4

Finding Articulation Points and Bridges with DFS

The Elegant Algorithm of Robert Tarjan

What You Will Master

Algorithm Overview: The Key Concepts

Before diving into code, let's establish the conceptual framework. The algorithm relies on three key ideas:

1. DFS Tree Structure

When we perform DFS on a connected undirected graph, we implicitly construct a spanning tree (the DFS tree) where:

Every vertex is visited exactly once
Edges used to discover new vertices become tree edges
Remaining edges connect descendants to ancestors (back edges)

2. Discovery Time (disc)

We assign each vertex a timestamp when DFS first visits it. This creates a linear ordering of vertices that reflects the DFS traversal order:

disc[v] = the step number when v is first visited

3. Low-Link Value (low)

For each vertex, we compute the earliest (lowest) discovery time reachable from its subtree:

low[v] = minimum of:
  - disc[v] (can reach itself)
  - low[u] for all children u in DFS tree (reaches of descendants)
  - disc[w] for all back edges (v, w) (direct reach to ancestors)

Low Value Intuition

Detection Conditions Summary
Element	Condition	Intuition
Articulation Point (non-root)	Has child u where low[u] ≥ disc[v]	Child's subtree can't escape above v
Articulation Point (root)	Has ≥ 2 children in DFS tree	Removing root separates children
Bridge (u→v tree edge)	low[v] > disc[u]	Child's subtree can't even reach u

Why the difference between ≥ and > ?

For articulation points: If low[u] = disc[v], the subtree can reach v itself (via a back edge to v), but not above. Removing v still disconnects the subtree from everything above v.

For bridges: If low[v] = disc[u], there's a back edge from v's subtree to u, creating a cycle that includes edge (u,v). The edge is not a bridge because the cycle provides an alternative path.

Complete Algorithm Implementation

Here's the complete, production-ready implementation that finds both articulation points and bridges in a single DFS traversal.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
interface ArticulationBridgeResult {
    articulationPoints: number[];
    bridges: [number, number][];
}
 
/**
 * Finds all articulation points and bridges in an undirected graph.
 * Uses Tarjan's algorithm with O(V + E) time complexity.
 * 
 * @param graph - Adjacency list representation (vertex -> neighbors)
 * @returns Object containing arrays of articulation points and bridges
 */
function findCriticalElements(
    graph: Map<number, number[]>
): ArticulationBridgeResult {
    const n = graph.size;
    if (n === 0) return { articulationPoints: [], bridges: [] };
    
    // Track discovery time and low values
    const disc: Map<number, number> = new Map();
    const low: Map<number, number> = new Map();
    
    // Track parent for each vertex in DFS tree
    const parent: Map<number, number | null> = new Map();
    
    // Results
    const articulationPoints: Set<number> = new Set();
    const bridges: [number, number][] = [];
    
    // Timer for discovery times
    let timer = 0;
    
    /**
     * DFS function that computes disc and low values
     * while identifying articulation points and bridges.
     */
    function dfs(vertex: number): void {
        // Initialize discovery time and low value
        disc.set(vertex, timer);
        low.set(vertex, timer);
        timer++;
        
        // Count children in DFS tree (for root check)
        let childCount = 0;
        
        for (const neighbor of (graph.get(vertex) || [])) {
            if (!disc.has(neighbor)) {
                // Unvisited vertex: tree edge
                childCount++;
                parent.set(neighbor, vertex);
                
                // Recurse on child
                dfs(neighbor);
                
                // After DFS returns, update low value
                low.set(vertex, Math.min(low.get(vertex)!, low.get(neighbor)!));
                
                // Check for articulation point (non-root case)
                // If child can't reach above this vertex, this vertex is critical
                if (parent.get(vertex) !== null && 
                    low.get(neighbor)! >= disc.get(vertex)!) {
                    articulationPoints.add(vertex);
                }
                
                // Check for bridge
                // If child can't reach this vertex or above, edge is a bridge
                if (low.get(neighbor)! > disc.get(vertex)!) {
                    bridges.push([vertex, neighbor]);
                }
            } else if (neighbor !== parent.get(vertex)) {
                // Already visited and not parent: back edge
                // Update low value with neighbor's discovery time
                low.set(vertex, Math.min(low.get(vertex)!, disc.get(neighbor)!));
            }
            // If neighbor is parent, we ignore (not a back edge)
        }
        
        // Check for articulation point (root case)
        // Root is an articulation point iff it has ≥ 2 children
        if (parent.get(vertex) === null && childCount >= 2) {
            articulationPoints.add(vertex);
        }
    }
    
    // Handle disconnected graphs by running DFS from all unvisited vertices
    for (const vertex of graph.keys()) {
        if (!disc.has(vertex)) {
            parent.set(vertex, null);  // Mark as root of DFS tree
            dfs(vertex);
        }
    }
    
    return {
        articulationPoints: Array.from(articulationPoints),
        bridges: bridges,
    };
}

Critical Detail: Parent Check

Step-by-Step Algorithm Trace

Let's trace through the algorithm on a concrete example to solidify understanding.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Graph Structure:
 
    0 ─── 1 ─── 2
          │ \   │
          │  \  │
          3 ──── 4
          
Adjacency List:
  0: [1]
  1: [0, 2, 3, 4]
  2: [1, 4]
  3: [1, 4]
  4: [1, 2, 3]
 
Starting DFS from vertex 0...

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
STEP 1: dfs(0)
  Visit 0: disc[0] = 0, low[0] = 0, parent[0] = null
  Neighbors of 0: [1]
  
  STEP 2: Process neighbor 1 (unvisited → tree edge)
    childCount for 0 = 1
    parent[1] = 0
    
    STEP 3: dfs(1)
      Visit 1: disc[1] = 1, low[1] = 1, parent[1] = 0
      Neighbors of 1: [0, 2, 3, 4]
      
      Process neighbor 0: visited AND is parent → skip
      
      STEP 4: Process neighbor 2 (unvisited → tree edge)
        childCount for 1 = 1
        parent[2] = 1
        
        STEP 5: dfs(2)
          Visit 2: disc[2] = 2, low[2] = 2, parent[2] = 1
          Neighbors of 2: [1, 4]
          
          Process neighbor 1: visited AND is parent → skip
          
          STEP 6: Process neighbor 4 (unvisited → tree edge)
            childCount for 2 = 1
            parent[4] = 2
            
            STEP 7: dfs(4)
              Visit 4: disc[4] = 3, low[4] = 3, parent[4] = 2
              Neighbors of 4: [1, 2, 3]
              
              Process neighbor 1: visited, not parent (1 ≠ 2)
                → Back edge! low[4] = min(3, disc[1]) = min(3, 1) = 1
              
              Process neighbor 2: visited AND is parent → skip
              
              STEP 8: Process neighbor 3 (unvisited → tree edge)
                childCount for 4 = 1
                parent[3] = 4
                
                STEP 9: dfs(3)
                  Visit 3: disc[3] = 4, low[3] = 4, parent[3] = 4
                  Neighbors of 3: [1, 4]
                  
                  Process neighbor 1: visited, not parent
                    → Back edge! low[3] = min(4, disc[1]) = min(4, 1) = 1
                  
                  Process neighbor 4: visited AND is parent → skip
                  
                  childCount for 3 = 0 (no tree children)
                  parent[3] = 4 ≠ null, not root
                  No articulation point check for root applies
                  
                  Return from dfs(3)
                
                Back in dfs(4):
                Update low[4] = min(low[4], low[3]) = min(1, 1) = 1
                
                Articulation point check: parent[4] = 2 ≠ null
                  low[3] = 1 ≥ disc[4] = 3? NO (1 < 3)
                  → 4 is NOT an articulation point (based on child 3)
                
                Bridge check: low[3] = 1 > disc[4] = 3? NO
                  → (4,3) is NOT a bridge
              
              childCount for 4 = 1
              parent[4] = 2 ≠ null, not root
              
              Return from dfs(4)
            
            Back in dfs(2):
            Update low[2] = min(low[2], low[4]) = min(2, 1) = 1
            
            Articulation point check:
              low[4] = 1 ≥ disc[2] = 2? NO
              → 2 is NOT an articulation point
            
            Bridge check: low[4] = 1 > disc[2] = 2? NO
              → (2,4) is NOT a bridge
          
          childCount for 2 = 1
          Return from dfs(2)
        
        Back in dfs(1):
        Update low[1] = min(low[1], low[2]) = min(1, 1) = 1
        
        Articulation point check:
          low[2] = 1 ≥ disc[1] = 1? YES!
          → 1 IS an articulation point!
        
        Bridge check: low[2] = 1 > disc[1] = 1? NO
          → (1,2) is NOT a bridge
      
      STEP 10: Process neighbor 3 in dfs(1)
        3 is already visited (disc[3] = 4), not parent (parent[1] = 0)
        → Back edge! low[1] = min(1, disc[3]) = min(1, 4) = 1
      
      STEP 11: Process neighbor 4 in dfs(1)  
        4 is already visited, not parent
        → Back edge! low[1] = min(1, disc[4]) = min(1, 3) = 1
      
      childCount for 1 = 1 (only 2 was a tree child)
      parent[1] = 0 ≠ null, not root
      
      Return from dfs(1)
    
    Back in dfs(0):
    Update low[0] = min(low[0], low[1]) = min(0, 1) = 0
    
    Articulation point check:
      low[1] = 1 ≥ disc[0] = 0? YES!
      → 0 IS an articulation point!
    
    Bridge check: low[1] = 1 > disc[0] = 0? YES!
      → (0,1) IS a bridge!
  
  childCount for 0 = 1
  parent[0] = null, is root
  Root articulation point check: childCount = 1 ≥ 2? NO
  
  Return from dfs(0)
 
FINAL VALUES:
  Vertex | disc | low | parent
  -------|------|-----|-------
    0    |  0   |  0  |  null
    1    |  1   |  1  |   0
    2    |  2   |  1  |   1
    3    |  4   |  1  |   4
    4    |  3   |  1  |   2
 
RESULTS:
  Articulation Points: {1} 
  (0 was added but let's verify - wait, we added 0 above!)
  
Let me re-check: In step when we processed (0,1) tree edge...
  parent[0] = null, but we checked parent.get(vertex) !== null
  for the articulation check. So 0 was NOT added via non-root path.
  
  For root check: childCount = 1, not ≥ 2, so 0 NOT added.
  
  Articulation Points: {1}
  Bridges: {(0,1)}

Verification

Edge Cases and Corner Cases

Production implementations must handle various edge cases correctly. Let's examine each.

Edge Cases to Handle

•Empty graph: No vertices → no articulation points or bridges. Return empty results.
•Single vertex: One vertex, no edges → no articulation points, no bridges.
•Two vertices, one edge: The edge is a bridge. Neither vertex is an articulation point (each is a leaf relative to the other).
•Disconnected graph: Must run DFS from all unvisited vertices. Each component analyzed independently.
•Self-loops: Edge (v,v) → not a bridge (removing it doesn't disconnect anything). Implementation should handle gracefully.
•Multiple edges (multigraph): Multiple edges between same vertices → typically none are bridges (parallels provide redundancy).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
function findCriticalElementsRobust(
    graph: Map<number, number[]>
): ArticulationBridgeResult {
    // Edge case: empty graph
    if (graph.size === 0) {
        return { articulationPoints: [], bridges: [] };
    }
    
    // Edge case: single vertex
    if (graph.size === 1) {
        return { articulationPoints: [], bridges: [] };
    }
    
    const disc: Map<number, number> = new Map();
    const low: Map<number, number> = new Map();
    const parent: Map<number, number | null> = new Map();
    const articulationPoints: Set<number> = new Set();
    const bridges: [number, number][] = [];
    let timer = 0;
    
    function dfs(vertex: number): void {
        disc.set(vertex, timer);
        low.set(vertex, timer);
        timer++;
        
        let childCount = 0;
        
        for (const neighbor of (graph.get(vertex) || [])) {
            // Edge case: self-loop (skip)
            if (neighbor === vertex) continue;
            
            if (!disc.has(neighbor)) {
                childCount++;
                parent.set(neighbor, vertex);
                dfs(neighbor);
                
                low.set(vertex, Math.min(
                    low.get(vertex)!, 
                    low.get(neighbor)!
                ));
                
                // Articulation point check (non-root)
                if (parent.get(vertex) !== null && 
                    low.get(neighbor)! >= disc.get(vertex)!) {
                    articulationPoints.add(vertex);
                }
                
                // Bridge check
                if (low.get(neighbor)! > disc.get(vertex)!) {
                    bridges.push([vertex, neighbor]);
                }
            } else if (neighbor !== parent.get(vertex)) {
                // Back edge
                low.set(vertex, Math.min(
                    low.get(vertex)!, 
                    disc.get(neighbor)!
                ));
            }
        }
        
        // Root articulation point check
        if (parent.get(vertex) === null && childCount >= 2) {
            articulationPoints.add(vertex);
        }
    }
    
    // Handle disconnected graphs
    for (const vertex of graph.keys()) {
        if (!disc.has(vertex)) {
            parent.set(vertex, null);
            dfs(vertex);
        }
    }
    
    return {
        articulationPoints: Array.from(articulationPoints),
        bridges: bridges,
    };
}

Multigraph Consideration

The Root Special Case: Deep Explanation

The root of the DFS tree requires special handling for articulation point detection. Understanding why reveals important insights about the algorithm's design.

Why the normal condition fails for the root:

The normal articulation point condition is: vertex v is an articulation point if it has a child u with low[u] ≥ disc[v].

For the root r with disc[r] = 0:

ANY vertex u in the graph has low[u] ≥ 0 (low values are non-negative)
So the condition low[u] ≥ disc[r] = 0 is ALWAYS true!
This would incorrectly mark the root as an articulation point in every graph.

The correct interpretation:

The intuition behind low[u] ≥ disc[v] is: 'No back edges escape u's subtree to above v.'

But for the root, there IS no 'above.' The root has no ancestors. So we need a different criterion: does removing the root disconnect its children from each other?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
CASE 1: Root with 1 DFS child
═══════════════════════════════
 
    1 (root)          If we remove 1:
    │                 The remaining graph is {2,3,4,5}
    2                 Still connected!
   / \                → 1 is NOT an articulation point
  3   4
  │
  5
 
Only 2 is a DFS child of 1 (3,4,5 are descendants but not direct children).
 
 
CASE 2: Root with ≥2 DFS children  
════════════════════════════════════
 
    1 (root)          If we remove 1:
   / \                {2,3} and {4,5} become disconnected!
  2   4               → 1 IS an articulation point
  │   │
  3   5
 
Both 2 and 4 are DFS children of 1.
Removing 1 disconnects their subtrees.
 
 
CASE 3: Root with multiple neighbors but 1 DFS child
═══════════════════════════════════════════════════════
 
    1 (root)          DFS from 1 might go: 1→2→3→4→1(back)→5→1(back)  
   /│\                Only 2 is a tree child! (3,4 via 2; 5 has back edge)
  2 4 5──┐            
  │ │    │            Actually wait, let me redo:
  3─┘    │            DFS: 1→2→3→4(back to 1 or 2?)→5
         │            
If there are edges 1-2, 2-3, 3-4, 4-1, 1-5:
 
Tree edges from 1: to 2, and to 5 (if 5 visited after 4's back edge)
That's 2 DFS children → 1 IS articulation point.
 
Key insight: DFS children ≠ neighbors. It depends on discovery order.

Root Choice Doesn't Matter

Alternative Low-Link Formulations

Different textbooks and implementations define the low value slightly differently. Understanding these variations prevents confusion when comparing implementations.

Low Value Definition Variants
Variant	Definition	Back Edge Update
Standard (disc)	min reachable disc time	low[v] = min(low[v], disc[ancestor])
Alternative (low)	min reachable low time	low[v] = min(low[v], low[ancestor])

Important subtlety for bridges:

With the standard definition (using disc[ancestor] for back edges), the bridge condition low[v] > disc[u] works correctly.

With the alternative definition (using low[ancestor]), we must be more careful. Consider:

Vertex x has disc[x] = 1, low[x] = 0 (due to back edge to disc=0)
Vertex y discovered after x, has back edge to x

With alternative definition: low[y] could become 0 (taking low[x]) With standard definition: low[y] becomes 1 (taking disc[x])

For bridges, the standard definition is typically preferred for correctness.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// STANDARD FORMULATION (Recommended for bridges)
// Back edge update uses discovery time
if (neighbor !== parent.get(vertex)) {
    low.set(vertex, Math.min(
        low.get(vertex)!, 
        disc.get(neighbor)!  // Use disc, not low
    ));
}
 
// Bridge check: works correctly
if (low.get(neighbor)! > disc.get(vertex)!) {
    bridges.push([vertex, neighbor]);
}
 
// ─────────────────────────────────────────────
 
// ALTERNATIVE FORMULATION (Some implementations)
// Back edge update uses low value
if (neighbor !== parent.get(vertex)) {
    low.set(vertex, Math.min(
        low.get(vertex)!, 
        low.get(neighbor)!  // Use low instead
    ));
}
 
// Bridge check: may need adjustment for correctness
// The condition low[v] > disc[u] may incorrectly identify
// some non-bridges as bridges in specific graph configurations.

Best Practice

Complexity Analysis

Let's rigorously analyze the time and space complexity of Tarjan's algorithm.

Time Complexity: O(V + E)

•DFS visits each vertex exactly once: O(V) total vertex visits.
•Each edge examined exactly twice: Once from each endpoint, contributing O(E) to neighbor processing.
•Update operations are O(1): Setting disc, low, checking conditions are constant time.
•No nested loops over graph structure: Single pass through adjacency lists.
•Total: O(V + E), which is optimal (we must read the entire graph at minimum).

Space Complexity: O(V)

•Discovery times: O(V) for disc array/map.
•Low values: O(V) for low array/map.
•Parent tracking: O(V) for parent array/map.
•Recursion stack: O(V) in worst case (path graph).
•Result storage: O(V) for articulation points, O(E) for bridges in worst case.

Complexity Comparison with Naive Approach
Aspect	Naive Approach	Tarjan's Algorithm
Time Complexity	O(V × (V + E))	O(V + E)
Space Complexity	O(V + E)	O(V)
of DFS Traversals	V (one per vertex test)	1
For \|V\|=1000, \|E\|=5000	~6 million ops	~6 thousand ops
For \|V\|=1M, \|E\|=10M	~10¹³ ops (years)	~10⁷ ops (seconds)

Why O(V + E) is Optimal

Iterative Implementation (Stack-Based)

The recursive implementation may cause stack overflow on very deep graphs. Here's an iterative version using explicit stack management.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
interface StackFrame {
    vertex: number;
    neighborIndex: number;  // Which neighbor are we processing?
    childCount: number;     // DFS tree children count
}
 
function findCriticalElementsIterative(
    graph: Map<number, number[]>
): ArticulationBridgeResult {
    if (graph.size === 0) return { articulationPoints: [], bridges: [] };
    
    const disc: Map<number, number> = new Map();
    const low: Map<number, number> = new Map();
    const parent: Map<number, number | null> = new Map();
    const articulationPoints: Set<number> = new Set();
    const bridges: [number, number][] = [];
    let timer = 0;
    
    for (const startVertex of graph.keys()) {
        if (disc.has(startVertex)) continue;
        
        const stack: StackFrame[] = [];
        parent.set(startVertex, null);
        
        // Initialize start vertex
        disc.set(startVertex, timer);
        low.set(startVertex, timer);
        timer++;
        stack.push({ vertex: startVertex, neighborIndex: 0, childCount: 0 });
        
        while (stack.length > 0) {
            const frame = stack[stack.length - 1];
            const vertex = frame.vertex;
            const neighbors = graph.get(vertex) || [];
            
            if (frame.neighborIndex < neighbors.length) {
                const neighbor = neighbors[frame.neighborIndex];
                frame.neighborIndex++;
                
                // Skip self-loops
                if (neighbor === vertex) continue;
                
                if (!disc.has(neighbor)) {
                    // Tree edge: push new frame
                    frame.childCount++;
                    parent.set(neighbor, vertex);
                    
                    disc.set(neighbor, timer);
                    low.set(neighbor, timer);
                    timer++;
                    
                    stack.push({ 
                        vertex: neighbor, 
                        neighborIndex: 0, 
                        childCount: 0 
                    });
                } else if (neighbor !== parent.get(vertex)) {
                    // Back edge
                    low.set(vertex, Math.min(
                        low.get(vertex)!, 
                        disc.get(neighbor)!
                    ));
                }
            } else {
                // Finished processing vertex, pop and update parent
                stack.pop();
                
                if (stack.length > 0) {
                    const parentFrame = stack[stack.length - 1];
                    const parentVertex = parentFrame.vertex;
                    
                    // Update parent's low value
                    low.set(parentVertex, Math.min(
                        low.get(parentVertex)!, 
                        low.get(vertex)!
                    ));
                    
                    // Articulation point check (non-root)
                    if (low.get(vertex)! >= disc.get(parentVertex)!) {
                        articulationPoints.add(parentVertex);
                    }
                    
                    // Bridge check
                    if (low.get(vertex)! > disc.get(parentVertex)!) {
                        bridges.push([parentVertex, vertex]);
                    }
                } else {
                    // Root check
                    if (frame.childCount >= 2) {
                        articulationPoints.add(vertex);
                    }
                }
            }
        }
    }
    
    return {
        articulationPoints: Array.from(articulationPoints),
        bridges: bridges,
    };
}

When to Use Iterative

Common Implementation Bugs

Even experienced programmers make mistakes implementing this algorithm. Here are the most common bugs and how to avoid them.

Common Bugs and Fixes

•Forgetting the parent check in back edges: Treating the tree edge to parent as a back edge corrupts low values. Always check neighbor !== parent[vertex].
•Using low[ancestor] instead of disc[ancestor] for back edges: This can cause incorrect bridge detection. Use disc[neighbor] in the min update.
•Not handling the root case separately: The normal low check always passes for root (disc=0). Add explicit root child count check.
•Incorrect inequality for bridges vs articulation points: Bridges use > (strictly greater); articulation points use >= (greater or equal). Mixing these up causes wrong results.
•Not handling disconnected graphs: If graph has multiple components, must run DFS from all unvisited vertices, not just one.
•Adding articulation points multiple times: A vertex might satisfy the condition for multiple children. Use a Set to avoid duplicates.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// BUG 1: Missing parent check
// WRONG:
for (const neighbor of graph.get(vertex)!) {
    if (disc.has(neighbor)) {
        low[vertex] = Math.min(low[vertex], disc[neighbor]);
    }
    // This updates low even for parent, corrupting values!
}
 
// CORRECT:
for (const neighbor of graph.get(vertex)!) {
    if (disc.has(neighbor) && neighbor !== parent[vertex]) {
        low[vertex] = Math.min(low[vertex], disc[neighbor]);
    }
}
 
// BUG 2: Wrong low update 
// WRONG (using low for back edge):
low[vertex] = Math.min(low[vertex], low[neighbor]);
 
// CORRECT (using disc for back edge):
low[vertex] = Math.min(low[vertex], disc[neighbor]);
 
// BUG 3: Wrong inequality
// WRONG (using > for articulation points):
if (low[neighbor] > disc[vertex]) articulationPoints.add(vertex);
 
// CORRECT (using >= for articulation points):
if (low[neighbor] >= disc[vertex]) articulationPoints.add(vertex);

Testing Strategy

Summary: The Complete Detection Algorithm

We've covered Tarjan's algorithm in full detail. Let's consolidate the essential points.

Key Takeaways

•Single DFS traversal suffices — Track disc times and low values to identify critical elements without repeated graph traversals.
•Low value captures reachability — low[v] = minimum disc time reachable from v's subtree via tree edges and one back edge.
•Articulation point condition — Non-root: has child u with low[u] ≥ disc[v]. Root: has ≥2 DFS children.
•Bridge condition — Tree edge (u,v) where low[v] > disc[u] (strictly greater, not ≥).
•Use disc (not low) for back edges — Back edge updates should use the ancestor's discovery time.
•Time complexity is optimal O(V + E) — Cannot do better since we must examine the entire graph.

What's next:

Page Complete

3 / 4

Articulation Points & Bridges

Finding Articulation Points and Bridges with DFS

of DFS Traversals

Articulation Points & Bridges

Finding Articulation Points and Bridges with DFS

of DFS Traversals