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

↓

Else if v != parent[u

↓

Update low[u

↓

End DFS for u

↓

Repeat for all nodes

↓

All bridges found

The algorithm runs DFS from each node, setting discovery and low times. It updates low values based on neighbors and identifies bridges when low[v] > discovery[u].

Execution Sample

DSA Typescript

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 to find bridges by tracking discovery and low times, pushing edges where low[v] > discovery[u].

Execution Table

Step	Operation	Node Visited	Discovery Time	Low Time	Parent	Bridge Found	Graph State	Visual State
1	Start DFS	0	0	0	null	No	Graph: 0-[1,2], 1-[0,2], 2-[0,1,3], 3-[2,4], 4-[3]	0(d=0,l=0)
2	Visit neighbor	1	1	1	0	No	Same	0(d=0,l=0) -> 1(d=1,l=1)
3	Visit neighbor	2	2	2	1	No	Same	0(d=0,l=0) -> 1(d=1,l=1) -> 2(d=2,l=2)
4	Visit neighbor	3	3	3	2	No	Same	0(d=0,l=0) -> 1(d=1,l=1) -> 2(d=2,l=2) -> 3(d=3,l=3)
5	Visit neighbor	4	4	4	3	No	Same	0(d=0,l=0) -> ... -> 4(d=4,l=4)
6	Backtrack	4	4	4	3	No	Same	Update low[3] = min(3,4) = 3
7	Check bridge	3->4	-	-	-	Yes	Edge 3-4	Bridge found: 3-4
8	Backtrack	3	3	3	2	No	Same	Update low[2] = min(2,3) = 2
9	Check bridge	2->3	-	-	-	No	No bridge	No bridge found
10	Backtrack	2	2	1	1	No	Same	Update low[1] = min(1,1) = 1
11	Check bridge	1->2	-	-	-	No	No bridge	No bridge found
12	Backtrack	1	1	0	0	No	Same	Update low[0] = min(0,0) = 0
13	Check bridge	0->1	-	-	-	No	No bridge	No bridge found
14	Visit neighbor	2	Already visited	Already visited	0	No	Same	Update low[0] = min(0,2) = 0
15	End DFS	0	0	0	null	No	All nodes visited	Bridges: [3-4]

💡 All nodes visited, DFS complete, bridges identified

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	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]
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]
parent	[null,null,null,null,null]	[null,null,null,null,null]	[null,0,null,null,null]	[null,0,1,null,null]	[null,0,1,2,null]	[null,0,1,2,3]	[null,0,1,2,3]	[null,0,1,2,3]	[null,0,1,2,3]
bridges	[]	[]	[]	[]	[]	[]	[[3,4]]	[[3,4]]	[[3,4]]

Key Moments - 3 Insights

