Articulation Points and Bridges in Graphs

An articulation point (or cut vertex) is a node whose removal disconnects the graph. A bridge (or cut edge) is an edge whose removal disconnects the graph. These concepts identify the critical points of failure in any network.

Understanding articulation points and bridges is essential for network design, infrastructure planning, and analyzing the robustness of any connected system. If a single router failure can split your network in half, that router is an articulation point and you need redundancy.

The Core Insight

Both articulation points and bridges are found using the same DFS-based approach with two arrays:

• disc[u]: The discovery time of node u during DFS. The first node visited gets disc=0, the second gets disc=1, and so on.
• low[u]: The lowest discovery time reachable from the subtree rooted at u, including through back edges.

A bridge is an edge (u, v) where low[v] > disc[u]. This means the subtree rooted at v has no back edge that reaches u or any ancestor of u. Removing the edge (u, v) disconnects v’s subtree.

An articulation point is a node u where low[v] >= disc[u] for some child v in the DFS tree. This means v’s subtree cannot reach any ancestor of 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 children in the DFS tree.

Finding Bridges

def find_bridges(graph, num_nodes):
    """
    Find all bridges in an undirected graph.
    graph: adjacency list (list of lists)
    Returns: list of bridge edges as (u, v) tuples
    """
    disc = [-1] * num_nodes
    low = [-1] * num_nodes
    bridges = []
    timer = [0]

    def dfs(node, parent):
        disc[node] = low[node] = timer[0]
        timer[0] += 1

        for neighbor in graph[node]:
            if disc[neighbor] == -1:
                # Tree edge: recurse
                dfs(neighbor, node)
                low[node] = min(low[node], low[neighbor])

                # Bridge condition: subtree of neighbor
                # cannot reach node or its ancestors
                if low[neighbor] > disc[node]:
                    bridges.append((node, neighbor))
            elif neighbor != parent:
                # Back edge: update low-link
                low[node] = min(low[node], disc[neighbor])

    for i in range(num_nodes):
        if disc[i] == -1:
            dfs(i, -1)

    return bridges

Example

# Graph with two bridges: (1, 3) and (3, 5)
graph = [
    [1, 2],     # 0: connected to 1, 2
    [0, 2, 3],  # 1: connected to 0, 2, 3
    [0, 1],     # 2: connected to 0, 1
    [1, 4, 5],  # 3: connected to 1, 4, 5
    [3, 5],     # 4: connected to 3, 5
    [3, 4]      # 5: connected to 3, 4
]

bridges = find_bridges(graph, 6)
print(bridges)  # [(1, 3)]

Wait, why only one bridge? Let us trace through. Nodes 3, 4, 5 form a triangle, so the edge (3,5) has a bypass through node 4. The edge (1,3) is the only bridge because removing it separates {0,1,2} from {3,4,5}.

Trace of disc and low Arrays

DFS order: 0 -> 1 -> 2 -> (back to 1) -> 3 -> 4 -> 5

Node:  0  1  2  3  4  5
disc:  0  1  2  3  4  5
low:   0  0  0  3  3  3

Edge (1,3): low[3]=3 > disc[1]=1  => BRIDGE
Edge (3,4): low[4]=3, disc[3]=3   => NOT bridge (3 = 3)
Edge (4,5): low[5]=3, disc[4]=4   => NOT bridge

Node 5 reaches back to node 3 through the edge 5-3, so low[5] = disc[3] = 3. Node 4 gets low[4] = min(low[4], low[5]) = 3 through its child. Since low[4] = disc[3] = 3, the edge (3,4) is not a bridge.

Finding Articulation Points

def find_articulation_points(graph, num_nodes):
    """
    Find all articulation points in an undirected graph.
    Returns: set of articulation point node indices
    """
    disc = [-1] * num_nodes
    low = [-1] * num_nodes
    parent = [-1] * num_nodes
    ap = set()
    timer = [0]

    def dfs(node):
        disc[node] = low[node] = timer[0]
        timer[0] += 1
        children = 0

        for neighbor in graph[node]:
            if disc[neighbor] == -1:
                children += 1
                parent[neighbor] = node
                dfs(neighbor)
                low[node] = min(low[node], low[neighbor])

                # Root with 2+ children is an AP
                if parent[node] == -1 and children > 1:
                    ap.add(node)

                # Non-root where child's subtree
                # cannot reach above this node
                if parent[node] != -1 and low[neighbor] >= disc[node]:
                    ap.add(node)

            elif neighbor != parent[node]:
                low[node] = min(low[node], disc[neighbor])

    for i in range(num_nodes):
        if disc[i] == -1:
            dfs(i)

    return ap

