Bridges in graph

Pre Requisite: DFS traversal technique

Intuition:

Any edge in a component of a graph is called a bridge when the component is divided into 2 or more components if that particular edge is removed.

Example:

Consider the following graph: If in this graph, if the edge (5,6) is removed, the component gets divided into 2 components making this edge a bridge. But the edge (2,3) is removed, the component remains connected. So, this edge is not a bridge. In this graph, we have a total of 3 bridges i.e. (4,5), (5,6), and (10, 8).

To solve this problem, the Tarjan's algorithm for finding bridges (or cut-edges) in a graph will come into picture. It is based on depth-first search (DFS) which uses the concept of discovery and low times for nodes. The core idea is to identify edges that, when removed, increase the number of connected components in the graph.

Understanding:

Before moving to the algorithm, it is important to know about the two arrays that play a crucial role in the algorithm:

Discovery time / Time of insertion Array: During the DFS call, the time when a node is visited first (discovered first), is called its time of insertion or discovery time. This array will store the discovery times of the nodes.
- Usage: It helps keep track of when each node was first visited. This value is unique and incremental, meaning it increases as the DFS progresses.
Lowest time of insertion Array: The lowest time of insertion for a node refers to The minimum discovery time that can be reached from a node, considering all its descendants and back edges to its ancestors.
- Usage: It helps determine if there is a back edge that connects the node or its descendants to an ancestor, which is essential for identifying bridges.

By tracking the discovery and lowest reachable times of nodes during DFS, it can identify edges that, when removed, increase the number of connected components, thus identifying bridges.

How the two arrays help in identifying the bridges in a graph?

Consider two nodes, node u and node v, where v is the neighbor of u. Let us assume that tin[u] represents the discovery time of node u and low[v] represents the lowest discovery time reachable from node v.

If low[v] > tin[u]:
It implies that v and its descendants cannot reach u or any of u's ancestors without the edge (u, v). Therefore, removing (u, v) would disconnect u and v, making (u, v) a bridge.

Thus, when the DFS calls to the descendants are completed, this condition can be checked to identify all the edges that are a bridge.

Approach:

Create adjacency lists from the graph edges. Initialize two arrays to store discovery (insertion) and lowest times for each node. Initialize a visited array to keep track of visited nodes and a timer to keep track of discovery time. Create a list to store the bridges.
Begin DFS from an arbitrary node (node 0 or any other if the graph has multiple components). Set the parent of the starting node to -1 (indicating no parent).
For each node, mark it as visited and set its discovery and lowest time to the current timer value, then increment the timer.
Process Neighbors: For each neighbor of the current node:
- Skip the parent node to avoid backtracking.
- If the neighbor is not visited, recursively perform DFS on this neighbor:
  - After returning from the recursive call, update the lowest time of the current node.
  - If the lowest time of the neighbor is greater than the discovery time of the current node, it indicates a bridge.
- If the neighbor is already visited and not the parent, update the lowest time of the current node based on the neighbor's discovery time.
During the DFS, check the condition low[neighbor] > tin[current_node] to determine if the edge is a bridge. Add the bridge to the list of bridges if the condition is met.
After completing the DFS for all nodes, return the list of identified bridges.

Dry Run:

Solution:

#include <bits/stdc++.h>
using namespace std;

class Solution {
private:
    // To store the current time during traversal
    int timer = 1;
    
    /* Helper function to make DFS calls while 
    checking for bridges in the graph */
    void dfs(int node, int parent, vector<int> &vis, vector<int> adj[], 
             vector<int> &tin, vector<int> &low,
             vector<vector<int>> &bridges) {
        
        // Mark the node as visited
        vis[node] = 1;
        
        /* Time of insertion and the lowest time of 
        insert for node will be the current time */
        tin[node] = low[node] = timer;
        
        // Increment the current time
        timer++;
        
        // Traverse all its neighbors
        for (auto it : adj[node]) {
            
            // Skip the parent
            if (it == parent) continue;
            
            // If a neighbor is not visited
            if (vis[it] == 0) {
                
                // Make a recursive DFS call
                dfs(it, node, vis, adj, tin, low, bridges);
                
                /* Once the recursive DFS call returns, upate
                the lowest time of insertion for the node */
                low[node] = min(low[it], low[node]);

                /* If the lowest time of insertion of the 
                node is found to be greater than the 
                time of insertion of the neighbor */
                if (low[it] > tin[node]) {
                    
                    // The edge represents a bridge
                    bridges.push_back({it, node});
                }
            }
            
            // Else if the neighbor is already visited
            else {
                // Update the lowest time of insertion of the node
                low[node] = min(low[node], low[it]);
            }
        }
    }
public:

    // Function to identify the bridges in a graph
    vector<vector<int>> criticalConnections(int n,
         vector<vector<int>>& connections) {

        // Adjacency list
        vector<int> adj[n];
        
        // Add all the edges to the adjacency list
        for (auto it : connections) {
            int u = it[0], v = it[1];
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        
        // Visited array
        vector<int> vis(n, 0);
        
        // To store the time of insertion (discovery time) of nodes
        vector<int> tin(n);
        
        // To store the lowest time of insert of the nodes
        vector<int> low(n);
        
        // To store the bridges of the graph
        vector<vector<int>> bridges;
        
        // Start a DFS traversal from node 0 with its parent as -1
        dfs(0, -1, vis, adj, tin, low, bridges);
        
        // Return the computed result
        return bridges;
    }
};


int main() {

    int V = 4;
    vector<vector<int>> E = {
        {0,1},
        {1,2},
        {2,0},
        {1,3} 
    };
    
    // Creating an instance of Solution class
    Solution obj;
    
    // Function call to identify the bridges in a graph
    vector<vector<int>> ans = obj.criticalConnections(V, E);
    
    cout << "The critical connections in the given graph are:\n";
    for(int i=0; i < ans.size(); i++) {
        cout << ans[i][0] << " " << ans[i][1] << endl;
    }
    return 0;
}
import java.util.*;

class Solution {
    private int timer = 1;
    
    /* Helper function to make DFS calls while 
    checking for bridges in the graph */
    private void dfs(int node, int parent, int[] vis, List<Integer>[] adj, 
                     int[] tin, int[] low, List<List<Integer>> bridges) {
        
        // Mark the node as visited
        vis[node] = 1;
        
        /* Time of insertion and the lowest time of 
        insert for node will be the current time */
        tin[node] = low[node] = timer;
        
        // Increment the current time
        timer++;
        
        // Traverse all its neighbors
        for (int it : adj[node]) {
            
            // Skip the parent
            if (it == parent) continue;
            
            // If a neighbor is not visited
            if (vis[it] == 0) {
                
                // Make a recursive DFS call
                dfs(it, node, vis, adj, tin, low, bridges);
                
                /* Once the recursive DFS call returns, update
                the lowest time of insertion for the node */
                low[node] = Math.min(low[it], low[node]);
                
                /* If the lowest time of insertion of the 
                node is found to be greater than the 
                time of insertion of the neighbor */
                if (low[it] > tin[node]) {
                    
                    // The edge represents a bridge
                    bridges.add(Arrays.asList(it, node));
                }
            }
            
            // Else if the neighbor is already visited
            else {
                // Update the lowest time of insertion of the node
                low[node] = Math.min(low[node], low[it]);
            }
        }
    }

    // Function to identify the bridges in a graph
    public List<List<Integer>> criticalConnections(int n, 
            List<List<Integer>> connections) {

        // Adjacency list
        List<Integer>[] adj = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<>();
        }
        
        // Add all the edges to the adjacency list
        for (List<Integer> it : connections) {
            int u = it.get(0), v = it.get(1);
            adj[u].add(v);
            adj[v].add(u);
        }
        
        // Visited array
        int[] vis = new int[n];
        
        // To store the time of insertion (discovery time) of nodes
        int[] tin = new int[n];
        
        // To store the lowest time of insert of the nodes
        int[] low = new int[n];
        
        // To store the bridges of the graph
        List<List<Integer>> bridges = new ArrayList<>();
        
        // Start a DFS traversal from node 0 with its parent as -1
        dfs(0, -1, vis, adj, tin, low, bridges);
        
        // Return the computed result
        return bridges;
    }

