{"id":26294,"date":"2017-10-26T20:53:30","date_gmt":"2017-10-26T15:23:30","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26294"},"modified":"2017-10-26T20:53:30","modified_gmt":"2017-10-26T15:23:30","slug":"calgorithm-biconnected-components","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/calgorithm-biconnected-components\/","title":{"rendered":"C++ Algorithm &#8211; Biconnected Components"},"content":{"rendered":"<p>A biconnected component is a maximal biconnected subgraph.<span id=\"more-133356\"><\/span><\/p>\n<p>Biconnected Graph is already discussed here. In this article, we will see how to find biconnected component in a graph using algorithm by John Hopcroft and Robert Tarjan.<\/p>\n<p>In above graph, following are the biconnected components:<\/p>\n<ul>\n<li>4\u20132 3\u20134 3\u20131 2\u20133 1\u20132<\/li>\n<li>8\u20139<\/li>\n<li>8\u20135 7\u20138 5\u20137<\/li>\n<li>6\u20130 5\u20136 1\u20135 0\u20131<\/li>\n<li>10\u201311<\/li>\n<\/ul>\n<p>Algorithm is based on Disc and Low Values discussed in Strongly Connected Components Article.<\/p>\n<p>Idea is to store visited edges in a stack while DFS on a graph and keep looking for Articulation Points (highlighted in above figure). As soon as an Articulation Point u is found, all edges visited while DFS from node u onwards will form one biconnected component. When DFS completes for one connected component, all edges present in stack will form a biconnected component.<br \/>\nIf there is no Articulation Point in graph, then graph is biconnected and so there will be one biconnected component which is the graph itself.<\/p>\n[ad type=\u201dbanner\u201d]\n<p><strong>C++ Programming:<\/strong><\/p>\n[pastacode lang=\u201dcpp\u201d manual=\u201d%2F%2F%20A%20C%2B%2B%20program%20to%20find%20biconnected%20components%20in%20a%20given%20undirected%20graph%0A%23include%3Ciostream%3E%0A%23include%20%3Clist%3E%0A%23include%20%3Cstack%3E%0A%23define%20NIL%20-1%0Ausing%20namespace%20std%3B%0Aint%20count%20%3D%200%3B%0Aclass%20Edge%0A%7B%0A%20%20%20%20public%3A%0A%20%20%20%20int%20u%3B%0A%20%20%20%20int%20v%3B%0A%20%20%20%20Edge(int%20u%2C%20int%20v)%3B%0A%7D%3B%0AEdge%3A%3AEdge(int%20u%2C%20int%20v)%0A%7B%0A%20%20%20%20this-%3Eu%20%3D%20u%3B%0A%20%20%20%20this-%3Ev%20%3D%20v%3B%0A%7D%0A%20%20%0A%2F%2F%20A%20class%20that%20represents%20an%20directed%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%20int%20E%3B%20%20%20%20%2F%2F%20No.%20of%20edges%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%0A%20%20%20%20%2F%2F%20A%20Recursive%20DFS%20based%20function%20used%20by%20BCC()%0A%20%20%20%20void%20BCCUtil(int%20u%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%20list%3CEdge%3E%20*st%2C%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%20%20%2F%2F%20function%20to%20add%20an%20edge%20to%20graph%0A%20%20%20%20void%20BCC()%3B%20%20%20%20%2F%2F%20prints%20strongly%20connected%20components%0A%7D%3B%0A%20%20%20%0AGraph%3A%3AGraph(int%20V)%0A%7B%0A%20%20%20%20this-%3EV%20%3D%20V%3B%0A%20%20%20%20this-%3EE%20%3D%200%3B%0A%20%20%20%20adj%20%3D%20new%20list%3Cint%3E%5BV%5D%3B%0A%7D%0A%20%20%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%20E%2B%2B%3B%0A%7D%0A%20%20%20%0A%2F%2F%20A%20recursive%20function%20that%20finds%20and%20prints%20strongly%20connected%0A%2F%2F%20components%20using%20DFS%20traversal%0A%2F%2F%20u%20\u2013%3E%20The%20vertex%20to%20be%20visited%20next%0A%2F%2F%20disc%5B%5D%20\u2013%3E%20Stores%20discovery%20times%20of%20visited%20vertices%0A%2F%2F%20low%5B%5D%20\u2013%20%3E%3E%20earliest%20visited%20vertex%20(the%20vertex%20with%20minimum%0A%2F%2F%20%20%20%20%20%20%20%20%20%20%20%20%20discovery%20time)%20that%20can%20be%20reached%20from%20subtree%0A%2F%2F%20%20%20%20%20%20%20%20%20%20%20%20%20rooted%20with%20current%20vertex%0A%2F%2F%20*st%20\u2013%20%3E%3E%20To%20store%20visited%20edges%0Avoid%20Graph%3A%3ABCCUtil(int%20u%2C%20int%20disc%5B%5D%2C%20int%20low%5B%5D%2C%20list%3CEdge%3E%20*st%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20int%20parent%5B%5D)%0A%7B%0A%20%20%20%20%2F%2F%20A%20static%20variable%20is%20used%20for%20simplicity%2C%20we%20can%20avoid%20use%0A%20%20%20%20%2F%2F%20of%20static%20variable%20by%20passing%20a%20pointer.%0A%20%20%20%20static%20int%20time%20%3D%200%3B%0A%20%20%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%20%20%20int%20children%20%3D%200%3B%0A%20%20%20%0A%20%20%20%20%2F%2F%20Go%20through%20all%20vertices%20adjacent%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%20\u2019u\u2019%0A%20%20%20%0A%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%20if%20(disc%5Bv%5D%20%3D%3D%20-1)%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%20%20%20%20%20%20%20%20%20%20%20%2F%2Fstore%20the%20edge%20in%20stack%0A%20%20%20%20%20%20%20%20%20%20%20%20st-%3Epush_back(Edge(u%2Cv))%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20BCCUtil(v%2C%20disc%2C%20low%2C%20st%2C%20parent)%3B%0A%20%20%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Check%20if%20the%20subtree%20rooted%20with%20\u2019v\u2019%20has%20a%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20connection%20to%20one%20of%20the%20ancestors%20of%20\u2019u\u2019%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Case%201%20\u2013%20per%20Strongly%20Connected%20Components%20Article%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%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2FIf%20u%20is%20an%20articulation%20point%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2Fpop%20all%20edges%20from%20stack%20till%20u%20\u2013%20v%0A%20%20%20%20%20%20%20%20%20%20%20%20if(%20(disc%5Bu%5D%20%3D%3D%201%20%26%26%20children%20%3E%201)%20%7C%7C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20(disc%5Bu%5D%20%3E%201%20%26%26%20low%5Bv%5D%20%3E%3D%20disc%5Bu%5D)%20)%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%20while(st-%3Eback().u%20!%3D%20u%20%7C%7C%20st-%3Eback().v%20!%3D%20v)%0A%20%20%20%20%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%20%20%20%20%20cout%20%3C%3C%20st-%3Eback().u%20%3C%3C%20%22\u2013%22%20%3C%3C%20st-%3Eback().v%20%3C%3C%20%22%20%22%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20st-%3Epop_back()%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20cout%20%3C%3C%20st-%3Eback().u%20%3C%3C%20%22\u2013%22%20%3C%3C%20st-%3Eback().v%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20st-%3Epop_back()%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20cout%20%3C%3C%20endl%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20count%2B%2B%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Update%20low%20value%20of%20\u2019u\u2019%20only%20of%20\u2019v\u2019%20is%20still%20in%20stack%0A%20%20%20%20%20%20%20%20%2F%2F%20(i.e.%20it\u2019s%20a%20back%20edge%2C%20not%20cross%20edge).%0A%20%20%20%20%20%20%20%20%2F%2F%20Case%202%20\u2013%20per%20Strongly%20Connected%20Components%20Article%0A%20%20%20%20%20%20%20%20else%20if(v%20!%3D%20parent%5Bu%5D%20%26%26%20disc%5Bv%5D%20%3C%20low%5Bu%5D)%0A%20%20%20%20%20%20%20%20%7B%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%20%20%20%20%20%20%20%20st-%3Epush_back(Edge(u%2Cv))%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%7D%0A%20%20%20%0A%2F%2F%20The%20function%20to%20do%20DFS%20traversal.%20It%20uses%20BCCUtil()%0Avoid%20Graph%3A%3ABCC()%0A%7B%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%20%20%20list%3CEdge%3E%20*st%20%3D%20new%20list%3CEdge%3E%5BE%5D%3B%0A%20%20%20%0A%20%20%20%20%2F%2F%20Initialize%20disc%20and%20low%2C%20and%20parent%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%20disc%5Bi%5D%20%3D%20NIL%3B%0A%20%20%20%20%20%20%20%20low%5Bi%5D%20%3D%20NIL%3B%0A%20%20%20%20%20%20%20%20parent%5Bi%5D%20%3D%20NIL%3B%0A%20%20%20%20%7D%0A%20%20%20%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%20if%20(disc%5Bi%5D%20%3D%3D%20NIL)%0A%20%20%20%20%20%20%20%20%20%20%20%20BCCUtil(i%2C%20disc%2C%20low%2C%20st%2C%20parent)%3B%0A%20%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20int%20j%20%3D%200%3B%0A%20%20%20%20%20%20%20%20%2F%2FIf%20stack%20is%20not%20empty%2C%20pop%20all%20edges%20from%20stack%0A%20%20%20%20%20%20%20%20while(st-%3Esize()%20%3E%200)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20j%20%3D%201%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20cout%20%3C%3C%20st-%3Eback().u%20%3C%3C%20%22\u2013%22%20%3C%3C%20st-%3Eback().v%20%3C%3C%20%22%20%22%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20st-%3Epop_back()%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20if(j%20%3D%3D%201)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20cout%20%3C%3C%20endl%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20count%2B%2B%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%7D%0A%20%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20function%0Aint%20main()%0A%7B%0A%20%20%20%20Graph%20g(12)%3B%0A%20%20%20%20g.addEdge(0%2C1)%3Bg.addEdge(1%2C0)%3B%0A%20%20%20%20g.addEdge(1%2C2)%3Bg.addEdge(2%2C1)%3B%0A%20%20%20%20g.addEdge(1%2C3)%3Bg.addEdge(3%2C1)%3B%0A%20%20%20%20g.addEdge(2%2C3)%3Bg.addEdge(3%2C2)%3B%0A%20%20%20%20g.addEdge(2%2C4)%3Bg.addEdge(4%2C2)%3B%0A%20%20%20%20g.addEdge(3%2C4)%3Bg.addEdge(4%2C3)%3B%0A%20%20%20%20g.addEdge(1%2C5)%3Bg.addEdge(5%2C1)%3B%0A%20%20%20%20g.addEdge(0%2C6)%3Bg.addEdge(6%2C0)%3B%0A%20%20%20%20g.addEdge(5%2C6)%3Bg.addEdge(6%2C5)%3B%0A%20%20%20%20g.addEdge(5%2C7)%3Bg.addEdge(7%2C5)%3B%0A%20%20%20%20g.addEdge(5%2C8)%3Bg.addEdge(8%2C5)%3B%0A%20%20%20%20g.addEdge(7%2C8)%3Bg.addEdge(8%2C7)%3B%0A%20%20%20%20g.addEdge(8%2C9)%3Bg.addEdge(9%2C8)%3B%0A%20%20%20%20g.addEdge(10%2C11)%3Bg.addEdge(11%2C10)%3B%0A%20%20%20%20g.BCC()%3B%0A%20%20%20%20cout%20%3C%3C%20%22Above%20are%20%22%20%3C%3C%20count%20%3C%3C%20%22%20biconnected%20components%20in%20graph%22%3B%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p><strong>Output:<\/strong><\/p>\n<pre>4--2 3--4 3--1 2--3 1--2\r\n8--9\r\n8--5 7--8 5--7\r\n6--0 5--6 1--5 0--1 \r\n10--11\r\nAbove are 5 biconnected components in graph\r\n<\/pre>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"<p>C++ Algorithm &#8211; Biconnected Components -Graph Algorithm &#8211; A biconnected component is a maximal biconnected subgraph. Biconnected Graph is already discussed <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[83515,1,74168,73906],"tags":[78213,78211,78212,78214,78208,78207,78206,78209,78215,78210,78216],"class_list":["post-26294","post","type-post","status-publish","format-standard","hentry","category-c-programming-3","category-coding","category-dfs-and-bfs","category-graph-algorithms","tag-biconnected-components-and-articulation-points-ppt","tag-biconnected-components-definition","tag-biconnected-components-of-an-undirected-graph","tag-biconnected-components-of-an-undirected-graph-ppt","tag-biconnected-components-pdf","tag-biconnected-graph-example","tag-biconnected-subgraph","tag-biconnectivity-algorithm","tag-biconnectivity-in-data-structure","tag-connected-components-in-daa","tag-what-is-articulation-point"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26294","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=26294"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26294\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26294"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26294"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26294"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}