Bridges in Graph Tarjan's Algorithm in DSA Python - Build from Scratch

Bridges in Graph using Tarjan's Algorithm

📖 Scenario: You are working as a network engineer. You want to find critical connections in a network. These connections, if removed, will split the network into two or more parts. Such connections are called bridges.We will use Tarjan's algorithm to find all bridges in a network represented as an undirected graph.

🎯 Goal: Build a Python program that finds all bridges in a given undirected graph using Tarjan's algorithm.

📋 What You'll Learn

Create a graph using adjacency list representation

Use Tarjan's algorithm with discovery and low time arrays

Identify and store all bridges in the graph

Print the list of bridges as pairs of nodes

💡 Why This Matters

🌍 Real World

Network engineers use bridge detection to find critical connections that, if broken, can disrupt communication.

💼 Career

Understanding Tarjan's algorithm and graph traversal is important for roles in network security, infrastructure, and software engineering.

1

Create the graph as an adjacency list

Create a dictionary called graph representing the undirected graph with these exact edges: 0-1, 1-2, 2-0, 1-3, 3-4. Use adjacency list format where each key is a node and the value is a list of connected nodes.

DSA Python

# Your code here

Hint

Use a dictionary where keys are node numbers and values are lists of connected nodes.

2

Initialize helper variables for Tarjan's algorithm

Create these variables: time set to 0, discovery as a dictionary with all nodes from graph set to -1, low as a dictionary with all nodes set to -1, and an empty list called bridges.

DSA Python

graph = {
    0: [1, 2],
    1: [0, 2, 3],
    2: [0, 1],
    3: [1, 4],
    4: [3]
}
# Your code here

Hint

Use dictionary comprehensions to initialize discovery and low with -1 for each node.

3

Implement the DFS function for Tarjan's algorithm

Define a function called dfs with parameters u and parent. Inside it, use the global time. Set discovery[u] and low[u] to time, then increment time. For each v in graph[u], if discovery[v] is -1, recursively call dfs(v, u), update low[u] to the minimum of low[u] and low[v]. If low[v] is greater than discovery[u], append the tuple (u, v) to bridges. Else if v is not parent, update low[u] to the minimum of low[u] and discovery[v].

DSA Python

graph = {
    0: [1, 2],
    1: [0, 2, 3],
    2: [0, 1],
    3: [1, 4],
    4: [3]
}
time = 0

discovery = {node: -1 for node in graph}
low = {node: -1 for node in graph}
bridges = []

# Your code here

Hint

Follow the Tarjan's algorithm steps carefully inside the DFS function.

4

Run DFS and print the bridges

Use a for loop to iterate over each node u in graph. If discovery[u] is -1, call dfs(u, -1). Then print the bridges list.

DSA Python

graph = {
    0: [1, 2],
    1: [0, 2, 3],
    2: [0, 1],
    3: [1, 4],
    4: [3]
}
time = 0

discovery = {node: -1 for node in graph}
low = {node: -1 for node in graph}
bridges = []

def dfs(u, parent):
    global time
    discovery[u] = time
    low[u] = time
    time += 1

    for v in graph[u]:
        if discovery[v] == -1:
            dfs(v, u)
            low[u] = min(low[u], low[v])
            if low[v] > discovery[u]:
                bridges.append((u, v))
        elif v != parent:
            low[u] = min(low[u], discovery[v])

# Your code here

Hint

Run DFS from each unvisited node and then print the list of bridges.

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