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 (bridges) in a network. A bridge is a connection that, if removed, will increase the number of disconnected parts in the network. This helps you find weak points that need extra protection.

🎯 Goal: Build a program that finds all bridges in an undirected graph using Tarjan's algorithm. You will create the graph, set up helper variables, implement the DFS logic to find bridges, and finally print all bridges.

📋 What You'll Learn

Create an adjacency list for the graph with 5 nodes and these edges: (0-1), (1-2), (2-0), (1-3), (3-4)

Create helper vectors for discovery time and low time, and a time counter

Implement Tarjan's DFS function to find bridges using discovery and low times

Print all bridges as pairs of nodes in ascending order

💡 Why This Matters

🌍 Real World

Network engineers use bridge detection to find weak points in communication networks that can cause failures if disconnected.

💼 Career

Understanding Tarjan's algorithm and graph traversal is important for roles in network design, cybersecurity, and software engineering involving graph data.

1

Create the graph adjacency list

Create a vector of vectors called graph with 5 nodes. Add edges exactly as these pairs: (0, 1), (1, 2), (2, 0), (1, 3), (3, 4). The graph is undirected, so add edges both ways.

DSA C++

# Create the graph adjacency list for 5 nodes
# Your code here

Hint

Remember to add edges in both directions because the graph is undirected.

2

Set up discovery, low vectors and time counter

Create three variables: a vector of int called disc with size 5 initialized to -1, a vector of int called low with size 5 initialized to -1, and an int called time initialized to 0.

DSA C++

#include 
#include 

using namespace std;

int main() {
    vector> graph(5);
    graph[0].push_back(1);
    graph[1].push_back(0);
    graph[1].push_back(2);
    graph[2].push_back(1);
    graph[2].push_back(0);
    graph[0].push_back(2);
    graph[1].push_back(3);
    graph[3].push_back(1);
    graph[3].push_back(4);
    graph[4].push_back(3);

    // Create disc, low vectors and time counter
    // Your code here

    return 0;
}

Hint

Use vector disc(5, -1); and similar for low. Initialize time to 0.

3

Implement Tarjan's DFS to find bridges

Write a recursive function called dfs with parameters int u, int parent, vector>& graph, vector& disc, vector& low, int& time, and vector>& bridges. Inside, set disc[u] and low[u] to time, then increment time. For each neighbor v of u, if disc[v] is -1, call dfs(v, u, graph, disc, low, time, bridges), update low[u] with min(low[u], low[v]), and if low[v] > disc[u], add {u, v} to bridges. Else if v != parent, update low[u] with min(low[u], disc[v]). Then call dfs for all nodes with disc[i] == -1.

DSA C++

#include 
#include 

using namespace std;

// Write dfs function here

int main() {
    vector> graph(5);
    graph[0].push_back(1);
    graph[1].push_back(0);
    graph[1].push_back(2);
    graph[2].push_back(1);
    graph[2].push_back(0);
    graph[0].push_back(2);
    graph[1].push_back(3);
    graph[3].push_back(1);
    graph[3].push_back(4);
    graph[4].push_back(3);

    vector disc(5, -1);
    vector low(5, -1);
    int time = 0;
    vector> bridges;

    // Call dfs for all nodes with disc[i] == -1
    // Your code here

    return 0;
}

Hint

Follow Tarjan's algorithm steps carefully. Use disc and low arrays to track discovery and lowest reachable times. Remember to skip the parent node when updating low values.

4

Print all bridges found

Print all pairs in bridges in ascending order by first node, then second node. Use a for loop to print each bridge as u v on its own line.

DSA C++

#include 
#include 
#include 

using namespace std;

void dfs(int u, int parent, vector>& graph, vector& disc, vector& low, int& time, vector>& bridges) {
    disc[u] = time;
    low[u] = time;
    time++;

    for (int v : graph[u]) {
        if (disc[v] == -1) {
            dfs(v, u, graph, disc, low, time, bridges);
            low[u] = min(low[u], low[v]);
            if (low[v] > disc[u]) {
                bridges.push_back({u, v});
            }
        } else if (v != parent) {
            low[u] = min(low[u], disc[v]);
        }
    }
}

int main() {
    vector> graph(5);
    graph[0].push_back(1);
    graph[1].push_back(0);
    graph[1].push_back(2);
    graph[2].push_back(1);
    graph[2].push_back(0);
    graph[0].push_back(2);
    graph[1].push_back(3);
    graph[3].push_back(1);
    graph[3].push_back(4);
    graph[4].push_back(3);

    vector disc(5, -1);
    vector low(5, -1);
    int time = 0;
    vector> bridges;

    for (int i = 0; i < 5; i++) {
        if (disc[i] == -1) {
            dfs(i, -1, graph, disc, low, time, bridges);
        }
    }

    // Print all bridges in ascending order
    // Your code here

    return 0;
}

Hint

Sort the bridges vector before printing. Print each bridge pair on its own line with a space between the nodes.

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 the shortest path between two nodes

C. To find edges that, if removed, increase the number of connected components

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 the graph.

