Prashant Mishra

Posted on

# Brides in the graph

``````/*
Bridges in the graph.
Those edges in the graph whose removal will result
in 2 or more components in the graph are called as bridges in the graph.
Consider the below example:
1-------2
|       |
|       |
4-------3
|
|
5-------6
/\
/  \
7    9
\    /
\  /
8
|
|
10---11
|   /
|  /
12

edge between 4 and 5 is called bridge,
edge between 5 and 6 is bridge
edge between 8 and 10 is bride.

We will be using two things in the algorithm (We will be using depth first search algorithm)
Time of Insertion of the node
Lowest time of Insertion of the node
Time complexity is : O(n +e)
Space complexity is : O(2n)~ O(n)
*/
class Main{
public static void main(String args[]){
int n = 5;
ArrayList<ArrayList<Integer> > adj = new ArrayList<ArrayList<Integer> >();

for (int i = 0; i < n; i++)

Main obj = new Main();
}
public void printBrides(ArrayList<ArrayList<Integer>> adjList, int n){
int visited[] = new int[n];
int timeOfInsertion[] = new int[n];
int lowestTimeOfInstion[] = new int[n];
int timer =0;
for(int i =0;i<n;i++){
if(visited[i] ==0){
}
}
}
public void dfs(int node, int parent, int visted[], int timeOfInsertion[], int lowestTimeOfInstion[], int timer){
visited[node] = 1;
timeOfInsertion[node] = lowestTimeOfInstion[node] = timer++;
if(adjNode == parent) continue; // if adjacent node is parent node just continue
// the case that check if the current edge is could be bridge or not
System.out.println(adjNode + " " + node);
}
}
}
}
``````

For more detailed explanation refer

Articulation point in graph