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

Bridges in Graph Tarjan's Algorithm

📖 Scenario: You are working as a network engineer. You want to find critical connections in a network. These connections are called bridges. If a bridge fails, some parts of the network become unreachable.We will use Tarjan's algorithm to find all bridges in a network graph.

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

📋 What You'll Learn

Create an adjacency list for the graph

Use arrays to track discovery times and low values

Implement a DFS function to find bridges

Print all bridges found in the graph

💡 Why This Matters

🌍 Real World

Network engineers use bridge detection to find critical connections that can cause network failure if broken.

💼 Career

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

1

Create the graph adjacency list

Create an integer variable V and set it to 5 for the number of vertices. Create an adjacency list array called adj of size V using int adj[5][5] initialized with zeros. Add edges to represent the graph by setting adj[0][1] = 1, adj[1][0] = 1, adj[1][2] = 1, adj[2][1] = 1, adj[1][3] = 1, adj[3][1] = 1, adj[3][4] = 1, and adj[4][3] = 1.

DSA C

# Create the graph adjacency list
# Your code here

Hint

Use a 2D array to represent the adjacency matrix for simplicity.

2

Setup discovery and low arrays and time counter

Create integer arrays disc and low of size V initialized with -1. Create an integer variable time and set it to 0.

DSA C

int V = 5;
int adj[5][5] = {0};
adj[0][1] = 1;
adj[1][0] = 1;
adj[1][2] = 1;
adj[2][1] = 1;
adj[1][3] = 1;
adj[3][1] = 1;
adj[3][4] = 1;
adj[4][3] = 1;

// Initialize discovery and low arrays and time counter
# Your code here

Hint

Use a for loop to initialize the arrays with -1.

3

Implement DFS function to find bridges

Write a function void dfs(int u, int parent) that sets disc[u] and low[u] to time and increments time. Loop through all vertices v from 0 to V-1. If adj[u][v] == 1 and v != parent, then if disc[v] == -1, call dfs(v, u) and update low[u] to the minimum of low[u] and low[v]. If low[v] > disc[u], print Bridge found: u - v. Else update low[u] to the minimum of low[u] and disc[v].

DSA C

int V = 5;
int adj[5][5] = {0};
adj[0][1] = 1;
adj[1][0] = 1;
adj[1][2] = 1;
adj[2][1] = 1;
adj[1][3] = 1;
adj[3][1] = 1;
adj[3][4] = 1;
adj[4][3] = 1;

int disc[5];
int low[5];
for (int i = 0; i < V; i++) {
    disc[i] = -1;
    low[i] = -1;
}
int time = 0;

// Write dfs function to find bridges
# Your code here

Hint

Remember to skip the parent vertex to avoid going back immediately.

Update low[u] after DFS calls and when back edges are found.

4

Run DFS and print all bridges

Write a main function that calls dfs(i, -1) for each vertex i from 0 to V-1 if disc[i] == -1. This will print all bridges in the graph.

DSA C

int V = 5;
int adj[5][5] = {0};
adj[0][1] = 1;
adj[1][0] = 1;
adj[1][2] = 1;
adj[2][1] = 1;
adj[1][3] = 1;
adj[3][1] = 1;
adj[3][4] = 1;
adj[4][3] = 1;

int disc[5];
int low[5];
for (int i = 0; i  disc[u]) {
                    printf("Bridge found: %d - %d\n", u, v);
                }
                if (low[v] < low[u]) {
                    low[u] = low[v];
                }
            } else {
                if (disc[v] < low[u]) {
                    low[u] = disc[v];
                }
            }
        }
    }
}

// Write main function to call dfs for all vertices
# Your code here

Hint

Call dfs for each vertex if it is not visited yet.

Use -1 as the parent for the first call.