Bridges in Graph Tarjan's Algorithm in DSA Python - Execution Trace

Concept Flow - Bridges in Graph Tarjan's Algorithm

Start DFS from a node

↓

Assign discovery time & low value

↓

For each neighbor

↓

If not visited

↓

DFS on neighbor

↓

Update low of current

↓

Check if low[neighbor

↓

If yes, record bridge

↓

If visited and not parent

↓

Update low of current

↓

Repeat for all nodes

↓

Output all bridges found

The algorithm runs DFS, assigns discovery and low times, updates low values using neighbors, and identifies edges where low[neighbor] > discovery[current] as bridges.

Execution Sample

DSA Python

def dfs(u, parent):
    disc[u] = time[0]
    low[u] = time[0]
    time[0] += 1
    for v in graph[u]:
        if disc[v] == -1:
            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])

This code runs DFS, sets discovery and low times, updates low values, and detects bridges when low[v] > disc[u].

Execution Table

Step	Operation	Node Visited	Parent	Discovery Time (disc)	Low Value (low)	Bridges Found	Visual State
1	Start DFS	0	None	disc[0]=0	low[0]=0	[]	Graph nodes: 0,1,2,3,4; Edges: (0-1),(1-2),(2-0),(1-3),(3-4)
2	Visit neighbor	1	0	disc[1]=1	low[1]=1	[]	Visited 0->1
3	Visit neighbor	2	1	disc[2]=2	low[2]=2	[]	Visited 1->2
4	Neighbor 0: visited, not parent	0	1	disc[0]=0	low[2]=0	[]	Back edge 2->0, update low[2]=min(2,0)=0
5	Return to 1	1	0	disc[1]=1	low[1]=0	[]	Updated low[1] after DFS(2)
6	Visit neighbor	3	1	disc[3]=3	low[3]=3	[]	Visited 1->3
7	Visit neighbor	4	3	disc[4]=4	low[4]=4	[]	Visited 3->4
8	No unvisited neighbors for 4	4	3	disc[4]=4	low[4]=4	[]	Return to 3
9	Update low[3]	3	1	disc[3]=3	low[3]=3	[]	low[3] unchanged
10	Check bridge 3-4	3	1	disc[3]=3	low[4]=4	[(3,4)]	low[4] > disc[3], bridge found (3,4)
11	Return to 1	1	0	disc[1]=1	low[1]=0	[(3,4)]	Updated low[1] after DFS(3)
12	Check bridge 1-3	1	0	disc[1]=1	low[3]=3	[(3,4),(1,3)]	low[3] > disc[1], bridge found (1,3)
13	Return to 0	0	None	disc[0]=0	low[0]=0	[(3,4),(1,3)]	Updated low[0] after DFS(1)
14	Check bridge 0-1	0	None	disc[0]=0	low[1]=0	[(3,4),(1,3)]	low[1] <= disc[0], no bridge
15	DFS complete	-	-	disc=[0,1,2,3,4]	low=[0,0,0,3,4]	[(3,4),(1,3)]	All nodes visited, bridges found: (3,4),(1,3)

💡 All nodes visited, DFS complete, bridges identified where low[v] > disc[u]

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 5	After Step 9	After Step 11	After Step 13	Final
disc	[-1,-1,-1,-1,-1]	[0,1,-1,-1,-1]	[0,1,2,-1,-1]	[0,1,2,-1,-1]	[0,1,2,3,4]	[0,1,2,3,4]	[0,1,2,3,4]	[0,1,2,3,4]
low	[-1,-1,-1,-1,-1]	[0,1,-1,-1,-1]	[0,1,0,-1,-1]	[0,0,0,-1,-1]	[0,0,0,3,4]	[0,0,0,3,4]	[0,0,0,3,4]	[0,0,0,3,4]
bridges	[]	[]	[]	[]	[]	[(3,4)]	[(3,4),(1,3)]	[(3,4),(1,3)]

Key Moments - 3 Insights

Why do we update low[u] with low[v] after DFS on neighbor v?

Because low[v] represents the earliest visited node reachable from v, updating low[u] helps u know if there's a back edge from its subtree. See steps 5 and 11 where low[u] is updated after DFS calls.

Why is an edge (u,v) a bridge only if low[v] > disc[u]?

If low[v] > disc[u], it means v and its descendants cannot reach u or any ancestor of u via back edges, so removing (u,v) disconnects the graph. This is shown at steps 10 and 12 where (3,4) and (1,3) are identified as bridges.

Why do we ignore the parent node when updating low[u] for visited neighbors?

Because the parent edge is the one we came from, not a back edge. Counting it would incorrectly lower low[u]. This is seen at step 4 where neighbor 0 is not parent of 2 and low[2] is updated correctly.

Visual Quiz - 3 Questions

Look at the execution_table at step 10, what condition causes the edge (3,4) to be a bridge?

A low[4] > disc[3]

B low[3] > disc[4]

C disc[4] > low[3]

D disc[3] > low[4]

💡 Hint

Check the 'Bridges Found' and 'Low Value' columns at step 10 in execution_table.

At which step does the algorithm first update low[2] to a value less than disc[2]?

A Step 3

B Step 4

C Step 5

D Step 6

💡 Hint

Look at the 'Low Value' column for node 2 in execution_table rows 3 and 4.

If the edge (3,4) was removed from the graph, how would the bridges list change at the end?

A It would contain (3,4) and (1,3)

B It would be empty

C It would contain only (1,3)

D It would contain no bridges

💡 Hint

Without edge (3,4), low[3] remains 3 > disc[1]=1, so (1,3) is found as bridge, but no (3,4).

Concept Snapshot

Tarjan's Algorithm for Bridges:
- Use DFS to assign discovery (disc) and low values
- low[u] = earliest visited node reachable from u
- For edge (u,v), if low[v] > disc[u], (u,v) is a bridge
- Update low[u] = min(low[u], low[v]) after DFS on v
- Ignore parent edge when updating low
- Bridges disconnect the graph if removed

Full Transcript

Tarjan's algorithm finds bridges in a graph by running a depth-first search (DFS). Each node gets a discovery time and a low value. The low value tells the earliest node reachable from that node using back edges. When DFS visits neighbors, it updates the low values. If the low value of a neighbor is greater than the discovery time of the current node, the edge between them is a bridge. This means removing that edge would split the graph. The algorithm ignores the parent edge when updating low values to avoid false updates. The process continues until all nodes are visited, and all bridges are recorded.

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