Bridges in Graph Tarjan's Algorithm in DSA C

Mental Model

We find edges that, if removed, split the graph into more parts by tracking the earliest reachable node from each node.

Analogy: Imagine a city with roads connecting neighborhoods. A bridge is a road that, if closed, cuts off some neighborhoods from others.

Graph:
  1 --- 2
   \   |
    \  |
      3

Edges:
1->2, 2->3, 1->3

Bridge edges are those that disconnect parts if removed.

Dry Run Walkthrough

Input: Graph with edges: 1-2, 2-3, 1-3, 3-4; find bridges

Goal: Identify edges that disconnect the graph if removed

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

disc[1]=1, low[1]=1, visited={1}

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[2]=2, low[2]=2, visited={1,2}

Why: Continue DFS to explore neighbors

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

disc[3]=3, low[3]=3, visited={1,2,3}

Why: Explore deeper neighbors

Step 4: From 3, visit node 4, set disc and low to 4

disc[4]=4, low[4]=4, visited={1,2,3,4}

Why: Reach leaf node

Step 5: Backtrack from 4 to 3, update low[3] = min(low[3], low[4]) = 3

low[3]=3

Why: No back edge from 4, low stays same

Step 6: Check if edge 3-4 is a bridge since low[4] > disc[3]

Edge 3-4 is a bridge

Why: Removing 3-4 disconnects node 4

Step 7: From 3, find back edge to 1, update low[3] = min(low[3], disc[1]) = 1

low[3]=1

Why: Back edge reduces low time

Step 8: Backtrack from 3 to 2, update low[2] = min(low[2], low[3]) = 1

low[2]=1

Why: Update low time considering subtree

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

low[1]=1

Why: Update low time for root

Step 10: Check edges 1-2 and 1-3; low[2] <= disc[1] and low[3] <= disc[1], so no bridges

No bridge on edges 1-2 and 1-3

Why: Back edges prevent disconnection

Result:

Bridge edges: 3-4
Graph after removing bridge:
1 -> 2 -> 3
4 (disconnected)

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX 100

int time_counter = 0;

typedef struct Node {
    int vertex;
    struct Node* next;
} Node;

Node* graph[MAX];
int disc[MAX], low[MAX], parent[MAX];
bool visited[MAX];

void add_edge(int u, int v) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->vertex = v;
    node->next = graph[u];
    graph[u] = node;

    node = (Node*)malloc(sizeof(Node));
    node->vertex = u;
    node->next = graph[v];
    graph[v] = node;
}

void dfs(int u) {
    visited[u] = true;
    disc[u] = low[u] = ++time_counter; // set discovery and low time

    Node* temp = graph[u];
    while (temp != NULL) {
        int v = temp->vertex;
        if (!visited[v]) {
            parent[v] = u;
            dfs(v);
            if (low[v] > disc[u]) {
                printf("Bridge found: %d - %d\n", u, v);
            }
            if (low[v] < low[u]) {
                low[u] = low[v]; // update low[u]
            }
        } else if (v != parent[u]) {
            if (disc[v] < low[u]) {
                low[u] = disc[v]; // update low[u] for back edge
            }
        }
        temp = temp->next;
    }
}

int main() {
    int n = 4; // nodes
    for (int i = 1; i <= n; i++) {
        graph[i] = NULL;
        visited[i] = false;
        parent[i] = -1;
        disc[i] = 0;
        low[i] = 0;
    }

    add_edge(1, 2);
    add_edge(2, 3);
    add_edge(1, 3);
    add_edge(3, 4);

    for (int i = 1; i <= n; i++) {
        if (!visited[i]) {
            dfs(i);
        }
    }

    return 0;
}

disc[u] = low[u] = ++time_counter; // set discovery and low time

Assign discovery and low time when visiting node u

if (!visited[v]) { parent[v] = u; dfs(v);

Visit unvisited neighbor v and set parent

if (low[v] > disc[u]) { printf("Bridge found: %d - %d\n", u, v); }

If no back edge from v or subtree to u or above, edge u-v is a bridge

if (low[v] < low[u]) { low[u] = low[v]; }

Update low[u] considering subtree low[v]

else if (v != parent[u]) { if (disc[v] < low[u]) { low[u] = disc[v]; } }

Update low[u] for back edge to ancestor v

Output

Bridge found: 3 - 4

Complexity Analysis

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

Space: O(V + E) for adjacency list and arrays to store discovery, low, parent, and visited

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

Edge Cases

Graph with no edges

No bridges found as there are no edges

DSA C

for (int i = 1; i <= n; i++) { if (!visited[i]) { dfs(i); } }

Graph with a single node

No bridges found as no edges exist

DSA C

for (int i = 1; i <= n; i++) { if (!visited[i]) { dfs(i); } }

Graph with multiple disconnected components

DFS runs on each component separately, finds bridges in each

DSA C

for (int i = 1; i <= n; i++) { if (!visited[i]) { dfs(i); } }

When to Use This Pattern

When asked to find edges that disconnect a graph if removed, use Tarjan's bridge-finding algorithm because it efficiently finds such edges in one DFS pass.

Common Mistakes

Mistake: Not updating low[u] correctly for back edges
Fix: Update low[u] = min(low[u], disc[v]) when encountering a back edge to ancestor v

Mistake: Checking bridge condition incorrectly as low[v] >= disc[u]
Fix: Use strict greater than (low[v] > disc[u]) to identify bridges

Mistake: Not initializing parent array or setting parent of root to -1
Fix: Initialize parent array with -1 and set parent[v] = u when visiting v

Summary

Finds edges that, if removed, increase the number of disconnected parts in a graph.

Use when you need to identify critical connections or vulnerabilities in network structures.

The key insight is tracking the earliest reachable ancestor node (low time) 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 detect cycles in a graph

B. To find 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 edges 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 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 parts when removed [OK]

Common Mistakes:

• Confusing bridges with shortest paths
• Thinking bridges detect cycles
• Assuming bridges count edges

2. Which of the following is the correct way to declare the array that stores discovery times in C for Tarjan's algorithm?

easy

A. int disc = new int[MAX];

B. int disc[];

C. int disc[MAX];

D. int[] disc = new int[MAX];

Solution

1. Step 1: Recall C array declaration syntax

   In C, arrays are declared with type and size like int arr[size];

2. Step 2: Match with discovery time array

   So, int disc[MAX]; is correct for fixed size MAX.

3. Final Answer:

   int disc[MAX]; -> Option C

4. Quick Check:

   C arrays use type name[size] [OK]

Hint: Use type name[size] for arrays in C [OK]

Common Mistakes:

• Using Java or C++ style array declarations in C
• Not specifying array size
• Using dynamic allocation syntax incorrectly

3. Consider the following code snippet for Tarjan's algorithm to find bridges. What will be printed?

void dfs(int u, int parent) {
  disc[u] = low[u] = ++time;
  for (int v : adj[u]) {
    if (disc[v] == -1) {
      dfs(v, u);
      low[u] = min(low[u], low[v]);
      if (low[v] > disc[u])
        printf("Bridge: %d - %d\n", u, v);
    } else if (v != parent) {
      low[u] = min(low[u], disc[v]);
    }
  }
}

// Graph edges:
// 0-1, 1-2, 2-0, 1-3
// Start dfs(0, -1);

medium

A. Bridge: 1 - 3

B. Bridge: 0 - 1

C. Bridge: 2 - 0

D. No bridges

Solution

1. Step 1: Analyze the graph structure

   The graph has a triangle 0-1-2 and an edge 1-3. Triangle edges are not bridges because removing them doesn't disconnect the graph.

2. Step 2: Apply Tarjan's condition for bridges

   Edge 1-3 is a bridge because removing it disconnects node 3.

3. Final Answer:

   Bridge: 1 - 3 -> Option A

4. Quick Check:

   Only edge 1-3 disconnects graph [OK]

Hint: Bridges disconnect nodes; triangle edges are safe [OK]

Common Mistakes:

• Thinking all edges in a cycle are bridges
• Ignoring parent check in DFS
• Misinterpreting low and disc values

4. The following code snippet is intended to find bridges using Tarjan's algorithm. What is the bug?

void dfs(int u, int parent) {
  disc[u] = low[u] = ++time;
  for (int v : adj[u]) {
    if (disc[v] == -1) {
      dfs(v, u);
      low[u] = min(low[u], low[v]);
      if (low[v] >= disc[u])
        printf("Bridge: %d - %d\n", u, v);
    } else if (v != parent) {
      low[u] = min(low[u], disc[v]);
    }
  }
}

medium

A. The condition should be low[v] > disc[u], not >=.

B. The disc array is not initialized.

C. The parent parameter is not used correctly.

D. The time variable is not incremented.

Solution

1. Step 1: Understand bridge condition in Tarjan's algorithm

   Bridge condition is low[v] > disc[u], meaning no back edge from v or its descendants to u or above.

2. Step 2: Identify the bug in condition

   Using >= incorrectly marks edges that are not bridges (like parent edges in cycles).

3. Final Answer:

   The condition should be low[v] > disc[u], not >=. -> Option A

4. Quick Check:

   Bridge if low[v] > disc[u] [OK]

Hint: Use strict greater than for bridge check [OK]

Common Mistakes:

• Using >= instead of > in bridge condition
• Not initializing discovery times
• Ignoring parent node in DFS

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

hard

A. [0-1, 2-3]

B. [2-3, 3-4]

C. [1-4]

D. [0-1]

Solution

1. Step 1: Visualize the graph

   Edges: 0-1, 1-2, 2-3, 3-4, 1-4. The edge 1-4 creates a cycle with 1-2-3-4.

2. Step 2: Identify bridges

   Removing 0-1 disconnects node 0, so 0-1 is a bridge. Edges 2-3 and 3-4 are in cycle with 1-4, so not bridges.

3. Final Answer:

   [0-1] -> Option D

4. Quick Check:

   Only 0-1 disconnects graph [OK]

Hint: Edges in cycles are not bridges [OK]

Common Mistakes:

• Marking cycle edges as bridges
• Ignoring connectivity after edge removal
• Confusing bridge with articulation point