Last Updated on February 24, 2022 by Ria Pathak
Depth First Search
Problem Statement :
Given an undirected connected graph, you must find all the edges which when removed divide the graph.
Solution Approach :
A bridge is an edge, when removed, will disconnect the graph (or increase the number of connected components by 1). Idea is to check all edges if it is an edge or not.
Method 1 (Brute Force) :
We can iterate for all the edges and remove an edge (
u--v) and check if the graph becomes disconnected, we can either use dfs or bfs for this. If graph becomes disconnected it means that the edge
u,vis a bridge, store it somewhere and increment the bridge count. Now add the edge (
u,v) back to the graph and repeat this process for all edges.
Method 2 (Efficient) :
One observation by referring certain websites to learn programming is that no edge that belong to a loop can be a bridge. So in a graph such as
1--2--3--1,removing any of the edge
3--1will not disconnect the graph. But for an undirected graph, the edge
2--1, and this edge could still be a bridge, where the only loop it is in is
1--2--1. So, we should consider only those loops formed by a back edge. This is where the parent information you’ve passed in the function argument helps. It will help you to not use the loops such as
Now to identify the back edge (or the loop),
1--2--3--1we use the low and disc arrays. The array disc keeps track of the discovery time of each vertex. The low array helps to identify if there is a loop. The low array identifies the minimum discovery time (from disc array) that the current vertex can reach.
IMAGE HERE!!! (EXAMPLE)
- Initialise the timer (timer=0).
- Iterate through vertex
v, we will mark the vertex
vas visited (
visited[v]= true), and update discovery time and low (
disc[v]= timer, low[v] = timer) .
- Iterate for all the adjacent vertices of
vand for every adjacent vertex
a, do following :
- update the parent and distance as,
parent[a] = vand
- recursively call bfs_Brigdes(
- if low[u]>disc[v], edge
u,vis a brigde.
ais not visited,
parent[v] != a,
low[v] = min(low[v],disc[u])
The time complexity of the above method 2 is represented in the form of
Vis the number of verices and
Eis the number of edges.