{"id":27102,"date":"2018-01-03T21:24:07","date_gmt":"2018-01-03T15:54:07","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27102"},"modified":"2018-01-03T21:24:07","modified_gmt":"2018-01-03T15:54:07","slug":"java-programming-bridges-graph","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/java-programming-bridges-graph\/","title":{"rendered":"JAVA programming &#8211; Bridges in a graph"},"content":{"rendered":"<p>An edge in an undirected connected graph is a bridge iff removing it disconnects the graph. <span id=\"more-118009\"><\/span>For a disconnected undirected graph, definition is similar, a bridge is an edge removing which increases number of connected components.<br \/>\nLike <a href=\"http:\/\/www.geeksforgeeks.org\/articulation-points-or-cut-vertices-in-a-graph\/\" target=\"_blank\" rel=\"noopener noreferrer\">Articulation Points<\/a>,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.<\/p>\n<p>Following are some example graphs with bridges highlighted with red color.<\/p>\n<p><strong>How to find all bridges in a given graph?<\/strong><br \/>\nA 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.<\/p>\n<p>1) For every edge (u, v), do following<br \/>\n\u2026..a) Remove (u, v) from graph<br \/>\n..\u2026b) See if the graph remains connected (We can either use BFS or DFS)<br \/>\n\u2026..c) Add (u, v) back to the graph.<\/p>\n<p>Time complexity of above method is O(E*(V+E)) for a graph represented using adjacency list. Can we do better?<\/p>\n[ad type=\u201dbanner\u201d]\n<p><strong>A O(V+E) algorithm to find all Bridges<\/strong><br \/>\nThe idea is similar to <a href=\"http:\/\/www.geeksforgeeks.org\/articulation-points-or-cut-vertices-in-a-graph\/\" target=\"_blank\" rel=\"noopener noreferrer\">O(V+E) algorithm for Articulation Points<\/a>. 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 <a href=\"http:\/\/www.geeksforgeeks.org\/articulation-points-or-cut-vertices-in-a-graph\/\" target=\"_blank\" rel=\"noopener noreferrer\">previous post<\/a>, the value low[v] indicates earliest visited vertex reachable from subtree rooted with v. <em>The condition for an edge (u, v) to be a bridge is, \u201clow[v] > disc[u]\u201d<\/em>.<\/p>\n[pastacode lang=\u201djava\u201d manual=\u201d%2F%2F%20A%20Java%20program%20to%20find%20bridges%20in%20a%20given%20undirected%20graph%0Aimport%20java.io.*%3B%0Aimport%20java.util.*%3B%0Aimport%20java.util.LinkedList%3B%0A%20%0A%2F%2F%20This%20class%20represents%20a%20undirected%20graph%20using%20adjacency%20list%0A%2F%2F%20representation%0Aclass%20Graph%0A%7B%0A%20%20%20%20private%20int%20V%3B%20%20%20%2F%2F%20No.%20of%20vertices%0A%20%0A%20%20%20%20%2F%2F%20Array%20%20of%20lists%20for%20Adjacency%20List%20Representation%0A%20%20%20%20private%20LinkedList%3CInteger%3E%20adj%5B%5D%3B%0A%20%20%20%20int%20time%20%3D%200%3B%0A%20%20%20%20static%20final%20int%20NIL%20%3D%20-1%3B%0A%20%0A%20%20%20%20%2F%2F%20Constructor%0A%20%20%20%20Graph(int%20v)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20V%20%3D%20v%3B%0A%20%20%20%20%20%20%20%20adj%20%3D%20new%20LinkedList%5Bv%5D%3B%0A%20%20%20%20%20%20%20%20for%20(int%20i%3D0%3B%20i%3Cv%3B%20%2B%2Bi)%0A%20%20%20%20%20%20%20%20%20%20%20%20adj%5Bi%5D%20%3D%20new%20LinkedList()%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Function%20to%20add%20an%20edge%20into%20the%20graph%0A%20%20%20%20void%20addEdge(int%20v%2C%20int%20w)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20adj%5Bv%5D.add(w)%3B%20%20%2F%2F%20Add%20w%20to%20v\u2019s%20list.%0A%20%20%20%20%20%20%20%20adj%5Bw%5D.add(v)%3B%20%20%2F%2FAdd%20v%20to%20w\u2019s%20list%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20A%20recursive%20function%20that%20finds%20and%20prints%20bridges%0A%20%20%20%20%2F%2F%20using%20DFS%20traversal%0A%20%20%20%20%2F%2F%20u%20\u2013%3E%20The%20vertex%20to%20be%20visited%20next%0A%20%20%20%20%2F%2F%20visited%5B%5D%20\u2013%3E%20keeps%20tract%20of%20visited%20vertices%0A%20%20%20%20%2F%2F%20disc%5B%5D%20\u2013%3E%20Stores%20discovery%20times%20of%20visited%20vertices%0A%20%20%20%20%2F%2F%20parent%5B%5D%20\u2013%3E%20Stores%20parent%20vertices%20in%20DFS%20tree%0A%20%20%20%20void%20bridgeUtil(int%20u%2C%20boolean%20visited%5B%5D%2C%20int%20disc%5B%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20int%20low%5B%5D%2C%20int%20parent%5B%5D)%0A%20%20%20%20%7B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Count%20of%20children%20in%20DFS%20Tree%0A%20%20%20%20%20%20%20%20int%20children%20%3D%200%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Mark%20the%20current%20node%20as%20visited%0A%20%20%20%20%20%20%20%20visited%5Bu%5D%20%3D%20true%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Initialize%20discovery%20time%20and%20low%20value%0A%20%20%20%20%20%20%20%20disc%5Bu%5D%20%3D%20low%5Bu%5D%20%3D%20%2B%2Btime%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Go%20through%20all%20vertices%20aadjacent%20to%20this%0A%20%20%20%20%20%20%20%20Iterator%3CInteger%3E%20i%20%3D%20adj%5Bu%5D.iterator()%3B%0A%20%20%20%20%20%20%20%20while%20(i.hasNext())%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20int%20v%20%3D%20i.next()%3B%20%20%2F%2F%20v%20is%20current%20adjacent%20of%20u%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20If%20v%20is%20not%20visited%20yet%2C%20then%20make%20it%20a%20child%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20of%20u%20in%20DFS%20tree%20and%20recur%20for%20it.%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20If%20v%20is%20not%20visited%20yet%2C%20then%20recur%20for%20it%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(!visited%5Bv%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20parent%5Bv%5D%20%3D%20u%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20bridgeUtil(v%2C%20visited%2C%20disc%2C%20low%2C%20parent)%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Check%20if%20the%20subtree%20rooted%20with%20v%20has%20a%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20connection%20to%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%20%3D%20Math.min(low%5Bu%5D%2C%20low%5Bv%5D)%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20If%20the%20lowest%20vertex%20reachable%20from%20subtree%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%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%20%2F%2F%20a%20bridge%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20(low%5Bv%5D%20%3E%20disc%5Bu%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20System.out.println(u%2B%22%20%22%2Bv)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Update%20low%20value%20of%20u%20for%20parent%20function%20calls.%0A%20%20%20%20%20%20%20%20%20%20%20%20else%20if%20(v%20!%3D%20parent%5Bu%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20low%5Bu%5D%20%20%3D%20Math.min(low%5Bu%5D%2C%20disc%5Bv%5D)%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%0A%20%20%20%20%2F%2F%20DFS%20based%20function%20to%20find%20all%20bridges.%20It%20uses%20recursive%0A%20%20%20%20%2F%2F%20function%20bridgeUtil()%0A%20%20%20%20void%20bridge()%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Mark%20all%20the%20vertices%20as%20not%20visited%0A%20%20%20%20%20%20%20%20boolean%20visited%5B%5D%20%3D%20new%20boolean%5BV%5D%3B%0A%20%20%20%20%20%20%20%20int%20disc%5B%5D%20%3D%20new%20int%5BV%5D%3B%0A%20%20%20%20%20%20%20%20int%20low%5B%5D%20%3D%20new%20int%5BV%5D%3B%0A%20%20%20%20%20%20%20%20int%20parent%5B%5D%20%3D%20new%20int%5BV%5D%3B%0A%20%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Initialize%20parent%20and%20visited%2C%20and%20ap(articulation%20point)%0A%20%20%20%20%20%20%20%20%2F%2F%20arrays%0A%20%20%20%20%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20V%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20parent%5Bi%5D%20%3D%20NIL%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20visited%5Bi%5D%20%3D%20false%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Call%20the%20recursive%20helper%20function%20to%20find%20Bridges%0A%20%20%20%20%20%20%20%20%2F%2F%20in%20DFS%20tree%20rooted%20with%20vertex%20\u2019i\u2019%0A%20%20%20%20%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20V%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(visited%5Bi%5D%20%3D%3D%20false)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20bridgeUtil(i%2C%20visited%2C%20disc%2C%20low%2C%20parent)%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20public%20static%20void%20main(String%20args%5B%5D)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Create%20graphs%20given%20in%20above%20diagrams%0A%20%20%20%20%20%20%20%20System.out.println(%22Bridges%20in%20first%20graph%20%22)%3B%0A%20%20%20%20%20%20%20%20Graph%20g1%20%3D%20new%20Graph(5)%3B%0A%20%20%20%20%20%20%20%20g1.addEdge(1%2C%200)%3B%0A%20%20%20%20%20%20%20%20g1.addEdge(0%2C%202)%3B%0A%20%20%20%20%20%20%20%20g1.addEdge(2%2C%201)%3B%0A%20%20%20%20%20%20%20%20g1.addEdge(0%2C%203)%3B%0A%20%20%20%20%20%20%20%20g1.addEdge(3%2C%204)%3B%0A%20%20%20%20%20%20%20%20g1.bridge()%3B%0A%20%20%20%20%20%20%20%20System.out.println()%3B%0A%20%0A%20%20%20%20%20%20%20%20System.out.println(%22Bridges%20in%20Second%20graph%22)%3B%0A%20%20%20%20%20%20%20%20Graph%20g2%20%3D%20new%20Graph(4)%3B%0A%20%20%20%20%20%20%20%20g2.addEdge(0%2C%201)%3B%0A%20%20%20%20%20%20%20%20g2.addEdge(1%2C%202)%3B%0A%20%20%20%20%20%20%20%20g2.addEdge(2%2C%203)%3B%0A%20%20%20%20%20%20%20%20g2.bridge()%3B%0A%20%20%20%20%20%20%20%20System.out.println()%3B%0A%20%0A%20%20%20%20%20%20%20%20System.out.println(%22Bridges%20in%20Third%20graph%20%22)%3B%0A%20%20%20%20%20%20%20%20Graph%20g3%20%3D%20new%20Graph(7)%3B%0A%20%20%20%20%20%20%20%20g3.addEdge(0%2C%201)%3B%0A%20%20%20%20%20%20%20%20g3.addEdge(1%2C%202)%3B%0A%20%20%20%20%20%20%20%20g3.addEdge(2%2C%200)%3B%0A%20%20%20%20%20%20%20%20g3.addEdge(1%2C%203)%3B%0A%20%20%20%20%20%20%20%20g3.addEdge(1%2C%204)%3B%0A%20%20%20%20%20%20%20%20g3.addEdge(1%2C%206)%3B%0A%20%20%20%20%20%20%20%20g3.addEdge(3%2C%205)%3B%0A%20%20%20%20%20%20%20%20g3.addEdge(4%2C%205)%3B%0A%20%20%20%20%20%20%20%20g3.bridge()%3B%0A%20%20%20%20%7D%0A%7D\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n[ad type=\u201dbanner\u201d]\nOutput:<\/p>\n<pre>Bridges in first graph\r\n3 4\r\n0 3\r\n\r\nBridges in second graph\r\n2 3\r\n1 2\r\n0 1\r\n\r\nBridges in third graph\r\n1 6<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>JAVA programming &#8211; Bridges in a graph &#8211; An edge in an undirected connected graph is a bridge iff removing it disconnects the graph.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[78385,73906,2139],"tags":[83836,83837,83830,83833,83831,83834,83835,83832],"class_list":["post-27102","post","type-post","status-publish","format-standard","hentry","category-connectivity","category-graph-algorithms","category-java","tag-articulation-point-program-in-c","tag-articulation-point-using-dfs-algorithm","tag-articulation-points-or-cut-vertices-in-a-graph","tag-articulation-points-java","tag-consider-the-following-graph-l-and-find-the-bridges-if-any","tag-cut-vertex-and-bridges","tag-find-all-nodes-in-a-graph-that-remove-any-1-of-them-would-cause-the-graph-to-disconnect","tag-show-how-to-compute-all-the-bridges-of-g-in-oe-time"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27102","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=27102"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27102\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27102"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27102"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27102"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}