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.

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