Example

# Graph where node 1 and node 3 are articulation points
graph = [
    [1],           # 0
    [0, 2, 3],     # 1 (AP: removing disconnects 0)
    [1],           # 2
    [1, 4, 5],     # 3 (AP: removing disconnects {4,5} from rest)
    [3, 5],        # 4
    [3, 4]         # 5
]

aps = find_articulation_points(graph, 6)
print(aps)  # {1, 3}

Understanding the Root Special Case

The root of the DFS tree is special. For non-root nodes, we check if any child’s subtree is “trapped” below it (low[child] >= disc[node]). But the root has no ancestor, so low[child] >= disc[root] is always true. Instead, we check if the root has two or more children in the DFS tree. If it does, removing the root disconnects those subtrees.

# Root with 1 child: NOT an articulation point
# 0 - 1 - 2 - 3 (path graph, DFS from 0)
# Root 0 has only 1 DFS child (1), so not AP

# Root with 2 children: IS an articulation point
# 1 - 0 - 2 (star graph, DFS from 0)
# Root 0 has 2 DFS children (1, 2), so it IS AP

Handling Parallel Edges

When multiple edges exist between the same pair of nodes, the parent check in the bridge algorithm needs care. Two edges between u and v mean that removing one still leaves the other, so it is not a bridge.

def find_bridges_multi_edge(num_nodes, edge_list):
    """
    Find bridges handling parallel edges.
    Track edge index instead of parent node.
    """
    graph = [[] for _ in range(num_nodes)]
    for idx, (u, v) in enumerate(edge_list):
        graph[u].append((v, idx))
        graph[v].append((u, idx))

    disc = [-1] * num_nodes
    low = [-1] * num_nodes
    bridges = []
    timer = [0]

    def dfs(node, parent_edge_idx):
        disc[node] = low[node] = timer[0]
        timer[0] += 1

        for neighbor, edge_idx in graph[node]:
            if disc[neighbor] == -1:
                dfs(neighbor, edge_idx)
                low[node] = min(low[node], low[neighbor])
                if low[neighbor] > disc[node]:
                    bridges.append(edge_list[edge_idx])
            elif edge_idx != parent_edge_idx:
                low[node] = min(low[node], disc[neighbor])

    for i in range(num_nodes):
        if disc[i] == -1:
            dfs(i, -1)

    return bridges

Iterative Implementation

For large graphs where recursion depth might be an issue:

def find_bridges_iterative(graph, num_nodes):
    """
    Iterative bridge-finding using explicit stack.
    """
    disc = [-1] * num_nodes
    low = [-1] * num_nodes
    bridges = []
    timer = [0]

    for start in range(num_nodes):
        if disc[start] != -1:
            continue

        # Stack: (node, parent, neighbor_index)
        stack = [(start, -1, 0)]
        disc[start] = low[start] = timer[0]
        timer[0] += 1

        while stack:
            node, parent, idx = stack[-1]

            if idx < len(graph[node]):
                stack[-1] = (node, parent, idx + 1)
                neighbor = graph[node][idx]

                if disc[neighbor] == -1:
                    disc[neighbor] = low[neighbor] = timer[0]
                    timer[0] += 1
                    stack.append((neighbor, node, 0))
                elif neighbor != parent:
                    low[node] = min(low[node], disc[neighbor])
            else:
                stack.pop()
                if stack:
                    parent_node = stack[-1][0]
                    low[parent_node] = min(low[parent_node], low[node])
                    if low[node] > disc[parent_node]:
                        bridges.append((parent_node, node))

    return bridges

Biconnected Components

A biconnected component is a maximal subgraph with no articulation point. Finding biconnected components extends the bridge-finding algorithm by maintaining a stack of edges.

