Graph Learning (17 Part Series)
1 Breadth First Search Traversal of Graph GeeksForGeeks
2 Topological Sorting in Graph Using DFS and BFS GeeksForGeeks
… 13 more parts…
3 Check if a graph is Bipartite or not Leetcode
4 Cycle detection in a graph using Breadh First Search and Depth First Search GeeksForGeeks
5 Depth first search GeeksForGeeks
6 Shortest Distance from source to all other nodes in the graph where the edge weight is 1 unit
7 Dijkstra’s single source shortest path algorithm
8 Minimum Spanning Tree (Prims Algorithm)
9 Minimum Spanning Tree (Kruskal’s algorithm) Using Disjoint set
10 Bridges in the graph
11 Strongly connected components in the graph
12 Bellman ford algorithm(Single Source Shorted Path in DAG)
13 Floyd Warshall Algorithm (Multi-source shorted path)
14 Disjoint Set Graph Learning
15 Disjoint set graph with union by rank and union by size
16 Number of islands
17 Find safest walk through the grid
/** 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) We will use Tarjan's algorithm for finding the bridges in the graph we will keep two array timeOfInsertion[], lowestTimeOfInsertion[] note: timeOfInsertion will keep track of step/time at which a node was visited(we will use dfs for traversing the nodes) lowestTimeOfInsertion[]: will be updated as and when we visit adjacent nodes, initially the unvisited nodes will have same timeOfInsertion and lowestTimeOfInsertion. But when we will encounter a neighour node say B of current node A(parent) that is already visited(B) ( which is not parent of A). we will updated the lowestTimeOfInsertion[] for the node A such that lowestTimeOfInsertion[A] = min(lowestTimeOfInsertion[A], lowestTimeOfInsertion[B]) at the end of a dfs call if node----adjacetNode can be removed ( to check if they form component) if the timeOfInserstion[node] > lowestTimeOfInsertion[adjacentNode] then node can still reach from someother adjacentNode node----AdjancentNode is not a bridge Similary we will do for rest of the nodes and determine the bridge in the given graph */
class Solution {
public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
int[] timeOfInsertion = new int[n];//dfs insertion time
int[] lowestTimeOfInsertion = new int[n];// min of lowest insertion time of all adjacent node except parent
//creating adjacency list
List<List<Integer>> adj = new ArrayList<>();
for(int i =0;i<n;i++) adj.add(new ArrayList<>());
for(List<Integer> list : connections){
//since the edge are undirected hence
adj.get(list.get(0)).add(list.get(1));
adj.get(list.get(1)).add(list.get(0));
}
int visited[] = new int[n];
List<List<Integer>> bridges = new ArrayList<>();
for(int i =0;i<n;i++){
if(visited[i]== 0){
dfs(0,-1,adj,visited,bridges,0,timeOfInsertion,lowestTimeOfInsertion);
}
}
return bridges;
}
public void dfs(int node, int parent, List<List<Integer>> adj, int visited[] , List<List<Integer>> bridges,int time, int t[] , int[] low){
visited[node] = 1;
t[node] =low[node] = time++;
/* 5-------6 /\ / \ 7 9 Say, we are at 9 in dfs coming from 8(parent) 6,7 are visited already \ / note: lowestTimeOfInsertion[6] = 6 and lowestTimeOfInsertion[9] = 9 => it will be updated \ / as min of both hence lowestTimeOfInsertion[9] =6, meaning from 9 it is possible to reach 8 at node with lowest insertion time of 6 hence any higher insertion time(>6) node can also be reached from 9 (i.e if 8----9 is removed then also we can reach 8 since now the lowestTimeOfInsertion[9] is 6, so from 9 to 6 to 7 to 8 is possible, hence 8---9 is not bridge) */
for(int adjNode : adj.get(node)){
if(adjNode == parent) continue;
if(visited[adjNode] ==0){
dfs(adjNode,node,adj,visited,bridges,time,t,low);
//from the example above once the dfs traversal of 9 is done it will come back to 8, hence 8 will updated its lowestTimeOfInsertion as well by choosing min of low of 8, 9
low[node] = Integer.min(low[node],low[adjNode]);
//after 8(node) updates its lowestTimeOfInsertion it check if (node)8---9(adjNode) could be a bridge or not
// if the timeOfinssertion[node] < lowestTimeOfInsertion[adjNode] then it is not possible for adjNode(9) to reach to node(8) hence this will form bridge else not a bride 8---9
if(t[node] < low[adjNode]) {
List<Integer> edge = new ArrayList<>();
edge.add(node);
edge.add(adjNode);
bridges.add(edge);
}
}
else{
low[node] = Integer.min(low[node],low[adjNode]); // if the adjNode is visited ( in above example 6) update the lowestTimeOfInsertion[9] = min of lowestTimeOfInsertion of 6 and 9
}
}
}
}
Enter fullscreen mode Exit fullscreen mode
For more detailed explanation refer
Graph Learning (17 Part Series)
1 Breadth First Search Traversal of Graph GeeksForGeeks
2 Topological Sorting in Graph Using DFS and BFS GeeksForGeeks
… 13 more parts…
3 Check if a graph is Bipartite or not Leetcode
4 Cycle detection in a graph using Breadh First Search and Depth First Search GeeksForGeeks
5 Depth first search GeeksForGeeks
6 Shortest Distance from source to all other nodes in the graph where the edge weight is 1 unit
7 Dijkstra’s single source shortest path algorithm
8 Minimum Spanning Tree (Prims Algorithm)
9 Minimum Spanning Tree (Kruskal’s algorithm) Using Disjoint set
10 Bridges in the graph
11 Strongly connected components in the graph
12 Bellman ford algorithm(Single Source Shorted Path in DAG)
13 Floyd Warshall Algorithm (Multi-source shorted path)
14 Disjoint Set Graph Learning
15 Disjoint set graph with union by rank and union by size
16 Number of islands
17 Find safest walk through the grid
原文链接：Bridges in the graph
暂无评论内容