Bridges in Graph Tarjan's Algorithm in DSA Python - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a bridge in a graph?

A bridge is an edge in a graph that, if removed, increases the number of connected components. It means the edge is critical for keeping the graph connected.

intermediate

What is the main idea behind Tarjan's algorithm for finding bridges?

Tarjan's algorithm uses a depth-first search (DFS) to assign discovery times and low values to each vertex. An edge is a bridge if the low value of the connected vertex is greater than the discovery time of the current vertex.

intermediate

In Tarjan's algorithm, what does the 'low' value represent?

The 'low' value of a vertex is the earliest discovery time reachable from that vertex or its descendants by following zero or more tree edges and then possibly one back edge.

advanced

Why do we compare low[v] > disc[u] to find a bridge between u and v?

If low[v] > disc[u], it means there is no back edge from v or its descendants to u or any ancestor of u. So, removing edge (u, v) disconnects the graph, making it a bridge.

beginner

What is the time complexity of Tarjan's algorithm for finding bridges?

The time complexity is O(V + E), where V is the number of vertices and E is the number of edges, because it uses a single DFS traversal.

What does a bridge in a graph do?

A Disconnects the graph if removed

B Connects two vertices with multiple paths

C Is part of a cycle

D Is a vertex with highest degree

A bridge is an edge that, if removed, increases the number of connected components, effectively disconnecting the graph.

In Tarjan's algorithm, what does the discovery time represent?

A The order in which vertices are visited in DFS

B The number of edges connected to a vertex

C The lowest vertex reachable from a vertex

D The total number of vertices in the graph

Discovery time is the timestamp when a vertex is first visited during DFS.

Which condition identifies an edge (u, v) as a bridge in Tarjan's algorithm?

A disc[u] > disc[v]

B low[u] > disc[v]

C low[v] > disc[u]

D low[u] == low[v]

If low[v] > disc[u], edge (u, v) is a bridge because v or its descendants cannot reach u or its ancestors.

What data structure is primarily used in Tarjan's algorithm for bridges?

A Hash Map

B Queue

C Priority Queue

D Depth-First Search (DFS) stack

Tarjan's algorithm uses DFS traversal and recursion stack to explore vertices.

What is the time complexity of Tarjan's algorithm for finding bridges?

A O(E^2)

B O(V + E)

C O(V^2)

D O(log V)

Tarjan's algorithm runs in linear time relative to vertices and edges, O(V + E).

Explain how Tarjan's algorithm finds bridges in a graph using discovery and low values.

Think about how DFS helps track back edges and earliest reachable vertices.

Describe why removing a bridge edge increases the number of connected components in a graph.

Consider what happens to connectivity if that edge is gone.

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