Find Bridges in Graph Using Tarjan's Algorithm - Visualization

Graphs

Contents

VisualizationProblemExamplesSolutionAlgorithmCode

Visualization Player

Problem Statement❯

You are given a network of n servers numbered from 0 to n - 1 connected by undirected server-to-server connections, where each connection is represented as [a, b].

A critical connection is a connection that, if removed, will disconnect the network — making some servers unreachable from others.

Return all such critical connections in any order.

Note: In this problem, servers are treated as nodes of a graph, and connections as undirected edges. The goal is to find all bridges in the graph using Tarjan's Algorithm.

Examples❯

n Connections Output Description
4 [[0,1],[1,2],[2,0],[1,3]] [[1,3]] Removing edge 1-3 disconnects node 3
5 [[0,1],[1,2],[2,3],[3,4],[4,2]] [[0,1]] Only 0-1 is a bridge; others are in a cycle
2 [[0,1]] [[0,1]] Single connection is always a bridge
3 [[0,1],[1,2],[2,0]] [] Fully connected triangle — no bridges
0 [] [] Empty graph, no edges or bridges

Solution❯

Understanding the Problem

We are given a network of servers (nodes) connected by undirected edges. Each connection is a two-way link. Our goal is to find all critical connections, also known as bridges.

A bridge is an edge that, if removed, would increase the number of connected components in the graph. In simple terms, removing that edge disconnects part of the network. This is a classic graph problem, and we can solve it efficiently using Tarjan’s Algorithm, which is based on Depth-First Search (DFS).

Step-by-Step Solution with Example

step 1: Represent the Graph

We first build an adjacency list from the input list of connections. This allows us to efficiently explore all neighbors of a node during DFS.

step 2: Setup Required Structures

We initialize:

  • visited[]: to keep track of visited nodes
  • tin[]: stores the discovery time (insertion time) for each node
  • low[]: the lowest discovery time reachable from that node or its subtree
  • timer: a global counter to assign discovery times
  • result[]: a list to store all bridges found

step 3: Run DFS from Any Node

We begin DFS traversal from an unvisited node. During DFS:

  • We mark the node as visited and assign its tin and low values using the global timer.
  • For each neighbor:
    • If the neighbor is the parent (the node we came from), we skip it.
    • If the neighbor is already visited, it means a back edge exists. We update the current node’s low value using the neighbor’s tin.
    • If the neighbor is unvisited, we recursively apply DFS on it. After returning, we update the current node’s low value based on the neighbor’s low. If low[neighbor] > tin[current], then [current, neighbor] is a bridge.

step 4: Example Walkthrough

Let's consider this input:

n = 5  
connections = [[0,1],[1,2],[2,0],[1,3],[3,4]]

This forms the following graph:

  • A cycle: 0–1–2–0
  • Two edges: 1–3 and 3–4 (which are not part of any cycle)

Running Tarjan's algorithm:

  • DFS visits nodes and assigns timestamps
  • When we backtrack, we find that removing 1–3 or 3–4 would increase the number of components

Output: [[3, 4], [1, 3]]

Edge Cases

  • Disconnected Graph: If the graph has multiple disconnected parts, run DFS for each unvisited node.
  • No Bridges: If the graph is fully connected with cycles (like a complete graph), then no bridge will be found.
  • Single Node: No connections to check, return an empty list.
  • Tree Structure: Every edge in a tree is a bridge since removing any edge disconnects the graph.

Finally

Tarjan’s Algorithm is an elegant and efficient solution to detect bridges in a graph. By tracking the discovery time and the lowest reachable ancestor for each node, we can find edges that, if removed, disconnect the graph. The algorithm runs in O(V + E) time and is highly suitable for large graphs.

Understanding the idea of back edges and how they affect the low value is key to mastering this approach. With step-by-step DFS and careful updates, even beginners can grasp the intuition behind finding critical connections in a network.

Algorithm Steps❯

  1. Initialize graph as an adjacency list.
  2. Create arrays: tin[], low[] and visited[] of size n.
  3. Set a timer = 0.
  4. For each unvisited node, run DFS:
    1. Mark node as visited, set tin[node] = low[node] = timer++.
    2. For each neighbor:
      1. If it is the parent, continue.
      2. If not visited, recurse and update low[node].
      3. If low[neighbor] > tin[node], then [node, neighbor] is a bridge.
      4. If already visited, update low[node] = min(low[node], tin[neighbor]).

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>
#include <stdlib.h>

// Structure for adjacency list node
typedef struct AdjListNode {
    int dest;
    struct AdjListNode* next;
} AdjListNode;

// Structure for adjacency list
typedef struct AdjList {
    AdjListNode* head;
} AdjList;

// Graph structure
typedef struct Graph {
    int V;
    AdjList* array;
} Graph;

// Function to create a new adjacency list node
AdjListNode* newAdjListNode(int dest) {
    AdjListNode* newNode = (AdjListNode*)malloc(sizeof(AdjListNode));
    newNode->dest = dest;
    newNode->next = NULL;
    return newNode;
}

// Function to create a graph of V vertices
Graph* createGraph(int V) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->V = V;

    graph->array = (AdjList*)malloc(V * sizeof(AdjList));

    for (int i = 0; i < V; ++i)
        graph->array[i].head = NULL;

    return graph;
}

// Adds an undirected edge
void addEdge(Graph* graph, int src, int dest) {
    AdjListNode* newNode = newAdjListNode(dest);
    newNode->next = graph->array[src].head;
    graph->array[src].head = newNode;

    newNode = newAdjListNode(src);
    newNode->next = graph->array[dest].head;
    graph->array[dest].head = newNode;
}

// Global variables for Tarjan's Algorithm
int timeCounter = 0;

void bridgeUtil(Graph* graph, int u, int visited[], int disc[], int low[], int parent[], int bridges[][2], int* bridgeCount) {
    visited[u] = 1;
    disc[u] = low[u] = ++timeCounter;

    AdjListNode* temp = graph->array[u].head;
    while (temp != NULL) {
        int v = temp->dest;
        if (!visited[v]) {
            parent[v] = u;
            bridgeUtil(graph, v, visited, disc, low, parent, bridges, bridgeCount);

            low[u] = (low[u] < low[v]) ? low[u] : low[v];

            if (low[v] > disc[u]) {
                bridges[*bridgeCount][0] = u;
                bridges[*bridgeCount][1] = v;
                (*bridgeCount)++;
            }
        } else if (v != parent[u]) {
            low[u] = (low[u] < disc[v]) ? low[u] : disc[v];
        }
        temp = temp->next;
    }
}

void findBridges(Graph* graph) {
    int V = graph->V;
    int visited[V], disc[V], low[V], parent[V];
    for (int i = 0; i < V; i++) {
        visited[i] = 0;
        parent[i] = -1;
    }

    int bridges[V * V][2]; // Max possible bridges
    int bridgeCount = 0;

    for (int i = 0; i < V; i++) {
        if (!visited[i]) {
            bridgeUtil(graph, i, visited, disc, low, parent, bridges, &bridgeCount);
        }
    }

    printf("Critical connections (bridges):\n");
    for (int i = 0; i < bridgeCount; i++) {
        printf("%d - %d\n", bridges[i][0], bridges[i][1]);
    }
}

int main() {
    int n = 4;
    Graph* graph = createGraph(n);
    addEdge(graph, 0, 1);
    addEdge(graph, 1, 2);
    addEdge(graph, 2, 0);
    addEdge(graph, 1, 3);

    findBridges(graph);
    return 0;
}

Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...