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

Concept Flow - Bridges in Graph Tarjan's Algorithm

Start DFS at node u

↓

Set discovery[u

↓

For each neighbor v of u

↓

If v not visited

↓

DFS(v)

↓

Update low[u

↓

If low[v

↓

Edge u-v is a bridge

↓

Record bridge

↓

Else if v != parent[u

↓

Update low[u

↓

If all neighbors processed

↓

Return from DFS(u)

The algorithm runs DFS from each node, setting discovery and low times. It updates low values based on neighbors. If low[v] > discovery[u], edge u-v is a bridge.

Execution Sample

DSA Go

func dfs(u int, parent int) {
  discovery[u] = time
  low[u] = time
  time++
  for _, v := range neighbors[u] {
    if discovery[v] == -1 {
      dfs(v, u)
      low[u] = min(low[u], low[v])
      if low[v] > discovery[u] {
        bridges = append(bridges, [2]int{u, v})
      }
    } else if v != parent {
      low[u] = min(low[u], discovery[v])
    }
  }
}

This code performs DFS to find bridges by tracking discovery and low times.

Execution Table

Step	Operation	Node Visited	Discovery Time	Low Time	Parent	Bridge Found	Stack/Call Trace	Graph State
1	Start DFS	0	0	0	-1	No	[0]	Edges: 0-1,0-2,1-2,1-3,3-4
2	Visit neighbor	1	1	1	0	No	[0,1]	Edges: 0-1,0-2,1-2,1-3,3-4
3	Visit neighbor	2	2	2	1	No	[0,1,2]	Edges: 0-1,0-2,1-2,1-3,3-4
4	Back edge found	2	2	0	1	No	[0,1,2]	Back edge 2->0 updates low[2]=0
5	Return from 2	2	2	0	1	No	[0,1]	low[1]=min(1,0)=0
6	Visit neighbor	3	3	3	1	No	[0,1,3]	Edges: 1-3,3-4
7	Visit neighbor	4	4	4	3	No	[0,1,3,4]	Edges: 3-4
8	Return from 4	4	4	4	3	No	[0,1,3]	low[3]=min(3,4)=3
9	Check bridge	3	3	3	1	Yes	[0,1,3]	low[4]=4 > discovery[3]=3, edge 3-4 is bridge
10	Return from 3	3	3	3	1	No	[0,1]	low[1]=min(0,3)=0
11	Return from 1	1	1	0	0	No	[0]	low[0]=min(0,0)=0
12	Visit neighbor	2	2	0	0	No	[0]	Already visited, back edge ignored
13	Return from 0	0	0	0	-1	No	[]	DFS complete
14	Start DFS	5	5	5	-1	No	[5]	Edges: 5-6
15	Visit neighbor	6	6	6	5	No	[5,6]	Edges: 5-6
16	Return from 6	6	6	6	5	Yes	[5]	low[6]=6 > discovery[5]=5, edge 5-6 is bridge
17	Return from 5	5	5	5	-1	No	[]	DFS complete
18	End	-	-	-	-	-	-	All nodes visited, bridges found: (3-4), (5-6)

💡 All nodes visited, DFS finished, bridges identified where low[v] > discovery[u]

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 6	After Step 9	After Step 14	After Step 16	Final
discovery	[-1,-1,-1,-1,-1,-1,-1]	[0,-1,-1,-1,-1,-1,-1]	[0,1,-1,-1,-1,-1,-1]	[0,1,2,-1,-1,-1,-1]	[0,1,2,3,-1,-1,-1]	[0,1,2,3,4,-1,-1]	[0,1,2,3,4,5,-1]	[0,1,2,3,4,5,6]	[0,1,2,3,4,5,6]
low	[-1,-1,-1,-1,-1,-1,-1]	[0,-1,-1,-1,-1,-1,-1]	[0,1,-1,-1,-1,-1,-1]	[0,1,0,-1,-1,-1,-1]	[0,0,0,3,-1,-1,-1]	[0,0,0,3,4,-1,-1]	[0,0,0,3,4,5,-1]	[0,0,0,3,4,5,6]	[0,0,0,3,4,5,6]
time	0	1	2	3	4	5	6	7	7
bridges	[]	[]	[]	[]	[]	[(3,4)]	[(3,4)]	[(3,4),(5,6)]	[(3,4),(5,6)]

Key Moments - 3 Insights

Why do we compare low[v] > discovery[u] to find a bridge?

Because if low[v] is greater than discovery[u], it means v and its descendants cannot reach u or any ancestor of u without using edge u-v, so u-v is a bridge. See execution_table step 9 where low[4] > discovery[3] identifies edge 3-4 as a bridge.

Why do we update low[u] with discovery[v] when v is already visited and not parent?

This update accounts for back edges that connect u to an ancestor, lowering low[u]. This prevents false bridge detection. See execution_table step 4 where low[2] is updated to 0 due to back edge 2->0.

What happens if the graph is disconnected?

The algorithm runs DFS from each unvisited node to cover all components. See execution_table steps 14-17 where DFS starts at node 5, a disconnected component, finding bridge 5-6.

Visual Quiz - 3 Questions

Look at the execution_table at step 9, which edge is identified as a bridge?

A Edge 0-1

B Edge 1-2

C Edge 3-4

D Edge 5-6

💡 Hint

Check the 'Bridge Found' and 'Graph State' columns at step 9 in execution_table.

At which step does the DFS start for the disconnected component containing node 5?

A Step 1

B Step 14

C Step 6

D Step 18

💡 Hint

Look for 'Start DFS' operation on node 5 in execution_table.

If the back edge from node 2 to node 0 was missing, how would low[2] change after step 4?

A It would remain 2

B It would become 0

C It would become 1

D It would become 3

💡 Hint

Refer to step 4 where low[2] is updated due to back edge 2->0; without it, low[2] stays discovery[2].

Concept Snapshot

Tarjan's Algorithm finds bridges by DFS.
Assign discovery and low times to nodes.
Update low[u] with min of neighbors' low or discovery.
If low[v] > discovery[u], edge u-v is a bridge.
Run DFS for all components to cover disconnected graphs.

Full Transcript

Tarjan's algorithm for finding bridges in a graph uses a depth-first search (DFS) approach. Each node is assigned a discovery time when first visited and a low value representing the earliest visited vertex reachable from that node. During DFS, for each neighbor, if it is unvisited, DFS is called recursively. After returning, low[u] is updated with the minimum of low[u] and low[v]. If low[v] is greater than discovery[u], the edge u-v is a bridge because v cannot reach u or its ancestors without that edge. If the neighbor is already visited and not the parent, low[u] is updated with the minimum of low[u] and discovery[v] to account for back edges. The algorithm runs DFS from every unvisited node to handle disconnected graphs. Bridges are collected during traversal. This method efficiently finds all bridges in O(V+E) time.

Practice

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

easy

A. To identify edges that, if removed, increase the number of connected components

B. To find the shortest path between two nodes

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 identify edges that, if removed, increase the number of connected components -> Option A

4. Quick Check:

   Bridges = edges increasing components when removed [OK]

Hint: Bridges split graph if removed, Tarjan finds them fast [OK]

Common Mistakes:

• Confusing bridges with cycles
• Thinking Tarjan finds shortest paths
• Mixing bridges with node counts

2. Which of the following Go code snippets correctly declares a slice to store adjacency lists for a graph with n nodes?

easy

A. adj := make([]int, n)

B. adj := make([][]int, n)

C. adj := [][]int{n}

D. adj := make([]int, 0, n)

Solution

1. Step 1: Understand adjacency list representation

   Adjacency list for n nodes is a slice of slices: each node has a slice of connected nodes.

2. Step 2: Correct Go syntax for adjacency list

   make([][]int, n) creates a slice of n slices of ints, perfect for adjacency lists.

3. Final Answer:

   adj := make([][]int, n) -> Option B

4. Quick Check:

   Adjacency list = slice of slices [OK]

Hint: Adjacency list needs slice of slices, not flat slice [OK]

Common Mistakes:

• Using make([]int, n) which is flat slice
• Incorrect slice literal syntax
• Confusing capacity with length

3. Consider the following Go code snippet implementing part of Tarjan's algorithm for bridges. What will be the output when run on the graph edges: (0-1), (1-2), (2-0), (1-3)?

package main
import "fmt"

var (
    time int
    adj [][]int
    disc []int
    low []int
    visited []bool
)

func dfs(u, parent int) {
    visited[u] = true
    disc[u] = time
    low[u] = time
    time++

    for _, v := range adj[u] {
        if v == parent {
            continue
        }
        if !visited[v] {
            dfs(v, u)
            if low[v] > disc[u] {
                fmt.Printf("Bridge found: %d - %d\n", u, v)
            }
            if low[v] < low[u] {
                low[u] = low[v]
            }
        } else {
            if disc[v] < low[u] {
                low[u] = disc[v]
            }
        }
    }
}

func main() {
    n := 4
    adj = make([][]int, n)
    adj[0] = []int{1, 2}
    adj[1] = []int{0, 2, 3}
    adj[2] = []int{0, 1}
    adj[3] = []int{1}

    disc = make([]int, n)
    low = make([]int, n)
    visited = make([]bool, n)

    dfs(0, -1)
}

medium

A. Bridge found: 2 - 0

B. Bridge found: 0 - 1
Bridge found: 1 - 3

C. No bridges found

D. Bridge found: 1 - 3

Solution

1. Step 1: Analyze the graph structure

   The graph has a triangle between nodes 0,1,2 and a single edge from 1 to 3. The triangle edges are not bridges because removing them doesn't disconnect the graph.

2. Step 2: Identify bridges using Tarjan's logic

   Edge 1-3 is a bridge because removing it disconnects node 3. The code prints "Bridge found: 1 - 3" only.

3. Final Answer:

   Bridge found: 1 - 3 -> Option D

4. Quick Check:

   Only edge 1-3 disconnects graph [OK]

Hint: Triangle edges are not bridges; check leaf edges [OK]

Common Mistakes:

• Marking triangle edges as bridges
• Ignoring parent check in DFS
• Confusing discovery and low values

4. The following Go code attempts to find bridges using Tarjan's algorithm but has a bug. What is the error?

func dfs(u, parent int) {
    visited[u] = true
    disc[u] = time
    low[u] = time
    time++

    for _, v := range adj[u] {
        if !visited[v] {
            dfs(v, u)
            if low[v] > disc[u] {
                fmt.Printf("Bridge: %d - %d\n", u, v)
            }
            if low[v] < low[u] {
                low[u] = low[v]
            }
        } else if v != parent {
            if disc[v] < low[u] {
                low[u] = disc[v]
            }
        }
    }
}

medium

A. The time variable is not incremented

B. The else condition should check v == parent instead of v != parent

C. The parent check is missing before recursive DFS call

D. The low[u] update is done incorrectly after DFS call

Solution

1. Step 1: Check parent skipping logic

   The code does not skip the parent node before calling DFS recursively, which can cause revisiting the parent and incorrect low values.

2. Step 2: Identify missing parent check before DFS

   Correct code should have "if v == parent { continue }" before DFS call to avoid revisiting parent edge.

3. Final Answer:

   The parent check is missing before recursive DFS call -> Option C

4. Quick Check:

   Skip parent before DFS to avoid cycles [OK]

Hint: Always skip parent node before DFS recursion [OK]

Common Mistakes:

• Confusing parent check placement
• Not incrementing time variable
• Misusing else if condition

5. Given a connected undirected graph with n nodes and m edges, how can Tarjan's algorithm be adapted to find all bridges efficiently? Choose the best approach.

hard

A. Use DFS once from any node, track discovery and low times, and identify edges where low[v] > disc[u]

B. Remove edges one by one and check connectivity each time

C. Use BFS to find shortest paths and mark edges not in shortest paths as bridges

D. Run DFS from each node separately without tracking discovery times

Solution

1. Step 1: Understand Tarjan's algorithm approach

   Tarjan's algorithm uses a single DFS traversal from any node, tracking discovery and low times to find bridges efficiently.

2. Step 2: Identify condition for bridges

   An edge u-v is a bridge if low[v] > disc[u], meaning v cannot reach u or its ancestors without that edge.

3. Final Answer:

   Use DFS once from any node, track discovery and low times, and identify edges where low[v] > disc[u] -> Option A

4. Quick Check:

   Single DFS + low/disc times = bridges [OK]

Hint: Single DFS with low/disc times finds bridges fast [OK]

Common Mistakes:

• Running DFS multiple times unnecessarily
• Using BFS which doesn't track low times
• Brute force edge removal checking connectivity