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, called bridges, if removed, will split the network into disconnected parts. You will use Tarjan's algorithm to find these bridges in a graph.

🎯 Goal: Build a program that finds all bridges in an undirected graph using Tarjan's algorithm. The program will output the list of bridges as pairs of nodes.

📋 What You'll Learn

Create an adjacency list representation of the graph

Use arrays to track discovery times and low values of nodes

Implement Tarjan's DFS 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, if broken, can disrupt communication.

💼 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 a dictionary called graph representing the undirected graph with these edges: (0, 1), (1, 2), (2, 0), (1, 3), (3, 4). Each key is an integer node, and the value is a list of connected nodes.

DSA C#

# Create the graph adjacency list as a dictionary>
# Your code here

Hint

Use a Dictionary<int, List<int>> and initialize it with the given edges.

2

Initialize discovery and low arrays and a timer

Create integer arrays called discovery and low with size 5, initialized to -1. Also create an integer variable called time and set it to 0.

DSA C#

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        Dictionary> graph = new Dictionary>
        {
            {0, new List{1, 2}},
            {1, new List{0, 2, 3}},
            {2, new List{0, 1}},
            {3, new List{1, 4}},
            {4, new List{3}}
        };

        // Initialize discovery and low arrays and time variable
        // Your code here
    }
}

Hint

Use a for loop to set all elements of discovery and low to -1.

3

Implement Tarjan's DFS to find bridges

Add a static method called DFS with parameters int u, int parent, Dictionary<int, List<int>> graph, int[] discovery, int[] low, ref int time, and List<Tuple<int, int>> bridges. Inside DFS, set discovery[u] and low[u] to time, then increment time. For each neighbor v of u, if discovery[v] is -1, recursively call DFS for v with u as parent, then update low[u] with low[v]. If low[v] > discovery[u], add Tuple.Create(u, v) to bridges. Else if v is not parent, update low[u] with discovery[v]. Then, in Main, create a list called bridges to store bridge edges, and call DFS for each node with discovery -1.

DSA C#

using System;
using System.Collections.Generic;

class Program
{
    static void DFS(int u, int parent, Dictionary> graph, int[] discovery, int[] low, ref int time, List> bridges)
    {
        // Your code here
    }