    public static void main(String[] args) {
        int V = 4;
        List<List<Integer>> E = Arrays.asList(
            Arrays.asList(0, 1),
            Arrays.asList(1, 2),
            Arrays.asList(2, 0),
            Arrays.asList(1, 3)
        );
        
        // Creating an instance of Solution class
        Solution obj = new Solution();
        
        // Function call to identify the bridges in a graph
        List<List<Integer>> ans = obj.criticalConnections(V, E);
        
        System.out.println("The critical connections in the given graph are:");
        for (List<Integer> bridge : ans) {
            System.out.println(bridge.get(0) + " " + bridge.get(1));
        }
    }
}
class Solution:
    def __init__(self):
        self.timer = 1
    
    def dfs(self, node, parent, vis, adj, tin, low, bridges):
        # Mark the node as visited
        vis[node] = 1
        
        # Time of insertion and the lowest time of 
        # insert for node will be the current time
        tin[node] = low[node] = self.timer
        
        # Increment the current time
        self.timer += 1
        
        # Traverse all its neighbors
        for it in adj[node]:
            # Skip the parent
            if it == parent:
                continue
            
            # If a neighbor is not visited
            if vis[it] == 0:
                # Make a recursive DFS call
                self.dfs(it, node, vis, adj, tin, low, bridges)
                
                # Once the recursive DFS call returns, update
                # the lowest time of insertion for the node
                low[node] = min(low[it], low[node])

                # If the lowest time of insertion of the 
                # node is found to be greater than the 
                # time of insertion of the neighbor
                if low[it] > tin[node]:
                    # The edge represents a bridge
                    bridges.append([it, node])
            else:
                # Update the lowest time of insertion of the node
                low[node] = min(low[node], tin[it])

    def criticalConnections(self, n, connections):
        # Adjacency list
        adj = [[] for _ in range(n)]
        
        # Add all the edges to the adjacency list
        for u, v in connections:
            adj[u].append(v)
            adj[v].append(u)
        
        # Visited array
        vis = [0] * n
        
        # To store the time of insertion (discovery time) of nodes
        tin = [0] * n
        
        # To store the lowest time of insert of the nodes
        low = [0] * n
        
        # To store the bridges of the graph
        bridges = []
        
        # Start a DFS traversal from node 0 with its parent as -1
        self.dfs(0, -1, vis, adj, tin, low, bridges)
        
        # Return the computed result
        return bridges

# Main function
if __name__ == "__main__":
    V = 4
    E = [
        [0, 1],
        [1, 2],
        [2, 0],
        [1, 3]
    ]
    
    # Creating an instance of Solution class
    sol = Solution()
    
    # Function call to identify the bridges in a graph
    ans = sol.criticalConnections(V, E)
    
    print("The critical connections in the given graph are:")
    for bridge in ans:
        print(bridge[0], bridge[1])
class Solution {
    constructor() {
        this.timer = 1;
    }

    /* Helper function to make DFS calls while 
    checking for bridges in the graph */
    dfs(node, parent, vis, adj, tin, low, bridges) {
        // Mark the node as visited
        vis[node] = 1;

        /* Time of insertion and the lowest time of 
        insert for node will be the current time */
        tin[node] = low[node] = this.timer;

        // Increment the current time
        this.timer++;

        // Traverse all its neighbors
        for (let it of adj[node]) {
            // Skip the parent
            if (it === parent) continue;

            // If a neighbor is not visited
            if (vis[it] === 0) {
                // Make a recursive DFS call
                this.dfs(it, node, vis, adj, tin, low, bridges);

                /* Once the recursive DFS call returns, update 
                the lowest time of insertion for the node */
                low[node] = Math.min(low[it], low[node]);

                /* If the lowest time of insertion of the 
                node is found to be greater than the time 
                of insertion of the neighbor */
                if (low[it] > tin[node]) {
                    // The edge represents a bridge
                    bridges.push([it, node]);
                }
            } else {
                // Update the lowest time of insertion of the node
                low[node] = Math.min(low[node], tin[it]);
            }
        }
    }

    // Function to identify the bridges in a graph
    criticalConnections(n, connections) {
        // Adjacency list
        const adj = new Array(n).fill(0).map(() => []);

        // Add all the edges to the adjacency list
        for (let [u, v] of connections) {
            adj[u].push(v);
            adj[v].push(u);
        }

        // Visited array
        const vis = new Array(n).fill(0);

        // To store the time of insertion (discovery time) of nodes
        const tin = new Array(n).fill(0);

        // To store the lowest time of insert of the nodes
        const low = new Array(n).fill(0);

        // To store the bridges of the graph
        const bridges = [];

        // Start a DFS traversal from node 0 with its parent as -1
        this.dfs(0, -1, vis, adj, tin, low, bridges);

        // Return the computed result
        return bridges;
    }
}

// Main function
(() => {
    const V = 4;
    const E = [
        [0, 1],
        [1, 2],
        [2, 0],
        [1, 3]
    ];

    // Creating an instance of Solution class
    const obj = new Solution();

    // Function call to identify the bridges in a graph
    const ans = obj.criticalConnections(V, E);

    console.log("The critical connections in the given graph are:");
    for (let [u, v] of ans) {
        console.log(u, v);
    }
})();

Complexity Analysis:

Time Complexity: O(V+E) (where E represents the number of edges in the graph)
A DFS traversal is performed which takes O(V+E) time.

Space Complexity: O(V) The algorithm uses two arrays to store the discovery time and lowest time of insertion taking O(V) space. The list of bridges returned will take O(E) space in worst-case when all the edges are bridges in the graph.

Problem List

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition:

Example:

Understanding:

How the two arrays help in identifying the bridges in a graph?

Approach:

Dry Run:

Solution:

Complexity Analysis:

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code