• Customer Support: admin@thealgorists.com
  • Feedback: We are listening to your every feedback, and taking action to constantly improve your learning experience. If you have any feedback, please use this form: https://thealgorists.com/Feedback.
  • If you are a student, email to admin@thealgorists.com to get special student discount.



Prerequisites:

If you haven't already gone through the chapter on Articulation Points and watched the video, then please do so before reading this chapter as we will be using all the concepts introduced in Articulation Points chapter while discussing the algorithm to find Bridges in an undirected graph.

Video Explanation of finding Bridges using Tarjan's Algorithm:




Let G = (V, E) be a connected, undirected graph. A bridge of G is an edge whose removal disconnects G.

In the diagram below all the bridges are the edges colored in red.



Two Important Observations:


  1. If we apply the same concept of keeping track of discovery time and earliest discovered node reachable and constructing a DFS Spanning Tree as discussed in the chapter Articulation Points, then for every bridges U-V there is something interesting about the earliest discovered node reachable from the subtree (subgraph with all the descendants of V) rooted at V . If edge U-V is a bridge and U is discovered before V in the DFS, i.e, discoveryTime of U is less than discoveryTime of V then the earliest discovered vertex reachable from the subgraph rooted at V will be a vertex with discoveryTime GREATER than the discoveryTime of U.
    And why is it so? It is because an edge U-V happens to be a bridge only when none of the vertices which were discovered before V in the DFS is reachable from the subtree (subgraph with all the descendants of V, in original given graph) rooted at vertex V in DFS Spanning Tree. Look at the connected undirected graph in the diagram below: the subgraph rooted at V which consists of V, W and X is NOT connected to any of vertices which were discovered before the root of this subgraph, and the root of this subgraph is V. To say in a different way, this subtree has no backedge that takes it to a vertex discovered before the root of this DFS subtree. So if the edge connecting the root (V) of this subgraph is to the root's parent (U) is removed the subgraph becomes disconnected from the rest of the graph.
    So for all the descendents of V, the earliest discovered vertex happens to be V, and no other earlier discovered point. Which means the subgraph rooted at V is totally dependent on the back-edge U-V to be connected to the rest of the graph due to absence of any other backedge leading to a vertex discovered before discovering V.

    So, in our Depth First Search (DFS) after we just backtracked from vertex V to vertex U if we see that the earliest discovered node reachable from V through its descendents and at most one back edge but not using the back edge V-U is LESS THAN OR EQUAL TO the discovery time of vertex U then the edge U-V is definitely not a Bridge.

    The edge U-V is a Bridge when the earliest discovered node reachable from V through the descendants of V using at most one back edge but not using the back edge V-U is GREATER THAN the discovery time of vertex U.


    NOTE: When I say subtree I refer to the subtree in the DFS Spanning Tree, but when I say subgraph I refer to the corresponding subgraph in the given original graph. The subtree and the corresponding subgraph will have same root, and have same nodes in it. For example, the subtree and its corresponding subgraph rooted at V: both of them have V, W and X as nodes.


    Please click on the image below to enlarge it in a new tab. The whole algorithm we discussed above is depicted in the diagram below:



  2. Since we can do DFS from any vertex, we need to do a check to see if the logic discussed above ALWAYSholds true if any of the adjacent edge of the start vertex happens to be a bridge. A quick check by doing a DFS starting from either U and V in the graph in the diagram above shows that the logic discussed above in (1) applies as is for the start node of the DFS as well.


The code below implements the algorithm we just came up with:




This is a Premium content. Please subscribe to access the code.
After subscribing please come back and refresh this page.




Time Complexity:

The time complexity will be the time taken by the Depth First Search (DFS) : O(V + E), where V = total number of vertices in the connected undirected graph, and E = total number of edges in the graph. We are visiting all the edges and all the vertices while finding the bridges.


Problem Solving:

Problem Statment: There are n servers numbered from 0 to n-1 connected by undirected server-to-server connections forming a network where connections[i] = [a, b] represents a connection between servers a and b. Any server can reach any other server directly or indirectly through the network.
A critical connection is a connection that, if removed, will make some server unable to reach some other server.
Return all critical connections in the network in any order.
Example:
    2
   /|
  / |
 /  |
1   |
| \ | 
|  \|
|   0
|
3

Input: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]
Output: [[1,3]]
Explanation: [[3,1]] is also accepted.

Solution:

This problem is about nothing but finding bridges in the given connected undirected graph.


This is a Premium content. Please subscribe to access the code.
After subscribing please come back and refresh this page.




More on Tarjan's Algorithm:



The above content is written by:

Abhishek Dey

Abhishek Dey

A Visionary Software Engineer With A Mission To Empower Every Person & Every Organization On The Planet To Achieve More

Microsoft | University of Florida

View LinkedIn profile


If you have any feedback, please use this form: https://thealgorists.com/Feedback.




Subscribe to Our Youtube Channel

Follow Us On LinkedIn
wave