2. Step 2: Relate Tarjan's algorithm to bridges

   Tarjan's algorithm efficiently finds such edges by using DFS and tracking discovery and low times.

3. Final Answer:

   To find edges that, if removed, increase the number of connected components -> Option C

4. Quick Check:

   Bridges = edges increasing components when removed [OK]

Hint: Bridges disconnect graph if removed [OK]

Common Mistakes:

• Confusing bridges with cycles
• Thinking it finds shortest paths
• Assuming it counts edges only

2. Which of the following is the correct way to declare the discovery time array in C++ for Tarjan's bridge-finding algorithm on a graph with n vertices?

easy

A. int disc[n];

B. vector<int> disc(n, -1);

C. int disc = new int[n];

D. int disc[] = new int();

Solution

1. Step 1: Understand C++ array and vector declarations

   Static arrays like int disc[n]; are not standard in C++ (unless n is a constant). Using vector<int> is safer and dynamic.

2. Step 2: Identify correct initialization for discovery times

   Initializing with -1 indicates unvisited nodes, which is common practice.

3. Final Answer:

   vector<int> disc(n, -1); -> Option B

4. Quick Check:

   Use vector with size and initial value [OK]

Hint: Use vector<int> with size and init value [OK]

Common Mistakes:

• Using variable-length arrays (not standard C++)
• Incorrect pointer syntax
• Not initializing discovery times

3. Consider the following C++ code snippet using Tarjan's algorithm to find bridges. What will be the output bridges for the given graph edges?

int n = 4;
vector<int> graph[4];
graph[0].push_back(1);
graph[1].push_back(0);
graph[1].push_back(2);
graph[2].push_back(1);
graph[2].push_back(3);
graph[3].push_back(2);
// After running Tarjan's bridge finder, which edges are bridges?
// Edges are represented as pairs (u, v) with u < v

medium

A. [(0, 1), (1, 2), (2, 3)]

B. [(0, 1), (1, 2)]

C. [(0, 1), (2, 3)]

D. []

Solution

1. Step 1: Visualize the graph structure

   The graph is a chain: 0 - 1 - 2 - 3 with bidirectional edges, forming a path with no cycles.

2. Step 2: Apply Tarjan's bridge finding logic

   In a path graph (a tree), every edge is a bridge because removing any disconnects the graph. Tarjan's DFS will detect all three edges where low[v] > disc[u] for each tree edge.

3. Final Answer:

   [(0, 1), (1, 2), (2, 3)] -> Option A

4. Quick Check:

   All edges in path are bridges [OK]

Hint: All edges in chain are bridges [OK]

Common Mistakes:

• Ignoring edge (0,1) as a bridge
• Assuming no bridges in chain
• Confusing bridge with cycle edges

4. Identify the bug in the following Tarjan's algorithm snippet for finding bridges:

void dfs(int u, int parent) {
  visited[u] = true;
  disc[u] = low[u] = time++;
  for (int v : graph[u]) {
    if (v == parent) continue;
    if (!visited[v]) {
      dfs(v, u);
      low[u] = min(low[u], low[v]);
      if (low[v] > disc[u])
        bridges.push_back({u, v});
    } else {
      low[u] = min(low[u], disc[v]);
    }
  }
}

medium

A. Missing initialization of time variable before DFS

B. Incorrect comparison in if condition for bridge detection

C. Not marking nodes as visited

D. Not checking for parent node in adjacency

Solution

1. Step 1: Review the DFS function variables

   The variable 'time' is used to assign discovery times but is not shown initialized before DFS calls.

2. Step 2: Understand impact of uninitialized time

   If 'time' is not initialized to 0 before DFS, discovery and low times will be incorrect, causing wrong bridge detection.

3. Final Answer:

   Missing initialization of time variable before DFS -> Option A

4. Quick Check:

   Initialize time = 0 before DFS [OK]

Hint: Initialize time counter before DFS call [OK]

Common Mistakes:

• Forgetting to initialize time
• Confusing low and disc arrays
• Not skipping parent node in DFS

5. Given a connected undirected graph with n vertices and m edges, how can Tarjan's algorithm be adapted to find all bridges efficiently, and what is its time complexity?

hard

A. Use Dijkstra's algorithm; time complexity O(m log n)

B. Use BFS with distance arrays; time complexity O(n^2)

C. Use DFS without low arrays; time complexity O(m^2)

D. Use DFS with discovery and low arrays; time complexity O(n + m)

Solution

1. Step 1: Describe Tarjan's algorithm adaptation

   Tarjan's algorithm uses DFS traversal, tracking discovery times and low values to detect bridges efficiently.

2. Step 2: Analyze time complexity

   Each vertex and edge is visited once during DFS, so the time complexity is O(n + m), where n is vertices and m is edges.

3. Final Answer:

   Use DFS with discovery and low arrays; time complexity O(n + m) -> Option D

4. Quick Check:

   DFS + low arrays = O(n + m) [OK]

Hint: DFS with low arrays runs in linear time [OK]

Common Mistakes:

• Using BFS which is not suitable here
• Ignoring low arrays in DFS
• Confusing with shortest path algorithms