def find_biconnected_components(graph, num_nodes):
    """
    Find all biconnected components of an undirected graph.
    Returns: list of components, each a list of edges.
    """
    disc = [-1] * num_nodes
    low = [-1] * num_nodes
    parent = [-1] * num_nodes
    edge_stack = []
    components = []
    timer = [0]

    def dfs(node):
        disc[node] = low[node] = timer[0]
        timer[0] += 1
        children = 0

        for neighbor in graph[node]:
            if disc[neighbor] == -1:
                children += 1
                parent[neighbor] = node
                edge_stack.append((node, neighbor))
                dfs(neighbor)
                low[node] = min(low[node], low[neighbor])

                # Check if node is AP or root with 2+ children
                is_root_ap = parent[node] == -1 and children > 1
                is_non_root_ap = parent[node] != -1 and low[neighbor] >= disc[node]

                if is_root_ap or is_non_root_ap:
                    component = []
                    while edge_stack[-1] != (node, neighbor):
                        component.append(edge_stack.pop())
                    component.append(edge_stack.pop())
                    components.append(component)

            elif neighbor != parent[node] and disc[neighbor] < disc[node]:
                edge_stack.append((node, neighbor))
                low[node] = min(low[node], disc[neighbor])

    for i in range(num_nodes):
        if disc[i] == -1:
            dfs(i)
            if edge_stack:
                components.append(list(edge_stack))
                edge_stack.clear()

    return components

Real-World Applications

Network Reliability

def analyze_network_reliability(network, num_servers):
    """
    Analyze a network for single points of failure.
    """
    bridges = find_bridges(network, num_servers)
    aps = find_articulation_points(network, num_servers)

    print(f"Critical links (bridges): {len(bridges)}")
    for u, v in bridges:
        print(f"  Link {u} <-> {v}: failure disconnects network")

    print(f"\nCritical servers (articulation points): {len(aps)}")
    for ap in aps:
        connections = len(network[ap])
        print(f"  Server {ap}: {connections} connections, "
              f"failure disconnects network")

    reliability = 1.0 - (len(aps) / num_servers)
    print(f"\nNetwork reliability score: {reliability:.2%}")
    if bridges:
        print("RECOMMENDATION: Add redundant links for bridges")
    if aps:
        print("RECOMMENDATION: Add redundant paths around APs")

Finding Critical Connections (LeetCode 1192)

def critical_connections(n, connections):
    """
    LeetCode 1192: Find all critical connections (bridges).
    connections: list of [u, v] edges
    """
    graph = [[] for _ in range(n)]
    for u, v in connections:
        graph[u].append(v)
        graph[v].append(u)

    return find_bridges(graph, n)


# Example
result = critical_connections(4, [[0,1],[1,2],[2,0],[1,3]])
print(result)  # [(1, 3)]

Complexity Summary

Operation	Time	Space
Find all bridges	O(V + E)	O(V)
Find all articulation points	O(V + E)	O(V)
Biconnected components	O(V + E)	O(V + E)

All algorithms are based on a single DFS pass, making them optimal for these problems.

Common Mistakes

1. Forgetting the root special case for articulation points. The root is an AP only if it has 2 or more DFS children.

2. Using parent node instead of parent edge when handling parallel edges. If there are two edges between A and B, checking neighbor != parent incorrectly treats one of them as a back edge.

3. Confusing bridge condition with AP condition. Bridge: low[v] > disc[u] (strict). AP: low[v] >= disc[u] (non-strict). The difference matters.

4. Not handling disconnected graphs. Always loop over all nodes and start DFS from unvisited ones.

Practice Problems

1. Critical Connections in a Network (LeetCode 1192) - Direct bridge finding
2. Biconnected Components (various judges) - Extension of AP finding
3. Network Redundancy Analysis - Competitive programming variant
4. Block-Cut Tree Construction - Advanced data structure using APs
5. 2-Edge-Connected Components - Bridge-based decomposition

Key Takeaways

Articulation points and bridges identify the structural weak points of a graph. Removing an articulation point or a bridge disconnects the graph. Both are found with a single DFS pass using discovery times (disc) and low-link values (low). The bridge condition is strict inequality (low[v] > disc[u]), while the AP condition uses non-strict inequality (low[v] >= disc[u]) plus a special case for the DFS root. These algorithms run in O(V + E) time and are essential for network reliability analysis.