{"id":26885,"date":"2017-12-26T20:36:02","date_gmt":"2017-12-26T15:06:02","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26885"},"modified":"2017-12-26T20:36:02","modified_gmt":"2017-12-26T15:06:02","slug":"c-programming-biconnected-graph","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/c-programming-biconnected-graph\/","title":{"rendered":"C++ programming Biconnected graph"},"content":{"rendered":"<p>An undirected graph is called Biconnected if there are two vertex-disjoint paths between any two vertices. <span id=\"more-118320\"><\/span>In a Biconnected Graph, there is a simple cycle through any two vertices.<br \/>\nBy convention, two nodes connected by an edge form a biconnected graph, but this does not verify the above properties. For a graph with more than two vertices, the above properties must be there for it to be Biconnected.<\/p>\n[ad type=\u201dbanner\u201d]\n<p>Following are some examples.<\/p>\n<p><strong>How to find if a given graph is Biconnected or not?<\/strong><br \/>\n<em>A connected graph is Biconnected if it is connected and doesn\u2019t have any <a href=\"http:\/\/www.geeksforgeeks.org\/articulation-points-or-cut-vertices-in-a-graph\/\">Articulation Point<\/a><\/em>. We mainly need to check two things in a graph.<br \/>\n1) The graph is connected.<br \/>\n2) There is not articulation point in graph.<\/p>\n<p>We start from any vertex and do DFS traversal. In DFS traversal, we check if there is any articulation point. If we don\u2019t find any articulation point, then the graph is Biconnected. Finally, we need to check whether all vertices were reachable in DFS or not. If all vertices were not reachable, then the graph is not even connected.<br \/>\nFollowing is C++ implementation of above approach.<\/p>\n[pastacode lang=\u201dcpp\u201d manual=\u201d%2F%2F%20A%20C%2B%2B%20program%20to%20find%20if%20a%20given%20undirected%20graph%20is%0A%2F%2F%20biconnected%0A%23include%3Ciostream%3E%0A%23include%20%3Clist%3E%0A%23define%20NIL%20-1%0Ausing%20namespace%20std%3B%0A%20%0A%2F%2F%20A%20class%20that%20represents%20an%20undirected%20graph%0Aclass%20Graph%0A%7B%0A%20%20%20%20int%20V%3B%20%20%20%20%2F%2F%20No.%20of%20vertices%0A%20%20%20%20list%3Cint%3E%20*adj%3B%20%20%20%20%2F%2F%20A%20dynamic%20array%20of%20adjacency%20lists%0A%20%20%20%20bool%20isBCUtil(int%20v%2C%20bool%20visited%5B%5D%2C%20int%20disc%5B%5D%2C%20int%20low%5B%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20int%20parent%5B%5D)%3B%0Apublic%3A%0A%20%20%20%20Graph(int%20V)%3B%20%20%20%2F%2F%20Constructor%0A%20%20%20%20void%20addEdge(int%20v%2C%20int%20w)%3B%20%2F%2F%20to%20add%20an%20edge%20to%20graph%0A%20%20%20%20bool%20isBC()%3B%20%20%20%20%2F%2F%20returns%20true%20if%20graph%20is%20Biconnected%0A%7D%3B%0A%20%0AGraph%3A%3AGraph(int%20V)%0A%7B%0A%20%20%20%20this-%3EV%20%3D%20V%3B%0A%20%20%20%20adj%20%3D%20new%20list%3Cint%3E%5BV%5D%3B%0A%7D%0A%20%0Avoid%20Graph%3A%3AaddEdge(int%20v%2C%20int%20w)%0A%7B%0A%20%20%20%20adj%5Bv%5D.push_back(w)%3B%0A%20%20%20%20adj%5Bw%5D.push_back(v)%3B%20%20%2F%2F%20Note%3A%20the%20graph%20is%20undirected%0A%7D%0A%20%0A%2F%2F%20A%20recursive%20function%20that%20returns%20true%20if%20there%20is%20an%20articulation%0A%2F%2F%20point%20in%20given%20graph%2C%20otherwise%20returns%20false.%0A%2F%2F%20This%20function%20is%20almost%20same%20as%20isAPUtil()%20here%20(%20http%3A%2F%2Fgoo.gl%2FMe9Fw%20)%0A%2F%2F%20u%20\u2013%3E%20The%20vertex%20to%20be%20visited%20next%0A%2F%2F%20visited%5B%5D%20\u2013%3E%20keeps%20tract%20of%20visited%20vertices%0A%2F%2F%20disc%5B%5D%20\u2013%3E%20Stores%20discovery%20times%20of%20visited%20vertices%0A%2F%2F%20parent%5B%5D%20\u2013%3E%20Stores%20parent%20vertices%20in%20DFS%20tree%0Abool%20Graph%3A%3AisBCUtil(int%20u%2C%20bool%20visited%5B%5D%2C%20int%20disc%5B%5D%2Cint%20low%5B%5D%2Cint%20parent%5B%5D)%0A%7B%0A%20%20%20%20%2F%2F%20A%20static%20variable%20is%20used%20for%20simplicity%2C%20we%20can%20avoid%20use%20of%20static%0A%20%20%20%20%2F%2F%20variable%20by%20passing%20a%20pointer.%0A%20%20%20%20static%20int%20time%20%3D%200%3B%0A%20%0A%20%20%20%20%2F%2F%20Count%20of%20children%20in%20DFS%20Tree%0A%20%20%20%20int%20children%20%3D%200%3B%0A%20%0A%20%20%20%20%2F%2F%20Mark%20the%20current%20node%20as%20visited%0A%20%20%20%20visited%5Bu%5D%20%3D%20true%3B%0A%20%0A%20%20%20%20%2F%2F%20Initialize%20discovery%20time%20and%20low%20value%0A%20%20%20%20disc%5Bu%5D%20%3D%20low%5Bu%5D%20%3D%20%2B%2Btime%3B%0A%20%0A%20%20%20%20%2F%2F%20Go%20through%20all%20vertices%20aadjacent%20to%20this%0A%20%20%20%20list%3Cint%3E%3A%3Aiterator%20i%3B%0A%20%20%20%20for%20(i%20%3D%20adj%5Bu%5D.begin()%3B%20i%20!%3D%20adj%5Bu%5D.end()%3B%20%2B%2Bi)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20int%20v%20%3D%20*i%3B%20%20%2F%2F%20v%20is%20current%20adjacent%20of%20u%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20If%20v%20is%20not%20visited%20yet%2C%20then%20make%20it%20a%20child%20of%20u%0A%20%20%20%20%20%20%20%20%2F%2F%20in%20DFS%20tree%20and%20recur%20for%20it%0A%20%20%20%20%20%20%20%20if%20(!visited%5Bv%5D)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20children%2B%2B%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20parent%5Bv%5D%20%3D%20u%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20check%20if%20subgraph%20rooted%20with%20v%20has%20an%20articulation%20point%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(isBCUtil(v%2C%20visited%2C%20disc%2C%20low%2C%20parent))%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20true%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Check%20if%20the%20subtree%20rooted%20with%20v%20has%20a%20connection%20to%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20one%20of%20the%20ancestors%20of%20u%0A%20%20%20%20%20%20%20%20%20%20%20%20low%5Bu%5D%20%20%3D%20min(low%5Bu%5D%2C%20low%5Bv%5D)%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20u%20is%20an%20articulation%20point%20in%20following%20cases%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20(1)%20u%20is%20root%20of%20DFS%20tree%20and%20has%20two%20or%20more%20chilren.%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(parent%5Bu%5D%20%3D%3D%20NIL%20%26%26%20children%20%3E%201)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20true%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20(2)%20If%20u%20is%20not%20root%20and%20low%20value%20of%20one%20of%20its%20child%20is%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20more%20than%20discovery%20value%20of%20u.%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(parent%5Bu%5D%20!%3D%20NIL%20%26%26%20low%5Bv%5D%20%3E%3D%20disc%5Bu%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20true%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%0A%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%20else%20if%20(v%20!%3D%20parent%5Bu%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20low%5Bu%5D%20%20%3D%20min(low%5Bu%5D%2C%20disc%5Bv%5D)%3B%0A%20%20%20%20%7D%0A%20%20%20%20return%20false%3B%0A%7D%0A%20%0A%2F%2F%20The%20main%20function%20that%20returns%20true%20if%20graph%20is%20Biconnected%2C%20%0A%2F%2F%20otherwise%20false.%20It%20uses%20recursive%20function%20isBCUtil()%0Abool%20Graph%3A%3AisBC()%0A%7B%0A%20%20%20%20%2F%2F%20Mark%20all%20the%20vertices%20as%20not%20visited%0A%20%20%20%20bool%20*visited%20%3D%20new%20bool%5BV%5D%3B%0A%20%20%20%20int%20*disc%20%3D%20new%20int%5BV%5D%3B%0A%20%20%20%20int%20*low%20%3D%20new%20int%5BV%5D%3B%0A%20%20%20%20int%20*parent%20%3D%20new%20int%5BV%5D%3B%0A%20%0A%20%20%20%20%2F%2F%20Initialize%20parent%20and%20visited%2C%20and%20ap(articulation%20point)%20%0A%20%20%20%20%2F%2F%20%20arrays%0A%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20V%3B%20i%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20parent%5Bi%5D%20%3D%20NIL%3B%0A%20%20%20%20%20%20%20%20visited%5Bi%5D%20%3D%20false%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Call%20the%20recursive%20helper%20function%20to%20find%20if%20there%20is%20an%20articulation%20%0A%20%20%20%20%2F%2F%20point%20in%20given%20graph.%20We%20do%20DFS%20traversal%20starring%20from%20vertex%200%0A%20%20%20%20if%20(isBCUtil(0%2C%20visited%2C%20disc%2C%20low%2C%20parent)%20%3D%3D%20true)%0A%20%20%20%20%20%20%20%20return%20false%3B%0A%20%0A%20%20%20%20%2F%2F%20Now%20check%20whether%20the%20given%20graph%20is%20connected%20or%20not.%20An%20undirected%0A%20%20%20%20%2F%2F%20graph%20is%20connected%20if%20all%20vertices%20are%20reachable%20from%20any%20starting%20%0A%20%20%20%20%2F%2F%20point%20(we%20have%20taken%200%20as%20starting%20point)%0A%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%20if%20(visited%5Bi%5D%20%3D%3D%20false)%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20false%3B%0A%20%0A%20%20%20%20return%20true%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20function%0Aint%20main()%0A%7B%0A%20%20%20%20%2F%2F%20Create%20graphs%20given%20in%20above%20diagrams%0A%20%20%20%20Graph%20g1(2)%3B%0A%20%20%20%20g1.addEdge(0%2C%201)%3B%0A%20%20%20%20g1.isBC()%3F%20cout%20%3C%3C%20%22Yes%5Cn%22%20%3A%20cout%20%3C%3C%20%22No%5Cn%22%3B%0A%20%0A%20%20%20%20Graph%20g2(5)%3B%0A%20%20%20%20g2.addEdge(1%2C%200)%3B%0A%20%20%20%20g2.addEdge(0%2C%202)%3B%0A%20%20%20%20g2.addEdge(2%2C%201)%3B%0A%20%20%20%20g2.addEdge(0%2C%203)%3B%0A%20%20%20%20g2.addEdge(3%2C%204)%3B%0A%20%20%20%20g2.addEdge(2%2C%204)%3B%0A%20%20%20%20g2.isBC()%3F%20cout%20%3C%3C%20%22Yes%5Cn%22%20%3A%20cout%20%3C%3C%20%22No%5Cn%22%3B%0A%20%0A%20%20%20%20Graph%20g3(3)%3B%0A%20%20%20%20g3.addEdge(0%2C%201)%3B%0A%20%20%20%20g3.addEdge(1%2C%202)%3B%0A%20%20%20%20g3.isBC()%3F%20cout%20%3C%3C%20%22Yes%5Cn%22%20%3A%20cout%20%3C%3C%20%22No%5Cn%22%3B%0A%20%0A%20%20%20%20Graph%20g4(5)%3B%0A%20%20%20%20g4.addEdge(1%2C%200)%3B%0A%20%20%20%20g4.addEdge(0%2C%202)%3B%0A%20%20%20%20g4.addEdge(2%2C%201)%3B%0A%20%20%20%20g4.addEdge(0%2C%203)%3B%0A%20%20%20%20g4.addEdge(3%2C%204)%3B%0A%20%20%20%20g4.isBC()%3F%20cout%20%3C%3C%20%22Yes%5Cn%22%20%3A%20cout%20%3C%3C%20%22No%5Cn%22%3B%0A%20%0A%20%20%20%20Graph%20g5(3)%3B%0A%20%20%20%20g5.addEdge(0%2C%201)%3B%0A%20%20%20%20g5.addEdge(1%2C%202)%3B%0A%20%20%20%20g5.addEdge(2%2C%200)%3B%0A%20%20%20%20g5.isBC()%3F%20cout%20%3C%3C%20%22Yes%5Cn%22%20%3A%20cout%20%3C%3C%20%22No%5Cn%22%3B%0A%20%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p>Output:<\/p>\n<pre>Yes\r\nYes\r\nNo\r\nNo\r\nYes<\/pre>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"<p>C++ programming Biconnected graph &#8211; There is a simple cycle through any two vertices.A connected graph is Biconnected if it is connected and doesn\u2019t have <\/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],"tags":[78213,78214,78208,78260,78207,80229,78209,78216],"class_list":["post-26885","post","type-post","status-publish","format-standard","hentry","category-connectivity","category-graph-algorithms","tag-biconnected-components-and-articulation-points-ppt","tag-biconnected-components-of-an-undirected-graph-ppt","tag-biconnected-components-pdf","tag-biconnected-components-ppt","tag-biconnected-graph-example","tag-biconnected-graph-in-data-structure","tag-biconnectivity-algorithm","tag-what-is-articulation-point"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26885","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=26885"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26885\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26885"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26885"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26885"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}