Bridges in Graph Tarjan's Algorithm in DSA Javascript - 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 on v

↓

Update low[u

↓

If low[v

↓

Edge u-v is a bridge

↓

Record bridge

↓

Else if v != parent

↓

Update low[u

↓

If all neighbors processed

↓

Return from DFS

This flow shows how DFS explores nodes, sets discovery and low times, updates low values, and detects bridges when low[v] > discovery[u].

Execution Sample

DSA Javascript

function dfs(u, parent) {
  discovery[u] = time;
  low[u] = time;
  time++;
  for (let v of graph[u]) {
    if (discovery[v] === -1) {
      dfs(v, u);
      low[u] = Math.min(low[u], low[v]);
      if (low[v] > discovery[u]) bridges.push([u, v]);
    } else if (v !== parent) {
      low[u] = Math.min(low[u], discovery[v]);
    }
  }
}

This code runs DFS on graph nodes, sets discovery and low times, and finds bridges by comparing low[v] and discovery[u].

Execution Table

Step	Operation	Current Node (u)	Neighbor (v)	discovery[]	low[]	Bridges Found	Visual State
1	Start DFS at node 0	0	-	[0:-1,1:-1,2:-1,3:-1,4:-1]	[0:-1,1:-1,2:-1,3:-1,4:-1]	[]	Graph: 0--1--2--3--4, All unvisited
2	Set discovery[0] and low[0]	0	-	[0:0,1:-1,2:-1,3:-1,4:-1]	[0:0,1:-1,2:-1,3:-1,4:-1]	[]	Node 0 visited, time=1
3	Explore neighbor 1 of 0	0	1	[0:0,1:-1,2:-1,3:-1,4:-1]	[0:0,1:-1,2:-1,3:-1,4:-1]	[]	Going deeper from 0 to 1
4	Start DFS at node 1	1	-	[0:0,1:-1,2:-1,3:-1,4:-1]	[0:0,1:-1,2:-1,3:-1,4:-1]	[]	Node 1 unvisited
5	Set discovery[1] and low[1]	1	-	[0:0,1:1,2:-1,3:-1,4:-1]	[0:0,1:1,2:-1,3:-1,4:-1]	[]	Node 1 visited, time=2
6	Explore neighbor 0 of 1	1	0	[0:0,1:1,2:-1,3:-1,4:-1]	[0:0,1:1,2:-1,3:-1,4:-1]	[]	Neighbor 0 is parent, skip
7	Explore neighbor 2 of 1	1	2	[0:0,1:1,2:-1,3:-1,4:-1]	[0:0,1:1,2:-1,3:-1,4:-1]	[]	Going deeper from 1 to 2
8	Start DFS at node 2	2	-	[0:0,1:1,2:-1,3:-1,4:-1]	[0:0,1:1,2:-1,3:-1,4:-1]	[]	Node 2 unvisited
9	Set discovery[2] and low[2]	2	-	[0:0,1:1,2:2,3:-1,4:-1]	[0:0,1:1,2:2,3:-1,4:-1]	[]	Node 2 visited, time=3
10	Explore neighbor 1 of 2	2	1	[0:0,1:1,2:2,3:-1,4:-1]	[0:0,1:1,2:2,3:-1,4:-1]	[]	Neighbor 1 is parent, skip
11	Explore neighbor 3 of 2	2	3	[0:0,1:1,2:2,3:-1,4:-1]	[0:0,1:1,2:2,3:-1,4:-1]	[]	Going deeper from 2 to 3
12	Start DFS at node 3	3	-	[0:0,1:1,2:2,3:-1,4:-1]	[0:0,1:1,2:2,3:-1,4:-1]	[]	Node 3 unvisited
13	Set discovery[3] and low[3]	3	-	[0:0,1:1,2:2,3:3,4:-1]	[0:0,1:1,2:2,3:3,4:-1]	[]	Node 3 visited, time=4
14	Explore neighbor 2 of 3	3	2	[0:0,1:1,2:2,3:3,4:-1]	[0:0,1:1,2:2,3:3,4:-1]	[]	Neighbor 2 is parent, skip
15	Explore neighbor 4 of 3	3	4	[0:0,1:1,2:2,3:3,4:-1]	[0:0,1:1,2:2,3:3,4:-1]	[]	Going deeper from 3 to 4
16	Start DFS at node 4	4	-	[0:0,1:1,2:2,3:3,4:-1]	[0:0,1:1,2:2,3:3,4:-1]	[]	Node 4 unvisited
17	Set discovery[4] and low[4]	4	-	[0:0,1:1,2:2,3:3,4:4]	[0:0,1:1,2:2,3:3,4:4]	[]	Node 4 visited, time=5
18	Explore neighbor 3 of 4	4	3	[0:0,1:1,2:2,3:3,4:4]	[0:0,1:1,2:2,3:3,4:4]	[]	Neighbor 3 is parent, skip
19	Return from DFS 4 to 3	3	-	[0:0,1:1,2:2,3:3,4:4]	[0:0,1:1,2:2,3:3,4:4]	[]	Update low[3] = min(3,4) = 3
20	Check if low[4] > discovery[3]	3	4	[0:0,1:1,2:2,3:3,4:4]	[0:0,1:1,2:2,3:3,4:4]	[[3,4]]	Bridge found: edge 3-4
21	Return from DFS 3 to 2	2	-	[0:0,1:1,2:2,3:3,4:4]	[0:0,1:1,2:2,3:3,4:4]	[[3,4]]	Update low[2] = min(2,3) = 2
22	Check if low[3] > discovery[2]	2	3	[0:0,1:1,2:2,3:3,4:4]	[0:0,1:1,2:2,3:3,4:4]	[[3,4],[2,3]]	Bridge found: edge 2-3
23	Return from DFS 2 to 1	1	-	[0:0,1:1,2:2,3:3,4:4]	[0:0,1:1,2:2,3:3,4:4]	[[3,4],[2,3]]	Update low[1] = min(1,2) = 1
24	Check if low[2] > discovery[1]	1	2	[0:0,1:1,2:2,3:3,4:4]	[0:0,1:1,2:2,3:3,4:4]	[[3,4],[2,3],[1,2]]	Bridge found: edge 1-2
25	Return from DFS 1 to 0	0	-	[0:0,1:1,2:2,3:3,4:4]	[0:0,1:1,2:2,3:3,4:4]	[[3,4],[2,3],[1,2]]	Update low[0] = min(0,1) = 0
26	Check if low[1] > discovery[0]	0	1	[0:0,1:1,2:2,3:3,4:4]	[0:0,1:1,2:2,3:3,4:4]	[[3,4],[2,3],[1,2],[0,1]]	Bridge found: edge 0-1
27	DFS complete	-	-	[0:0,1:1,2:2,3:3,4:4]	[0:0,1:1,2:2,3:3,4:4]	[[3,4],[2,3],[1,2],[0,1]]	All nodes visited, all edges are bridges

💡 DFS ends after visiting all nodes; bridges found at all edges because low[v] > discovery[u] for each tree edge in the path graph.

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 9	After Step 13	After Step 17	After Step 19	After Step 21	After Step 23	After Step 25	Final
discovery	[-1,-1,-1,-1,-1]	[0,-1,-1,-1,-1]	[0,1,-1,-1,-1]	[0,1,2,-1,-1]	[0,1,2,3,-1]	[0,1,2,3,4]	[0,1,2,3,4]	[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,-1,-1,-1]	[0,1,2,-1,-1]	[0,1,2,3,-1]	[0,1,2,3,4]	[0,1,2,3,4]	[0,1,2,3,4]	[0,1,2,3,4]	[0,1,2,3,4]	[0,1,2,3,4]
time	0	1	2	3	4	5	5	5	5	5	5
bridges	[]	[]	[]	[]	[]	[]	[]	[[3,4]]	[[3,4],[2,3]]	[[3,4],[2,3],[1,2]]	[[3,4],[2,3],[1,2],[0,1]]

Key Moments - 3 Insights

Why do we check if 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 removing u-v disconnects the graph. See execution_table step 20 where this condition identifies edge 3-4 as a bridge.

Why do we skip updating low[u] when neighbor v is the parent?

The parent edge leads back to the node we came from, so it doesn't provide a back edge to update low[u]. This prevents incorrect low value updates. See execution_table steps 6, 10, 14, and 18 where neighbors equal to parent are skipped.

What does low[u] represent during DFS?

low[u] is the earliest discovery time reachable from u by following zero or more tree edges and at most one back edge. It helps detect if there's a back edge connecting u's subtree to an ancestor. See variable_tracker low[] values updating after each DFS return.

Visual Quiz - 3 Questions

Look at the execution_table at step 20, what bridge is found?

A Edge between nodes 3 and 4

B Edge between nodes 2 and 3

C Edge between nodes 1 and 2

D Edge between nodes 0 and 1

💡 Hint

Check the Bridges Found column at step 20 in execution_table

At which step does the discovery time of node 2 get set?

A Step 5

B Step 9

C Step 13

D Step 17

💡 Hint

Look at discovery[] column in execution_table and find when discovery[2] changes from -1

If the edge between nodes 3 and 4 was removed from the graph, how would the bridges list change?

A It would contain the edge 3-4 as a bridge

B It would be empty because 3-4 edge doesn't exist

C It would contain more bridges

D It would contain the edge 2-3 as a bridge

💡 Hint

Refer to the bridges array in variable_tracker and consider the graph structure without edge 3-4; the remaining path would still identify earlier edges like 2-3 as bridges.

Concept Snapshot

Tarjan's Algorithm finds bridges by DFS traversal.
Assign discovery and low times to each node.
Update low[u] with min of neighbors' low or discovery.
If low[v] > discovery[u], edge u-v is a bridge.
Skip parent node to avoid false updates.
Bridges disconnect graph if removed.

Full Transcript

Tarjan's algorithm uses DFS to find bridges in a graph. Each node gets a discovery time when first visited and a low value representing the earliest reachable ancestor. During DFS, for each neighbor, if unvisited, DFS continues recursively. After returning, low[u] updates with low[v]. If low[v] is greater than discovery[u], the edge u-v is a bridge because v's subtree cannot reach u or its ancestors without that edge. If neighbor is already visited and not parent, low[u] updates with discovery[v]. This process identifies all bridges. The example graph is a straight path 0--1--2--3--4, so all edges are bridges. The execution table tracks discovery, low, and bridges step-by-step. Variable tracker shows how discovery and low arrays update. Key moments clarify why conditions check low[v] > discovery[u], why parent edges are skipped, and what low[u] means. The visual quiz tests understanding of bridge detection steps and variable updates. The snapshot summarizes the algorithm's key points for quick recall.

Practice

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

easy

A. To detect cycles in a graph

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

C. To find the shortest path between two nodes

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: Relate Tarjan's algorithm to bridges

   Tarjan's algorithm efficiently finds such edges by using DFS and tracking discovery and low times.

3. Final Answer:

   To identify 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 array in JavaScript for Tarjan's algorithm?

easy

A. const disc = new Array(n).fill(-1);

B. const disc = Array(n).map(() => 0);

C. const disc = new Array(n).map(0);

D. const disc = Array.fill(n, -1);

Solution

1. Step 1: Understand array initialization in JavaScript

   Using new Array(n).fill(value) correctly fills all elements with the given value.

2. Step 2: Check each option

   A: const disc = new Array(n).fill(-1); correctly creates an array of length n filled with -1. B: const disc = Array(n).map(() => 0); fills with 0 instead of -1. C: const disc = new Array(n).map(0); passes non-function to map, causing TypeError. D: const disc = Array.fill(n, -1); uses incorrect syntax (no static Array.fill).

3. Final Answer:

   const disc = new Array(n).fill(-1); -> Option A

4. Quick Check:

   Use fill() to initialize arrays [OK]

Hint: Use new Array(n).fill(value) to initialize arrays [OK]

Common Mistakes:

• Initializing with 0 instead of -1
• Passing non-function to map
• Wrong syntax for Array.fill

3. What will be the output bridges found by the following code snippet for the graph edges: [[0,1],[1,2],[2,0],[1,3]]?

const graph = [[1],[0,2,3],[1,0],[1]];
// Assume Tarjan's algorithm is correctly implemented and called
// Output bridges are printed as pairs of nodes

medium

A. []

B. [[0,1],[1,3]]

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

D. [[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.

2. Step 2: Identify bridges

   The triangle edges are part of a cycle, so none are bridges. The edge [1,3] connects node 3 alone, so removing it increases components.

3. Final Answer:

   [[1,3]] -> Option D

4. Quick Check:

   Only edge to isolated node is bridge [OK]

Hint: Edges in cycles are not bridges [OK]

Common Mistakes:

• Marking cycle edges as bridges
• Ignoring isolated node connections
• Confusing node indices

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

function dfs(u, parent) {
  visited[u] = true;
  disc[u] = low[u] = time++;
  for (const v of graph[u]) {
    if (!visited[v]) {
      dfs(v, u);
      low[u] = Math.min(low[u], low[v]);
      if (low[v] > disc[u]) {
        bridges.push([u, v]);
      }
    } else if (v !== parent) {
      low[u] = Math.min(low[u], disc[v]);
    }
  }
}

medium

A. The 'visited' array is not initialized

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

C. The 'time' variable is not incremented correctly

D. The else if condition should check 'v === parent' instead of 'v !== parent'

Solution

1. Step 1: Check variable initialization

   The code uses 'visited' array but does not show its initialization, which is necessary before DFS.

2. Step 2: Verify other parts

   The condition 'low[v] > disc[u]' is correct for bridges. The time variable is incremented properly. The else if condition correctly checks 'v !== parent'.

3. Final Answer:

   The 'visited' array is not initialized -> Option A

4. Quick Check:

   Initialize visited before DFS [OK]

Hint: Always initialize visited array before DFS [OK]

Common Mistakes:

• Changing correct bridge condition
• Misunderstanding parent check
• Forgetting to initialize arrays

5. Given a graph with nodes 0 to 4 and edges [[0,1],[1,2],[2,0],[1,3],[3,4]], which edges are bridges using Tarjan's algorithm?

hard

A. [[0,1],[1,2],[2,0]]

B. [[0,1],[3,4]]

C. [[1,3],[3,4]]

D. [[1,2],[1,3]]

Solution

1. Step 1: Analyze the graph structure

   Nodes 0,1,2 form a cycle, so edges among them are not bridges. Edges [1,3] and [3,4] connect nodes outside the cycle.

2. Step 2: Identify bridges

   Removing [1,3] or [3,4] increases connected components, so these are bridges.

3. Final Answer:

   [[1,3],[3,4]] -> Option C

4. Quick Check:

   Edges connecting cycle to outside are bridges [OK]

Hint: Edges outside cycles connecting nodes are bridges [OK]

Common Mistakes:

• Marking cycle edges as bridges
• Ignoring edges connecting outside nodes
• Confusing node indices