Bridges in a graph are the edges which when removed makes the graph disconnected.
In case of an undirected graph, the definition remains the same, i.e. a bridge is an edge which when removed increases the number of connected components. In real-world, the concept of bridges is very useful. They represent vulnerabilities in a network or critical connections in a network.
Let us also introduce the concept of articulation points. Lots of applications for detecting critical points in any network for communications, airline traffic, electric circuits, etc, include the concept of bridges and articulation points (or cut vertex).
Let us consider the following figure:
If in the above network we remove node 1 and all its edges, 1-0, 1-3, 1-2 the connected components in the graph increase. Likewise removing vertex 0 will also increase the number of connected components. Hence node 0 and node 1 is articulation points.
A brute force method to check if a node is articulation point or not is to remove every node and count the number of connected components. But this algorithm will work in O (V*(V+E)), where V is the number of vertices and E is the number of edges in the graph. There is also an algorithm that finds all articulation points in O (V+E) time complexity. Let us first define the terms forward edge and back edge.
The forward edge is the edge that we encounter when we find all the edges during a DFS traversal of a graph that leads us to find DFS tree. The back edge is an edge that connects a vertex to one of its ancestor or a vertex that was discovered before its parent. In the image shown below the edge 4-2 connects 4 to one of the ancestors of its parent 3 and hence it is a back edge.
Presence of a back edge means the presence of an alternative path in case the parent of the vertex is removed. Also, forward edges can never be bridges as there is always an alternative path. Suppose a vertex u is having a child v such that none of the vertices in the subtree rooted at v has a back edge to any vertex discovered before u.
It means if vertex u is removed then there will be no path left for vertex v or any of the vertices present in the subtree rooted at vertex v to reach any vertex discovered before u, that implies, the subtree rooted at vertex v will get disconnected from the entire graph, and thus the number of components will increase and u will be counted as an articulation point.
On the other hand, if the subtree rooted at vertex v has a vertex x that has back edge that connects it to a vertex discovered before u, say y, then there will be a path for any vertex in subtree rooted at v to reach y even after removal of u, and if that is the case with all the children of u, then u will not count as an articulation point. So ultimately it all converges down to finding a back edge for every vertex.
For this, we can apply DFS and record the discovery time of every vertex and also maintain for every vertex v the earliest discovered vertex that can be reached from any subtree rooted at that vertex. But in all this we haven’t considered the case whether the root is an articulation point or not. To check this we only need to check if root has more than one child or not. If yes then the root is an articulation point. Now let us look at the code for finding the articulation in a graph.
The main function is articulation_points which starts DFS for every unvisited vertex in each connected component of the graph. In the above code tin[v] is used to denote the entry time for every node v and low[v] = min (tin[v], tin[p], low[x]), where tin[p] is for all p for which (v,p) is a back edge , low[x] is for all x for which (v,x) is a tree edge. Hence, the vertex v in the DFS tree is an articulation point if and only if low[x] ≥ tin[v].Children count is used to keep track for the root. Already discussed root will be an articulation point is children > 1 and it has no parent.
Now that we have understood the notion of DFS tree, low time, in time, back edges we will move our discussion on finding bridges. An edge between two vertices u and v in a graph is a bridge if after removing it, there will be no path left between u and v. Finding bridges is similar to finding articulation points. We start DFS traversal from the root and find the DFS tree. Like the articulation point concept, we will keep track of low and discovery time for nodes. Any edge between node v and x will be a bridge if low[x] > in[v].
Some important points to note regarding articulation points and bridges are:
- It is not necessary for an articulation point to be an endpoint of a bridge.
- Endpoints of a bridge will be an articulation point if that node has degree at least 2.
- The same algorithm cannot be used to find articulation point and bridges. Algorithms are similar but not same.
Want to clear your doubts around Data Structures and Graphs? You can visit our website www.codingninjas.com to explore our courses.
By Mridul Kumar