Do you think IIT Guwahati certified course can help you in your career?
Introduction
A 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.
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:
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-
If we remove the edge 3-6, the graph will become a Disconnected Graph, resulting in two components👇.
If we remove the edge 3-8, the graph will become a Disconnected Graph, resulting in two components👇.
If we remove the edge 6-9, the graph will become a Disconnected Graph, resulting in two components👇.
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:
Pick an edge (u,v).
Remove the edge from the graph.
Check if the graph remains a connected one.
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' isthe 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:
#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;
}
You can also try this code with Online C++ Compiler
Below is the implementation of code in Java for finding bridges of the graph:
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();
}
}
You can also try this code with Online Java Compiler
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.
19+ registered 
