Bridges in Graph Tarjan's Algorithm in DSA Go

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 finds these critical bridges by walking through the islands and seeing which bridges lead to isolated parts.

Graph:
  1 --- 2
  |     |
  3 --- 4

Bridges are edges that if cut, split the graph.
Example: Edge 2-4 might be a bridge.

Representation:
1 -> [2,3]
2 -> [1,4]
3 -> [1,4]
4 -> [2,3]

↑ start at node 1

Dry Run Walkthrough

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

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

Step 1: Start DFS at node 1, set discovery time and low value to 1

disc: {1:1}, low: {1:1}, stack: [1], bridges: []

Why: Initialize discovery and low times to track earliest reachable nodes

Step 2: Visit node 2 from 1, set disc and low to 2

disc: {1:1, 2:2}, low: {1:1, 2:2}, stack: [1,2], bridges: []

Why: Explore neighbors to find earliest reachable ancestors

Step 3: Visit node 4 from 2, set disc and low to 3

disc: {1:1, 2:2, 4:3}, low: {1:1, 2:2, 4:3}, stack: [1,2,4], bridges: []

Why: Continue DFS deeper to find back edges

Step 4: Visit node 3 from 4, set disc and low to 4

disc: {1:1, 2:2, 4:3, 3:4}, low: {1:1, 2:2, 4:3, 3:4}, stack: [1,2,4,3], bridges: []

Why: Explore all neighbors to detect cycles

Step 5: Node 3 sees node 1 already visited, update low[3] to min(low[3], disc[1]) = 1

low: {3:1}, disc unchanged, bridges: []

Why: Back edge found, update low to earliest ancestor

Step 6: Backtrack to node 4, update low[4] to min(low[4], low[3]) = 1

low: {4:1}, bridges: []

Why: Propagate earliest reachable ancestor up the DFS tree

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

low: {2:1}, bridges: []

Why: Continue propagating low values

Step 8: Check edge 2-4: low[4] > disc[2]? 1 > 2? No, so not a bridge

bridges: []

Why: Edge is part of a cycle, so not a bridge

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

low: {1:1}

Why: Update low for root node

Step 10: Visit node 5 from 4, set disc and low to 5

disc: {5:5}, low: {5:5}, stack: [...,5], bridges: []

Why: Explore new node connected by edge 4-5

Step 11: Node 5 has no unvisited neighbors, backtrack to 4

low: {4:1}, disc unchanged

Why: Leaf node reached, start backtracking

Step 12: Check edge 4-5: low[5] > disc[4]? 5 > 3? Yes, so edge 4-5 is a bridge

bridges: [(4,5)]

Why: No back edge from 5 to 4 or above, so edge is critical

Result:

Bridges found: 4 -> 5
Final graph state unchanged

Annotated Code

DSA Go

package main

import (
	"fmt"
)

type Graph struct {
	adj map[int][]int
}

func NewGraph() *Graph {
	return &Graph{adj: make(map[int][]int)}
}

func (g *Graph) AddEdge(u, v int) {
	g.adj[u] = append(g.adj[u], v)
	g.adj[v] = append(g.adj[v], u)
}

func (g *Graph) FindBridges() [][2]int {
	time := 0
	disc := make(map[int]int)
	low := make(map[int]int)
	visited := make(map[int]bool)
	bridges := make([][2]int, 0)

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

		for _, v := range g.adj[u] {
			if v == parent {
				continue
			}
			if !visited[v] {
				dfs(v, u) // explore deeper
				if low[v] > disc[u] {
					bridges = append(bridges, [2]int{u, v}) // found bridge
				}
				if low[v] < low[u] {
					low[u] = low[v] // update low[u]
				}
			} else {
				if disc[v] < low[u] {
					low[u] = disc[v] // back edge found
				}
			}
		}
	}

	for u := range g.adj {
		if !visited[u] {
			dfs(u, -1) // start DFS
		}
	}

	return bridges
}

func main() {
	g := NewGraph()
	g.AddEdge(1, 2)
	g.AddEdge(1, 3)
	g.AddEdge(2, 4)
	g.AddEdge(3, 4)
	g.AddEdge(4, 5)

	bridges := g.FindBridges()
	for _, b := range bridges {
		fmt.Printf("Bridge found between nodes %d and %d\n", b[0], b[1])
	}
}

visited[u] = true

mark current node as visited to avoid revisiting

time++ disc[u] = time low[u] = time

assign discovery time and initialize low value

for _, v := range g.adj[u] { if v == parent { continue }

skip edge back to parent to prevent trivial cycle

if !visited[v] { dfs(v, u)

explore unvisited neighbor recursively

if low[v] > disc[u] { bridges = append(bridges, [2]int{u, v}) }

detect bridge if neighbor's low is greater than current discovery

if low[v] < low[u] { low[u] = low[v] }

update low[u] with earliest reachable ancestor from subtree

else { if disc[v] < low[u] { low[u] = disc[v] } }

update low[u] if back edge to ancestor found

for u := range g.adj { if !visited[u] { dfs(u, -1) } }

start DFS from each unvisited node to cover all components

Output

Bridge found between nodes 4 and 5

Complexity Analysis

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

Space: O(V) for storing discovery, low arrays and recursion stack

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

Edge Cases

Graph with no edges

No bridges found as there are no edges

DSA Go

for u := range g.adj { if !visited[u] { dfs(u, -1) } }

Graph with single node

No bridges found as no edges exist

DSA Go

for u := range g.adj { if !visited[u] { dfs(u, -1) } }

Graph with multiple disconnected components

Algorithm runs DFS on each component separately to find bridges

DSA Go

for u := range g.adj { if !visited[u] { dfs(u, -1) } }

When to Use This Pattern

When asked to find edges whose removal increases graph components, use Tarjan's bridge-finding algorithm because it efficiently finds critical edges in linear time.

Common Mistakes

Mistake: Not updating low[u] after visiting a neighbor, missing back edges
Fix: Always update low[u] with min(low[u], low[v]) after DFS call

Mistake: Checking for bridges using low[u] > disc[v] instead of low[v] > disc[u]
Fix: Compare low[v] with disc[u] to correctly identify bridges

Mistake: Not skipping the parent node in adjacency during DFS
Fix: Add condition to skip parent node to avoid false back edges

Summary

Finds edges that, if removed, split the graph into more parts (bridges).

Use when you need to identify critical connections in a network or graph.

The key insight is tracking the earliest reachable ancestor (low value) during DFS to detect bridges.

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