An edge in an undirected connected graph is a bridge iff removing it disconnects the graph. For a disconnected undirected graph, definition is similar, a bridge is an edge removing which increases number of connected components.
Like Articulation Points,bridges represent vulnerabilities in a connected network and are useful for designing reliable networks. For example, in a wired computer network, an articulation point indicates the critical computers and a bridge indicates the critical wires or connections.
Following are some example graphs with bridges highlighted with red color.
How to find all bridges in a given graph?
A simple approach is to one by one remove all edges and see if removal of a edge causes disconnected graph. Following are steps of simple approach for connected graph.
1) For every edge (u, v), do following
…..a) Remove (u, v) from graph
..…b) See if the graph remains connected (We can either use BFS or DFS)
…..c) Add (u, v) back to the graph.
Time complexity of above method is O(E*(V+E)) for a graph represented using adjacency list. Can we do better?
[ad type=”banner”]
A O(V+E) algorithm to find all Bridges
The idea is similar to O(V+E) algorithm for Articulation Points. We do DFS traversal of the given graph. In DFS tree an edge (u, v) (u is parent of v in DFS tree) is bridge if there does not exit any other alternative to reach u or an ancestor of u from subtree rooted with v. As discussed in the previous post, the value low[v] indicates earliest visited vertex reachable from subtree rooted with v. The condition for an edge (u, v) to be a bridge is, “low[v] > disc[u]”.
[pastacode lang=”python” manual=”%23%20Python%20program%20to%20find%20bridges%20in%20a%20given%20undirected%20graph%0A%23Complexity%20%3A%20O(V%2BE)%0A%20%20%0Afrom%20collections%20import%20defaultdict%0A%20%20%0A%23This%20class%20represents%20an%20undirected%20graph%20using%20adjacency%20list%20representation%0Aclass%20Graph%3A%0A%20%20%0A%20%20%20%20def%20__init__(self%2Cvertices)%3A%0A%20%20%20%20%20%20%20%20self.V%3D%20vertices%20%23No.%20of%20vertices%0A%20%20%20%20%20%20%20%20self.graph%20%3D%20defaultdict(list)%20%23%20default%20dictionary%20to%20store%20graph%0A%20%20%20%20%20%20%20%20self.Time%20%3D%200%0A%20%20%0A%20%20%20%20%23%20function%20to%20add%20an%20edge%20to%20graph%0A%20%20%20%20def%20addEdge(self%2Cu%2Cv)%3A%0A%20%20%20%20%20%20%20%20self.graph%5Bu%5D.append(v)%0A%20%20%20%20%20%20%20%20self.graph%5Bv%5D.append(u)%0A%20%20%0A%20%20%20%20”’A%20recursive%20function%20that%20finds%20and%20prints%20bridges%0A%20%20%20%20using%20DFS%20traversal%0A%20%20%20%20u%20–%3E%20The%20vertex%20to%20be%20visited%20next%0A%20%20%20%20visited%5B%5D%20–%3E%20keeps%20tract%20of%20visited%20vertices%0A%20%20%20%20disc%5B%5D%20–%3E%20Stores%20discovery%20times%20of%20visited%20vertices%0A%20%20%20%20parent%5B%5D%20–%3E%20Stores%20parent%20vertices%20in%20DFS%20tree”’%0A%20%20%20%20def%20bridgeUtil(self%2Cu%2C%20visited%2C%20parent%2C%20low%2C%20disc)%3A%0A%20%0A%20%20%20%20%20%20%20%20%23Count%20of%20children%20in%20current%20node%20%0A%20%20%20%20%20%20%20%20children%20%3D0%0A%20%0A%20%20%20%20%20%20%20%20%23%20Mark%20the%20current%20node%20as%20visited%20and%20print%20it%0A%20%20%20%20%20%20%20%20visited%5Bu%5D%3D%20True%0A%20%0A%20%20%20%20%20%20%20%20%23%20Initialize%20discovery%20time%20and%20low%20value%0A%20%20%20%20%20%20%20%20disc%5Bu%5D%20%3D%20self.Time%0A%20%20%20%20%20%20%20%20low%5Bu%5D%20%3D%20self.Time%0A%20%20%20%20%20%20%20%20self.Time%20%2B%3D%201%0A%20%0A%20%20%20%20%20%20%20%20%23Recur%20for%20all%20the%20vertices%20adjacent%20to%20this%20vertex%0A%20%20%20%20%20%20%20%20for%20v%20in%20self.graph%5Bu%5D%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20If%20v%20is%20not%20visited%20yet%2C%20then%20make%20it%20a%20child%20of%20u%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20in%20DFS%20tree%20and%20recur%20for%20it%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20visited%5Bv%5D%20%3D%3D%20False%20%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20parent%5Bv%5D%20%3D%20u%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20children%20%2B%3D%201%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.bridgeUtil(v%2C%20visited%2C%20parent%2C%20low%2C%20disc)%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20Check%20if%20the%20subtree%20rooted%20with%20v%20has%20a%20connection%20to%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20one%20of%20the%20ancestors%20of%20u%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20low%5Bu%5D%20%3D%20min(low%5Bu%5D%2C%20low%5Bv%5D)%0A%20%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20”’%20If%20the%20lowest%20vertex%20reachable%20from%20subtree%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20under%20v%20is%20below%20u%20in%20DFS%20tree%2C%20then%20u-v%20is%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20a%20bridge”’%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20low%5Bv%5D%20%3E%20disc%5Bu%5D%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20print%20(%22%25d%20%25d%22%20%25(u%2Cv))%0A%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%20%20%20%20elif%20v%20!%3D%20parent%5Bu%5D%3A%20%23%20Update%20low%20value%20of%20u%20for%20parent%20function%20calls.%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20low%5Bu%5D%20%3D%20min(low%5Bu%5D%2C%20disc%5Bv%5D)%0A%20%0A%20%0A%20%20%20%20%23%20DFS%20based%20function%20to%20find%20all%20bridges.%20It%20uses%20recursive%0A%20%20%20%20%23%20function%20bridgeUtil()%0A%20%20%20%20def%20bridge(self)%3A%0A%20%20%0A%20%20%20%20%20%20%20%20%23%20Mark%20all%20the%20vertices%20as%20not%20visited%20and%20Initialize%20parent%20and%20visited%2C%20%0A%20%20%20%20%20%20%20%20%23%20and%20ap(articulation%20point)%20arrays%0A%20%20%20%20%20%20%20%20visited%20%3D%20%5BFalse%5D%20*%20(self.V)%0A%20%20%20%20%20%20%20%20disc%20%3D%20%5Bfloat(%22Inf%22)%5D%20*%20(self.V)%0A%20%20%20%20%20%20%20%20low%20%3D%20%5Bfloat(%22Inf%22)%5D%20*%20(self.V)%0A%20%20%20%20%20%20%20%20parent%20%3D%20%5B-1%5D%20*%20(self.V)%0A%20%0A%20%20%20%20%20%20%20%20%23%20Call%20the%20recursive%20helper%20function%20to%20find%20bridges%0A%20%20%20%20%20%20%20%20%23%20in%20DFS%20tree%20rooted%20with%20vertex%20’i’%0A%20%20%20%20%20%20%20%20for%20i%20in%20range(self.V)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20visited%5Bi%5D%20%3D%3D%20False%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.bridgeUtil(i%2C%20visited%2C%20parent%2C%20low%2C%20disc)%0A%20%20%20%20%20%20%20%20%20%0A%20%20%0A%23%20Create%20a%20graph%20given%20in%20the%20above%20diagram%0Ag1%20%3D%20Graph(5)%0Ag1.addEdge(1%2C%200)%0Ag1.addEdge(0%2C%202)%0Ag1.addEdge(2%2C%201)%0Ag1.addEdge(0%2C%203)%0Ag1.addEdge(3%2C%204)%0A%20%0A%20%20%0Aprint%20%22Bridges%20in%20first%20graph%20%22%0Ag1.bridge()%0A%20%0Ag2%20%3D%20Graph(4)%0Ag2.addEdge(0%2C%201)%0Ag2.addEdge(1%2C%202)%0Ag2.addEdge(2%2C%203)%0Aprint%20%22%5CnBridges%20in%20second%20graph%20%22%0Ag2.bridge()%0A%20%0A%20%20%0Ag3%20%3D%20Graph%20(7)%0Ag3.addEdge(0%2C%201)%0Ag3.addEdge(1%2C%202)%0Ag3.addEdge(2%2C%200)%0Ag3.addEdge(1%2C%203)%0Ag3.addEdge(1%2C%204)%0Ag3.addEdge(1%2C%206)%0Ag3.addEdge(3%2C%205)%0Ag3.addEdge(4%2C%205)%0Aprint%20%22%5CnBridges%20in%20third%20graph%20%22%0Ag3.bridge()%0A%20%0A%20″ message=”” highlight=”” provider=”manual”/]
Output:
Bridges in first graph
3 4
0 3
Bridges in second graph
2 3
1 2
0 1
Bridges in third graph
1 6
[ad type=”banner”]