    static void Main()
    {
        Dictionary> graph = new Dictionary>
        {
            {0, new List{1, 2}},
            {1, new List{0, 2, 3}},
            {2, new List{0, 1}},
            {3, new List{1, 4}},
            {4, new List{3}}
        };

        int[] discovery = new int[5];
        int[] low = new int[5];
        for (int i = 0; i > bridges = new List>();

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

Hint

Follow Tarjan's algorithm steps carefully. Use discovery and low arrays to track times. Add edges to bridges when condition is met.

4

Print all bridges found

Add code in Main to print each bridge in the bridges list as "Bridge: u - v" where u and v are the nodes of the bridge.

DSA C#

using System;
using System.Collections.Generic;

class Program
{
    static void DFS(int u, int parent, Dictionary> graph, int[] discovery, int[] low, ref int time, List> bridges)
    {
        discovery[u] = time;
        low[u] = time;
        time++;

        foreach (int v in graph[u])
        {
            if (discovery[v] == -1)
            {
                DFS(v, u, graph, discovery, low, ref time, bridges);
                low[u] = Math.Min(low[u], low[v]);

                if (low[v] > discovery[u])
                {
                    bridges.Add(Tuple.Create(u, v));
                }
            }
            else if (v != parent)
            {
                low[u] = Math.Min(low[u], discovery[v]);
            }
        }
    }

    static void Main()
    {
        Dictionary> graph = new Dictionary>
        {
            {0, new List{1, 2}},
            {1, new List{0, 2, 3}},
            {2, new List{0, 1}},
            {3, new List{1, 4}},
            {4, new List{3}}
        };

        int[] discovery = new int[5];
        int[] low = new int[5];
        for (int i = 0; i > bridges = new List>();

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

        // Print all bridges
        // Your code here
    }
}

Hint

Use a foreach loop to print each bridge in the format Bridge: u - v.

Practice

1. What is the main purpose of Tarjan's algorithm when finding bridges in a graph?

easy

A. To sort nodes in topological order

B. To find the shortest path between two nodes

C. To detect cycles in a graph

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

Solution

1. Step 1: Understand what a bridge is in a graph

   A bridge is an edge that, when removed, increases the number of connected components in the graph.

2. Step 2: Identify Tarjan's algorithm goal

   Tarjan's algorithm finds such edges efficiently by using depth-first search and tracking discovery and low times.

3. Final Answer:

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

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
• Mixing bridges with articulation points

2. Which of the following is the correct way to declare the arrays used for discovery and low times in C# for Tarjan's algorithm?

easy

A. int disc = new int[n]; int low = new int[n];

B. int[] disc = new int[n]; int[] low = new int[n];

C. int disc[] = new int[n]; int low[] = new int[n];

D. int[] disc, low = new int[n];

Solution

1. Step 1: Recall C# array declaration syntax

   In C#, arrays are declared as type[] name = new type[size];

2. Step 2: Check each option

   int[] disc = new int[n]; int[] low = new int[n]; uses correct syntax for both arrays. int disc[] = new int[n]; int low[] = new int[n]; uses Java-style syntax, invalid in C#. int disc = new int[n]; int low = new int[n]; misses [] for arrays. int[] disc, low = new int[n]; declares only low as array, disc is just a variable.

3. Final Answer:

   int[] disc = new int[n]; int[] low = new int[n]; -> Option B

4. Quick Check:

   C# arrays = type[] name = new type[size] [OK]

Hint: Use type[] name = new type[size] in C# [OK]

Common Mistakes:

• Using Java array syntax in C#
• Forgetting [] in declaration
• Declaring multiple arrays incorrectly

3. Given the following graph edges and Tarjan's algorithm code snippet, what is the output list of bridges?

Edges: (0-1), (1-2), (2-0), (1-3)

// Assume graph is adjacency list
// Tarjan's algorithm finds bridges

Output bridges:

medium

A. [(0, 1)]

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

C. [(1, 3)]

D. []

Solution

1. Step 1: Analyze the graph structure

   The edges (0-1), (1-2), and (2-0) form a cycle. The edge (1-3) connects node 3 to the cycle.

2. Step 2: Identify bridges

   Edges in a cycle are not bridges because removing them does not disconnect the graph. The edge (1-3) is a bridge because removing it disconnects node 3.

3. Final Answer:

   [(1, 3)] -> Option C

4. Quick Check:

   Only edge (1-3) disconnects graph [OK]

Hint: Edges in cycles are not bridges [OK]

Common Mistakes:

• Marking cycle edges as bridges
• Ignoring leaf edges as bridges
• Confusing nodes and edges

4. Identify the bug in this Tarjan's algorithm snippet for finding bridges in C#:

void DFS(int u, int parent) {
  disc[u] = time;
  low[u] = time;
  time++;
  foreach (int v in graph[u]) {
    if (disc[v] == -1) {
      DFS(v, u);
      low[u] = Math.Min(low[u], low[v]);
      if (low[v] > disc[u])
        bridges.Add((u, v));
    } else {
      low[u] = Math.Min(low[u], disc[v]);
    }
  }
}

medium

A. The check 'if (v == parent) continue;' is missing

B. The 'disc[u]' and 'low[u]' are not initialized before DFS

C. The 'time' variable is not incremented correctly

D. The condition 'if (low[v] > disc[u])' should be 'if (low[v] >= disc[u])'

Solution

1. Step 1: Examine the DFS traversal logic

   The code lacks 'if (v == parent) continue;' after foreach. This check prevents processing the parent edge as a back edge, which would incorrectly lower low[u] and miss bridges.

2. Step 2: Rule out other options

   The condition 'if (low[v] > disc[u])' should be 'if (low[v] >= disc[u])': 'low[v] > disc[u]' is correct for bridges (strict >). The 'disc[u]' and 'low[u]' are not initialized before DFS: disc[u] and low[u] are set inside DFS. The 'time' variable is not incremented correctly: time++ follows assignment correctly.

3. Final Answer:

   The check 'if (v == parent) continue;' is missing -> Option A

4. Quick Check:

   Parent check avoids revisiting parent [OK]

Hint: Always skip parent node in DFS to avoid false bridges [OK]

Common Mistakes:

• Forgetting to skip parent node
• Using wrong comparison operator for bridges
• Not initializing discovery times

5. You have a graph with nodes 0 to 5 and edges: (0-1), (1-2), (2-0), (1-3), (3-4), (4-5), (5-3). Using Tarjan's algorithm, which edges are bridges?

hard

A. [(1, 3)]

B. [(1, 3), (3, 4)]

C. [(1, 3), (4, 5)]

D. []

Solution

1. Step 1: Analyze graph cycles and connections

   Edges (0-1), (1-2), (2-0) form a cycle. Edges (3-4), (4-5), (5-3) form another cycle. Edge (1-3) connects these two cycles.

2. Step 2: Identify bridges

   Only edge (1-3) is a bridge; removing it disconnects {0,1,2} from {3,4,5}. Cycle edges like (3-4) are not bridges (path 3-5-4 remains), similarly for others.

3. Final Answer:

   [(1, 3)] -> Option A

4. Quick Check:

   Only edge (1-3) disconnects graph [OK]

Hint: Bridges connect cycles or leaf nodes [OK]

Common Mistakes:

• Missing bridges inside connected components
• Confusing cycle edges as bridges
• Ignoring multi-cycle connections