Why do we update low[u] with low[v] after DFS(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 v's subtree to u or above. See execution_table rows 8 and 10 where low[u] is updated after DFS calls.

Why is an edge a bridge only if low[v] > discovery[u]?

If low[v] > discovery[u], it means v's subtree cannot reach u or any ancestor of u via back edges, so removing edge u-v disconnects the graph. This is shown in execution_table row 7 where edge 3-4 is identified as a bridge.

Why do we ignore the parent node when updating low[u] with discovery[v]?

Because the parent edge is the one we came from, not a back edge. Including it would incorrectly lower low[u]. This is handled in the else-if condition in the code and shown in execution_table row 14.

Visual Quiz - 3 Questions

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

A Edge 3-4

B Edge 2-3

C Edge 0-1

D Edge 1-2

💡 Hint

Check the 'Bridge Found' and 'Visual State' columns at step 7 in execution_table.

At which step does the low time of node 2 get updated to 1?

A Step 10

B Step 8

C Step 12

D Step 14

💡 Hint

Look at the 'Low Time' column for node 2 in execution_table rows around 10.

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

A No bridges would be found

B Edge 3-4 would not be in the bridges list

C Edge 2-3 would become a bridge

D Edge 0-1 would become a bridge

💡 Hint

Refer to the 'bridges' variable in variable_tracker and the graph structure in execution_table.

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.
Ignore parent edge when updating low.
Bridges disconnect the graph if removed.

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 time representing the earliest visited node reachable from it. During DFS, for each neighbor, if it is unvisited, DFS is called recursively. After returning, the low time of the current node is updated with the minimum of its own low time and the neighbor's low time. If the neighbor's low time is greater than the current node's discovery time, the edge between them is a bridge. If the neighbor is already visited and is not the parent, the low time is updated with the neighbor's discovery time to account for back edges. This process continues until all nodes are visited, and all bridges are identified. The execution table traces these steps with discovery and low times, parent tracking, and bridge detection. Key moments clarify why low times are updated and why parent edges are excluded. The visual quiz tests understanding of bridge identification and low time updates. The concept snapshot summarizes the algorithm's key points for quick reference.

Practice

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

easy

A. To sort nodes in topological order

B. To find the shortest path between two nodes

C. To detect cycles in a graph

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

Solution

1. Step 1: Understand what a bridge is in a graph

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

2. Step 2: Identify Tarjan's algorithm goal

   Tarjan's algorithm is used to find such edges efficiently by using DFS and tracking discovery and low times.

3. Final Answer:

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

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
• Mixing with topological sorting

2. Which of the following is the correct TypeScript syntax to declare the discovery time array for Tarjan's algorithm?

easy

A. let disc = Array(n).fill('undefined');

B. let disc: number = new Array(n);

C. let disc: number[] = new Array(n).fill(-1);

D. let disc: number[] = new Array(n);

Solution

1. Step 1: Understand array declaration with initial values in TypeScript

   To create an array of numbers with size n and initialize all values to -1, use new Array(n).fill(-1).

2. Step 2: Check type correctness

   TypeScript syntax requires disc to be number[] for an array of numbers.

3. Final Answer:

   let disc: number[] = new Array(n).fill(-1); -> Option C

4. Quick Check:

   Array<number> with fill(-1) = correct initialization [OK]

Hint: Use new Array(n).fill(-1) for initialized arrays [OK]

Common Mistakes:

• Using wrong type annotation
• Not initializing array values
• Filling with string instead of number

3. Consider the following TypeScript code snippet using Tarjan's algorithm to find bridges. What will be the output bridges for the given graph?

const graph = [[1, 2], [0, 2], [0, 1, 3], [2, 4], [3]];
// Edges: 0-1, 0-2, 1-2, 2-3, 3-4
// Find bridges
const bridges = findBridges(graph);
console.log(bridges);

medium

A. [[2, 3], [3, 4]]

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

C. [[0, 2], [2, 3]]

D. []

Solution

1. Step 1: Analyze the graph edges and connectivity

   The graph edges are 0-1, 0-2, 1-2 forming a triangle, and 2-3, 3-4 forming a chain. The triangle edges are not bridges because removing one does not disconnect the graph.

2. Step 2: Identify bridges

   Edges 2-3 and 3-4 are bridges because removing either disconnects node 4 or node 3 from the rest.

3. Final Answer:

   [[2, 3], [3, 4]] -> Option A

4. Quick Check:

   Bridges disconnect graph = [[2,3],[3,4]] [OK]

Hint: Bridges are edges not in any cycle [OK]

Common Mistakes:

• Including edges inside cycles as bridges
• Missing chain edges as bridges
• Confusing node indices

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

function dfs(u: number, parent: number) {
  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 condition 'low[v] > disc[u]' should be 'low[v] >= disc[u]'

B. The 'visited' array is not initialized before DFS

C. The 'time' variable is not incremented correctly

D. The parent node check 'v !== parent' is missing

Solution

1. Step 1: Check initialization of visited array

   The code uses 'visited[u]' but does not show initialization. Without initializing, visited may be undefined causing runtime errors.

2. Step 2: Verify other parts

   The condition 'low[v] > disc[u]' is correct for bridges. The parent check is present. The time increment is correct.

3. Final Answer:

   The 'visited' array is not initialized before DFS -> Option B

4. Quick Check:

   Uninitialized visited array causes errors [OK]

Hint: Always initialize visited before DFS [OK]

Common Mistakes:

• Changing correct bridge condition
• Ignoring visited initialization
• Removing parent check

5. Given a connected undirected graph with nodes 0 to 5 and edges: 0-1, 1-2, 2-0, 1-3, 3-4, 4-5, 5-3, which edges are bridges according to Tarjan's algorithm?

hard

A. [[1, 3]]

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

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

D. []

Solution

1. Step 1: Analyze graph structure

   Edges 0-1, 1-2, 2-0 form a triangle (cycle). Edges 3-4, 4-5, 5-3 form another cycle. Edge 1-3 connects these two cycles.

2. Step 2: Identify bridges

   Only edge 1-3 is a bridge because removing it disconnects the two cycles. Other edges are part of cycles and not bridges.

3. Final Answer:

   [[1, 3]] -> Option A

4. Quick Check:

   Bridge connects two cycles = [[1, 3]] [OK]

Hint: Bridges connect separate cycles or components [OK]

Common Mistakes:

• Marking cycle edges as bridges
• Missing the connecting bridge edge
• Confusing node pairs