Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Bridges in a Graph
3.
Problem Statement
4.
Example
5.
Approach to the solution
5.1.
Brute Force Approach
5.2.
Better Approach
5.3.
Algorithm:
5.4.
Variable Description:
6.
Implementation in C++
7.
Input snapshot📸
8.
Output snapshot📸
9.
Implementation in Java
10.
Time Complexity
11.
Space Complexity
12.
Frequently Asked Questions
12.1.
How is the data for graphs represented in the algorithm?
12.2.
What is a bridge in a graph?
12.3.
What is the other way to represent a graph?
12.4.
Give an example where bridges of a graph are of use.
13.
Conclusion
Last Updated: Mar 27, 2024
Hard

Bridges in a Graph

gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up

Introduction

graph is a non-linear data structure. A set of vertices and edges represents it. Vertices are the nodes of the graph and the edges are the links which connect two vertices. This article will help you understand bridges in a graph and implement codes in C++ and Java to find the bridges in a graph.

Bridges in a Graph

An edge is a connection that joins two vertices in a graph. A bridge is an edge in an undirected graph that, when removed, makes the graph a Disconnected Graph (whenever there are two or more nodes in a graph which do not have any edge or link between them) or divides the graph into two or more components. We will see Disconnected Graphs further in the article.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Problem Statement

We are given an undirected graph. We need to find out all the bridges in the graph if present. An example will help us understand better.

Example

Input graph:

input graph

For the input, we will give the number of vertices, the number of edges, and the edges in the graph. For the particular problem we are representing the graph using Adjacency List. You can read about the two ways to represent a graph here.

Now in the example👇, we can see that 3-6, 3-8, and 6-9 are the bridges in the graph because-

all the bridges in the graph

If we remove the edge 3-6, the graph will become a Disconnected Graph, resulting in two components👇.

2 components of the graph after the bridge is removed

If we remove the edge 3-8, the graph will become a Disconnected Graph, resulting in two components👇.

2 components of the graph after the bridge is removed

If we remove the edge 6-9, the graph will become a Disconnected Graph, resulting in two components👇.

2 components of the graph after the bridge is removed


These are the three bridges in the graph. We have to identify these bridges for the example graph.

Approach to the solution

Brute Force Approach

We can start by traversing the graph using one edge at a time. We then see if the removal of that edge causes a Disconnected graph.

The steps would be:

  1. Pick an edge (u,v).
  2. Remove the edge from the graph.
  3. Check if the graph remains a connected one.
  4. Put back the edge in the graph and move to step 1 for another edge.

 

If we see, the time complexity of this approach would be O(E*(V+E)), E representing the number of edges, and V representing the number of vertices. To improve this we follow a better approach:

Better Approach

A better approach to the solution would be using a DFS approach. In the DFS tree, we can identify a bridge between (u,v) if 

  • There's no other way to reach 'v' from 'u.'
  • Or, there's no back edge from 'v' or the vertices below 'v' in the DFS tree to 'u.' The back edge will form a cycle, and any edge part of forming a cycle can never be a bridge.

Let us see the algorithm for this approach:

Algorithm:

Begin
   t <- 0       //time variable
   visited[u]<- true // mark the vertex as visited
   set discovered[u] <- t+1
   set low[u] <- t+1
   increment t <-t+1

   for each vertex v ∈ adj_list[u] :
      if there exists an edge (u, v):
         if visited[v] is true:
            parent[v] <-u
            check_bridge(v, visited, discovered, low, parent)
            low[u] <- min(low[u] & low[v])

            if low[v] > discovered[u]:
               print(u,v) //bridge exists
         else if v is not parent[u]
            low[u]<- min (low[u] and discovered[v])
   done
End

Variable Description:

'u' is the current vertex for which every other vertex will be checked. 

'visited[]' array marks the vertices that have been visited.

'discovered[]' array stores the time at which the vertices were visited.

'parent[]' array stores the parent vertices in the DFS tree
 

Do you want to try writing the code for the problem before moving on to the solution? Here you go.

Implementation in C++

Below is the implementation of code in C++ for finding bridges of the graph:

c++
#include<iostream>

#include <list>

using namespace std;

class Graph_Bridge {
  //number of vertices in the graph
  int vertices;
  int t = -1;
  // Adjacency list for every vertex
  list < int > * adj_list;
  public:
    Graph_Bridge(int v) {
      this -> vertices = v;
      adj_list = new list < int > [vertices];
    }

  void add_Edge(int u, int v) {
    adj_list[u].push_back(v);
    adj_list[v].push_back(u);
  }

  void check_bridge(int u, bool visited[], int discovered[], int low[], int parent[]) {
    static int t = 0;

    // Mark the current node as visited
    visited[u] = true;

    // for the current node/vertex 'u,' initialize the time and the earliest visited vertex
    discovered[u] = t + 1;
    low[u] = t + 1;
    t = t + 1;

    // to iterate over all the adjacent vertices to 'u.' 
    list < int > ::iterator i;

    for (i = adj_list[u].begin(); i != adj_list[u].end(); i++) {
      // store the adjacent vertex of 'u.'
      int v = * i;

      if (!visited[v]) {
        parent[v] = u;
        check_bridge(v, visited, discovered, low, parent);

        // check if the 'v' node has a connection to a node that can be traversed through 'u.'

        low[u] = min(low[u], low[v]);

        // print the bridge_DFS in the graph
        if (low[v] > discovered[u])
          cout << "Edge between " << u << " and " << v << " is a bridge." << endl;
      }

      // for 'u' vertex update its low value
      else if (v != parent[u])
        low[u] = min(low[u], discovered[v]);
    }
  }

