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.