Find Bridges in a Graph

You have been given a graph. You have to find out the bridges in that graph. Graph may be connected or disconnected. You have to print vertices of particular edge which is called bridge.

 Input: 

Output:        4 – 2

                    2 – 3

                    0 – 6

                    0 – 7

Concept behind this solution

The efficient algorithm is DFS traversal of the graph. We get the DFS tree. Now, we check for every two vertices (one will be parent and another will be child). If we cut the edge between them, it is possible to go parent section from child section. Time complexity of this approach is O(V+E) where V represents vertices and E represents edges.

Code:

// C++ program to find bridges in the graph

#include<iostream>
#include <list>
#define NIL -1
using namespace std;
class Graph
{
	int V; 
	list<int> *adj;
	void bridgeUtil(int v, bool visited[], int disc[], int low[],
					int parent[]);
public:
	Graph(int V);
	void addEdge(int v, int w); 
	void bridge(); 
};


Graph::Graph(int V)
{
	this->V = V;
	adj = new list<int>[V];
}


void Graph::addEdge(int v, int w)
{
	adj[v].push_back(w);
	adj[w].push_back(v); 
}
void Graph::bridgeUtil(int u, bool visited[], int disc[],
								int low[], int parent[])
{
	
	static int time = 0;
	visited[u] = true;


		disc[u] = low[u] = ++time;


	
	list<int>::iterator i;
	for (i = adj[u].begin(); i != adj[u].end(); ++i)
	{
		int v = *i; 
				if (!visited[v])
		{
			parent[v] = u;
			bridgeUtil(v, visited, disc, low, parent);
			low[u] = min(low[u], low[v]);
			if (low[v] > disc[u])
			cout << u <<" " << v << endl;
		}


				else if (v != parent[u])
			low[u] = min(low[u], disc[v]);
	}
}
void Graph::bridge()
{
	bool *visited = new bool[V];
	int *disc = 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)
			bridgeUtil(i, visited, disc, low, parent);
}
int main()
{
	cout << "\nBridges in first graph \n";
	Graph g1(5);
	g1.addEdge(1, 0);
	g1.addEdge(0, 2);
	g1.addEdge(2, 1);
	g1.addEdge(0, 3);
	g1.addEdge(3, 4);
	g1.bridge();


	cout << "\nBridges in second graph \n";
	Graph g2(4);
	g2.addEdge(0, 1);
	g2.addEdge(1, 2);
	g2.addEdge(2, 3);
	g2.bridge();


	cout << "\nBridges in third graph \n";
	Graph g3(7);
	g3.addEdge(0, 1);
	g3.addEdge(1, 2);
	g3.addEdge(2, 0);
	g3.addEdge(1, 3);
	g3.addEdge(1, 4);
	g3.addEdge(1, 6);
	g3.addEdge(3, 5);
	g3.addEdge(4, 5);
	g3.bridge();


	return 0;
}

// JAVA program to find bridges in the graph

import java.io.*;
import java.util.*;
import java.util.LinkedList;
class Graph
{
	private int V; 
	private LinkedList<Integer> adj[];
	int time = 0;
	static final int NIL = -1;
	@SuppressWarnings("unchecked")Graph(int v)
	{
		V = v;
		adj = new LinkedList[v];
		for (int i=0; i<v; ++i)
			adj[i] = new LinkedList();
	}
	void addEdge(int v, int w)
	{
		adj[v].add(w); // Add w to v's list.
		adj[w].add(v); //Add v to w's list
	}
	void bridgeUtil(int u, boolean visited[], int disc[],
					int low[], int parent[])
	{


				visited[u] = true;
		disc[u] = low[u] = ++time;
		Iterator<Integer> i = adj[u].iterator();
		while (i.hasNext())
		{
			int v = i.next(); 
			if (!visited[v])
			{
				parent[v] = u;
				bridgeUtil(v, visited, disc, low, parent);
				low[u] = Math.min(low[u], low[v]);
				if (low[v] > disc[u])
					System.out.println(u+" "+v);
			}
			else if (v != parent[u])
				low[u] = Math.min(low[u], disc[v]);
		}
	}


	void bridge()
	{
		boolean visited[] = new boolean[V];
		int disc[] = 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)
				bridgeUtil(i, visited, disc, low, parent);
	}


	public static void main(String args[])
	{
		System.out.println("Bridges in first graph ");
		Graph g1 = new Graph(5);
		g1.addEdge(1, 0);
		g1.addEdge(0, 2);
		g1.addEdge(2, 1);
		g1.addEdge(0, 3);
		g1.addEdge(3, 4);
		g1.bridge();
		System.out.println();


		System.out.println("Bridges in Second graph");
		Graph g2 = new Graph(4);
		g2.addEdge(0, 1);
		g2.addEdge(1, 2);
		g2.addEdge(2, 3);
		g2.bridge();
		System.out.println();


		System.out.println("Bridges in Third graph ");
		Graph g3 = new Graph(7);
		g3.addEdge(0, 1);
		g3.addEdge(1, 2);
		g3.addEdge(2, 0);
		g3.addEdge(1, 3);
		g3.addEdge(1, 4);
		g3.addEdge(1, 6);
		g3.addEdge(3, 5);
		g3.addEdge(4, 5);
		g3.bridge();
	}
}

# Python program to find bridges in the graph

from collections import defaultdict
class Graph:


	def __init__(self,vertices):
		self.V= vertices #No. of vertices
		self.graph = defaultdict(list) # default dictionary to store graph
		self.Time = 0
	def addEdge(self,u,v):
		self.graph[u].append(v)
		self.graph[v].append(u)
	def bridgeUtil(self,u, visited, parent, low, disc):
		visited[u]= True
		disc[u] = self.Time
		low[u] = self.Time
		self.Time += 1
		for v in self.graph[u]:
			if visited[v] == False :
				parent[v] = u
				self.bridgeUtil(v, visited, parent, low, disc)
				low[u] = min(low[u], low[v])




				
				if low[v] > disc[u]:
					print ("%d %d" %(u,v))
	
					
			elif v != parent[u]: # Update low value of u for parent function calls.
				low[u] = min(low[u], disc[v])


	def bridge(self):
		visited = [False] * (self.V)
		disc = [float("Inf")] * (self.V)
		low = [float("Inf")] * (self.V)
		parent = [-1] * (self.V)
		for i in range(self.V):
			if visited[i] == False:
				self.bridgeUtil(i, visited, parent, low, disc)
		
g1 = Graph(5)
g1.addEdge(1, 0)
g1.addEdge(0, 2)
g1.addEdge(2, 1)
g1.addEdge(0, 3)
g1.addEdge(3, 4)




print ("Bridges in first graph ")
g1.bridge()


g2 = Graph(4)
g2.addEdge(0, 1)
g2.addEdge(1, 2)
g2.addEdge(2, 3)
print ("\nBridges in second graph ")
g2.bridge()




g3 = Graph (7)
g3.addEdge(0, 1)
g3.addEdge(1, 2)
g3.addEdge(2, 0)
g3.addEdge(1, 3)
g3.addEdge(1, 4)
g3.addEdge(1, 6)
g3.addEdge(3, 5)
g3.addEdge(4, 5)
print ("\nBridges in third graph ")
g3.bridge()

Output: