Bridges in Graph Tarjan's Algorithm in DSA Python

Mental Model

A bridge is an edge that, if removed, splits the graph into more pieces. Tarjan's algorithm finds these by exploring nodes deeply and tracking the earliest reachable node from each subtree.

Analogy: Imagine a network of islands connected by bridges. Some bridges are the only way to reach certain islands. If you remove such a bridge, the islands get separated. Tarjan's algorithm helps find these critical bridges by walking through the islands and seeing which bridges are vital.

Graph example:
1 -> 2 -> 3
|    |
4    5

Edges:
1-2, 2-3, 1-4, 2-5
Bridge edges are those which, if removed, disconnect parts.

Initial state:
1 ↑
Nodes: 1,2,3,4,5
Edges: 1-2, 2-3, 1-4, 2-5

Dry Run Walkthrough

Input: Graph with edges: 1-2, 2-3, 1-4, 2-5

Goal: Find all bridges in the graph using Tarjan's algorithm

Step 1: Start DFS at node 1, assign discovery time and low value = 0

Node 1: disc=0, low=0 ↑
Nodes 2,3,4,5: disc=∞, low=∞

Why: We begin exploring from node 1 to assign discovery times and low values.

Step 2: Visit node 2 from node 1, disc=1, low=1

Node 1: disc=0, low=0
Node 2: disc=1, low=1 ↑
Others: disc=∞, low=∞

Why: We explore neighbors of 1; node 2 is next, so assign discovery and low.

Step 3: Visit node 3 from node 2, disc=2, low=2

Node 3: disc=2, low=2 ↑
Node 2: disc=1, low=1
Node 1: disc=0, low=0

Why: Continue DFS deeper to node 3, assign discovery and low.

Step 4: Node 3 has no unvisited neighbors, backtrack to node 2, update low[2] = min(low[2], low[3]) = 1

Node 2: disc=1, low=1 ↑
Node 3: disc=2, low=2
Node 1: disc=0, low=0

Why: Backtracking updates low values to reflect earliest reachable ancestor.

Step 5: Check if edge 2-3 is a bridge: low[3] > disc[2] (2 > 1) -> yes, record bridge (2,3)

Bridge found: (2,3)

Why: If low of child is greater than discovery of parent, edge is a bridge.

Step 6: Visit node 5 from node 2, disc=3, low=3

Node 5: disc=3, low=3 ↑
Node 2: disc=1, low=1
Node 1: disc=0, low=0

Why: Explore another neighbor of 2.

Step 7: Node 5 has no unvisited neighbors, backtrack to node 2, update low[2] = min(low[2], low[5]) = 1

Node 2: disc=1, low=1 ↑
Node 5: disc=3, low=3
Node 1: disc=0, low=0

Why: Backtracking updates low values.

Step 8: Check if edge 2-5 is a bridge: low[5] > disc[2] (3 > 1) -> yes, record bridge (2,5)

Bridge found: (2,5)

Why: Edge 2-5 is a bridge by the same rule.

Step 9: Backtrack to node 1, update low[1] = min(low[1], low[2]) = 0

Node 1: disc=0, low=0 ↑
Node 2: disc=1, low=1

Why: Update low of node 1 after exploring node 2.

Step 10: Visit node 4 from node 1, disc=4, low=4

Node 4: disc=4, low=4 ↑
Node 1: disc=0, low=0

Why: Explore another neighbor of 1.

Step 11: Node 4 has no unvisited neighbors, backtrack to node 1, update low[1] = min(low[1], low[4]) = 0

Node 1: disc=0, low=0 ↑
Node 4: disc=4, low=4

Why: Backtracking updates low values.

Step 12: Check if edge 1-4 is a bridge: low[4] > disc[1] (4 > 0) -> yes, record bridge (1,4)

Bridge found: (1,4)

Why: Edge 1-4 is a bridge.

Result:

Bridges found:
(2,3)
(2,5)
(1,4)

Annotated Code

DSA Python

from collections import defaultdict

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = defaultdict(list)
        self.time = 0

    def add_edge(self, u, v):
        self.graph[u].append(v)
        self.graph[v].append(u)

    def bridge_util(self, u, visited, parent, low, disc, bridges):
        visited[u] = True
        disc[u] = self.time
        low[u] = self.time
        self.time += 1

        for v in self.graph[u]:
            if not visited[v]:
                parent[v] = u
                self.bridge_util(v, visited, parent, low, disc, bridges)  # DFS deeper
                low[u] = min(low[u], low[v])  # Update low[u] after visiting child

                if low[v] > disc[u]:  # Bridge condition
                    bridges.append((u, v))
            elif v != parent[u]:
                low[u] = min(low[u], disc[v])  # Update low[u] for back edge

    def find_bridges(self):
        visited = [False] * (self.V + 1)
        disc = [float('inf')] * (self.V + 1)
        low = [float('inf')] * (self.V + 1)
        parent = [-1] * (self.V + 1)
        bridges = []

        for i in range(1, self.V + 1):
            if not visited[i]:
                self.bridge_util(i, visited, parent, low, disc, bridges)

        for u, v in bridges:
            print(f"({u},{v})")

# Driver code
if __name__ == '__main__':
    g = Graph(5)
    g.add_edge(1, 2)
    g.add_edge(2, 3)
    g.add_edge(1, 4)
    g.add_edge(2, 5)

    g.find_bridges()

visited[u] = True disc[u] = self.time low[u] = self.time self.time += 1

Mark node u as visited and assign discovery and low times.

for v in self.graph[u]:

Explore all neighbors of u.

if not visited[v]: parent[v] = u self.bridge_util(v, visited, parent, low, disc, bridges)

DFS deeper to unvisited neighbor v.

low[u] = min(low[u], low[v])

Update low[u] after visiting child v.

if low[v] > disc[u]: bridges.append((u, v))

If child's low is greater than u's discovery, edge u-v is a bridge.

elif v != parent[u]: low[u] = min(low[u], disc[v])

Update low[u] for back edge to ancestor.

for i in range(1, self.V + 1): if not visited[i]: self.bridge_util(i, visited, parent, low, disc, bridges)

Start DFS from all unvisited nodes to cover disconnected graph.

Output

(2,3)

(2,5)

(1,4)

Complexity Analysis

Time: O(V + E) because each vertex and edge is visited once during DFS

Space: O(V + E) for storing the graph and auxiliary arrays for DFS

vs Alternative: Naive approach checks connectivity after removing each edge, costing O(E*(V+E)), much slower than Tarjan's O(V+E)

Edge Cases

Empty graph (no edges)

No bridges found, algorithm completes without errors

DSA Python

for i in range(1, self.V + 1):
    if not visited[i]:
        self.bridge_util(i, visited, parent, low, disc, bridges)

Graph with a single node

No bridges found, as no edges exist

DSA Python

for i in range(1, self.V + 1):
    if not visited[i]:
        self.bridge_util(i, visited, parent, low, disc, bridges)

Graph with multiple disconnected components

Algorithm runs DFS on each component, finds bridges in all

DSA Python

for i in range(1, self.V + 1):
    if not visited[i]:
        self.bridge_util(i, visited, parent, low, disc, bridges)

When to Use This Pattern

When a problem asks for edges whose removal increases disconnected parts, use Tarjan's bridge-finding algorithm because it efficiently finds critical edges in one DFS pass.

Common Mistakes

Mistake: Not updating low[u] for back edges to ancestors
Fix: Add condition to update low[u] = min(low[u], disc[v]) when v is visited and not parent[u]

Mistake: Checking bridge condition incorrectly as low[v] >= disc[u]
Fix: Use strict greater than: low[v] > disc[u] to identify bridges correctly

Mistake: Not handling disconnected graphs by starting DFS from all nodes
Fix: Run DFS from every unvisited node in find_bridges()

Summary

Finds edges in a graph that, if removed, increase the number of disconnected parts.

Use when you need to identify critical connections in networks or graphs.

The key insight is tracking the earliest reachable ancestor from each node's subtree using discovery and low times.

Practice

1. What is the main purpose of Tarjan's algorithm when finding bridges in a graph?

easy

A. To find the shortest path between two nodes

B. To find edges that, if removed, increase the number of connected components

C. To detect cycles in a graph

D. To count the total number of nodes in the graph

Solution

1. Step 1: Understand the definition of a bridge

   A bridge is an edge that, when removed, increases the number of connected components in a graph.

2. Step 2: Purpose of Tarjan's algorithm for bridges

   Tarjan's algorithm efficiently finds all such edges (bridges) in a graph using DFS and low-link values.

3. Final Answer:

   To find edges that, if removed, increase the number of connected components -> Option B

4. Quick Check:

   Bridges = edges increasing components when removed [OK]

Hint: Bridges disconnect graph if removed [OK]

Common Mistakes:

• Confusing bridges with cycles
• Thinking it finds shortest paths
• Assuming it counts nodes

2. Which of the following is the correct way to initialize the discovery time and low arrays in Tarjan's algorithm in Python?

easy

A. discovery = [-1] * n; low = [-1] * n

B. discovery = [0] * n; low = [0] * n

C. discovery = list(range(n)); low = list(range(n))

D. discovery = None; low = None

Solution

1. Step 1: Understand initialization purpose

   Discovery and low arrays store times; initializing with -1 means unvisited nodes.

2. Step 2: Choose correct initialization

   Using [-1] * n marks all nodes as unvisited initially, which is standard practice.

3. Final Answer:

   discovery = [-1] * n; low = [-1] * n -> Option A

4. Quick Check:

   Unvisited nodes marked with -1 [OK]

Hint: Use -1 to mark unvisited nodes [OK]

Common Mistakes:

• Initializing with zeros (means visited)
• Using range values (incorrect meaning)
• Setting to None (causes errors)

3. What will be the output bridges for the following undirected graph using Tarjan's algorithm?

graph = {0: [1, 2], 1: [0, 2], 2: [0, 1, 3], 3: [2, 4], 4: [3]}

medium

A. []

B. [(0, 1), (1, 2)]

C. [(2, 3), (3, 4)]

D. [(0, 2), (1, 2)]

Solution

1. Step 1: Analyze graph connections

   Nodes 0,1,2 form a triangle (cycle), so no bridges there. Edges (2,3) and (3,4) connect to nodes outside the cycle.

2. Step 2: Identify bridges

   Removing edge (2,3) or (3,4) disconnects the graph, so these are bridges.

3. Final Answer:

   [(2, 3), (3, 4)] -> Option C

4. Quick Check:

   Edges breaking connectivity = bridges [OK]

Hint: Edges outside cycles are likely bridges [OK]

Common Mistakes:

• Marking cycle edges as bridges
• Missing edges connecting components
• Confusing node pairs order

4. Identify the bug in this Tarjan's algorithm snippet for finding bridges:

def dfs(u, parent):
    visited[u] = True
    disc[u] = time
    low[u] = time
    time += 1
    for v in graph[u]:
        if not visited[v]:
            dfs(v, u)
            low[u] = min(low[u], low[v])
            if low[v] > disc[u]:
                bridges.append((u, v))
        elif v != parent:
            low[u] = min(low[u], disc[v])

medium

A. visited array is not updated correctly

B. The condition low[v] > disc[u] should be low[v] >= disc[u]

C. The parent check should be if v == parent, not v != parent

D. time variable is not declared global or passed, causing UnboundLocalError

Solution

1. Step 1: Check variable usage

   The variable 'time' is incremented inside dfs but not declared global or passed, causing an error.

2. Step 2: Understand Python variable scope

   Without 'global time' or passing time as argument, Python treats 'time' as local, causing UnboundLocalError.

3. Final Answer:

   time variable is not declared global or passed, causing UnboundLocalError -> Option D

4. Quick Check:

   Modify time scope to fix error [OK]

Hint: Declare time global or pass as argument [OK]

Common Mistakes:

• Ignoring variable scope errors
• Changing condition operators incorrectly
• Misunderstanding parent node check

5. Given a graph with nodes 0 to 5 and edges:

edges = [(0,1), (1,2), (2,0), (1,3), (3,4), (4,5), (5,3)]

Using Tarjan's algorithm, which edges are bridges?

hard

A. [(1, 3)]

B. [(3, 4), (4, 5), (5, 3)]

C. [(0, 1), (1, 2), (2, 0)]

D. []

Solution

1. Step 1: Analyze graph structure

   Nodes 0,1,2 form a cycle, so edges among them are not bridges. Nodes 3,4,5 form another cycle.

2. Step 2: Identify connecting edges

   Edge (1,3) connects two cycles. Removing it disconnects the graph, so it is a bridge.

3. Final Answer:

   [(1, 3)] -> Option A

4. Quick Check:

   Bridge connects two cycles [OK]

Hint: Bridges connect separate cycles or components [OK]

Common Mistakes:

• Marking cycle edges as bridges
• Including all edges in bridge list
• Ignoring connectivity impact