  // this function uses the dfs approach to find the bridges.
  void bridge_DFS() {
    bool * visited = new bool[vertices];
    int * disc = new int[vertices];
    int * low = new int[vertices];
    int * parent = new int[vertices];

    // set parent and visited arrays for every vertex as nil and false
    for (int i = 0; i < vertices; i++) {
      parent[i] = t;
      visited[i] = false;
    }
    for (int i = 0; i < vertices; i++)
      if (visited[i] == false)
        check_bridge(i, visited, disc, low, parent);
  }
};

int main() {
  cout << "Enter the number of vertices:\n";
  int n, e, k;
  cin >> n;
  int u, v;
  Graph_Bridge ob(n);

  cout << "Enter the number of edges:\n";
  cin >> e;

  cout << "Enter the edges to be added by entering the two connected vertices separated by spaces-\n";
  for (int i = 0; i < e; i++) {
    cin >> u >> v;
    ob.add_Edge(u, v);
  }
  ob.bridge_DFS();
  return 0;
}

Input snapshot📸

input ss

Output snapshot📸

output ss

Implementation in Java

Below is the implementation of code in Java for finding bridges of the graph:

java

 

import java.io.*;
import java.util.*;
import java.util.LinkedList;

class Graph_Bridge {   
    private int V;     
    private LinkedList < Integer > adj_list[];   
    int t = 0;   
    static final int NIL = -1;
       
    Graph_Bridge(int v)    
    {       
        V = v;       
        adj_list = new LinkedList[v];       
        for (int i = 0; i < v; i++)            
        	adj_list[i] = new LinkedList();   
    }
       
    void add_Edge(int u, int v)    
    {       
        adj_list[u].add(v);        
        adj_list[v].add(u);      
    }

    void check_bridge(int u, boolean visited[], int discovered[], int low[], int parent[])    
    {  
        visited[u] = true;
        discovered[u] = t + 1;       
        low[u] = t + 1;       
        t = t + 1;
               
        Iterator < Integer > i = adj_list[u].iterator();       
        while (i.hasNext())        
        {           
            int v = i.next();
            if (!visited[v])            
            {               
                parent[v] = u;               
                check_bridge(v, visited, discovered, low, parent);
                low[u]  = Math.min(low[u], low[v]);
                
                if (low[v] > discovered[u])                    
                	System.out.println("Edge between " + u + " and " + v + " is a bridge.");           
            }
            
            else if (v != parent[u])                
            	low[u]  = Math.min(low[u], discovered[v]);       
        }   
    }
       
    void bridge_DFS()    
    {          
        boolean visited[] = new boolean[V];       
        int discovered[] = new int[V];       
        int low[] = new int[V];       
        int parent[] = new int[V];
        for (int i = 0; i < V; i++)        
        {           
            parent[i] = NIL;           
            visited[i] = false;       
        }
               
        for (int i = 0; i < V; i++)           
            if (visited[i] == false)                
            	check_bridge(i, visited, discovered, low, parent);   
    }

       
    public static void main(String args[])    
    {       
        System.out.println("Enter the number of vertices\n");       
        int n, e, k;       
        Scanner sc = new Scanner(System.in);       
        n = sc.nextInt();       
        int u, v;
        Graph_Bridge g1 = new Graph_Bridge(n);

        System.out.println("Enter the number of edges\n");       
        e = sc.nextInt();
               
        System.out.println("Enter the edges to be added by entering the two connected vertices separated by spaces\n");       
        for (int i = 0; i < e; i++)        
        {           
            u = sc.nextInt();           
            v = sc.nextInt();           
            g1.add_Edge(u, v);       
        }
        g1.bridge_DFS();   
    }
}

Time Complexity

The time complexity for the above code is O(V+E), (V and E=vertices and edges in the graph).

We have used DFS to solve the problem and some additional arrays, so the time complexity remains the same as that of the DFS Algorithm.

Space Complexity

The space complexity for the code is O(B^D), where B represents the maximum number of branches in the DFS Tree and D is the maximum depth.

Frequently Asked Questions

How is the data for graphs represented in the algorithm?

We use an adjacency list to represent the graph for the above algorithm.

What is a bridge in a graph?

A bridge is an edge in an undirected graph that, when removed, makes the graph a Disconnected Graph or divides the graph into two or more components. 

What is the other way to represent a graph?

The adjacency matrix can be the other way to represent a graph.

Give an example where bridges of a graph are of use.

When we design a network, and if the network is represented using a graph bridge can determine what connections are critical. If the connection identified as a bridge breaks, the network would break into two or more disjoint networks.

Conclusion

This article made us aware of bridges in an undirected graph and implemented the code to find the same. Look at significant graph algorithms like Dijkstra's AlgorithmBellman Ford Algorithm, and Floyd Warshall Algorithm. Why not have a look at web technologies on Coding Ninjas Studio? Practice data structures and algorithmsinterview questionsDBMScomputer networks, and operating systems to crack the interviews of big tech giants. Explore other fields like machine learningdeep learningcomputer vision, and big data. Also, check out Interview Experiences for different companies.

Related Links -

To learn more about Data Structures and Algorithms, you can enroll in our DSA in C++ Course.

Happy Learning!

Previous article
Biconnected Graph
Next article
Peterson Graph Problem
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass