그래프의 신부
12295 단어 javagraphalgorithms
/*
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++)
adj.add(new ArrayList<Integer>());
adj.get(0).add(1);
adj.get(1).add(0);
adj.get(0).add(2);
adj.get(2).add(0);
adj.get(1).add(2);
adj.get(2).add(1);
adj.get(1).add(3);
adj.get(3).add(1);
adj.get(3).add(4);
adj.get(4).add(3);
Main obj = new Main();
obj.printBridges(adj, n);
}
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){
dfs(i,-1,visited,timeOfInsertion,lowestTimeOfInstion,adjList,timer);
}
}
}
public void dfs(int node, int parent, int visted[], int timeOfInsertion[], int lowestTimeOfInstion[], int timer){
visited[node] = 1;
timeOfInsertion[node] = lowestTimeOfInstion[node] = timer++;
for(Integer adjNode : adjList.get(node)){
if(adjNode == parent) continue; // if adjacent node is parent node just continue
if(visited[adjNode] == 0){
dfs(adjNode, node,visited,timeOfInsertion,lowestTimeOfInstion,adjList,timer);
lowestTimeOfInstion[node] = Integer.min(lowestTimeOfInstion[node],lowestTimeOfInstion[adjNode]);
// the case that check if the current edge is could be bridge or not
if(lowestTimeOfInstion[adjNode] > timeOfInsertion[node]){
System.out.println(adjNode + " " + node);
}
}
else lowestTimeOfInstion[node] = Integer.min(lowestTimeOfInstion[node],timeOfInsertion[adjNode]);
}
}
Reference
이 문제에 관하여(그래프의 신부), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://dev.to/prashantrmishra/brides-in-the-graph-44dc텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)