{"id":26997,"date":"2018-01-02T20:33:56","date_gmt":"2018-01-02T15:03:56","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26997"},"modified":"2018-01-02T20:33:56","modified_gmt":"2018-01-02T15:03:56","slug":"java-programming-biconnected-graph-2","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/java-programming-biconnected-graph-2\/","title":{"rendered":"JAVA Programming &#8211;  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<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.<\/p>\n[ad type=\u201dbanner\u201d]\n<p>Java programming:<\/p>\n[pastacode lang=\u201djava\u201d manual=\u201d%2F%2F%20A%20Java%20program%20to%20find%20if%20a%20given%20undirected%20graph%20is%0A%2F%2F%20biconnected%0Aimport%20java.io.*%3B%0Aimport%20java.util.*%3B%0Aimport%20java.util.LinkedList%3B%0A%20%0A%2F%2F%20This%20class%20represents%20a%20directed%20graph%20using%20adjacency%0A%2F%2F%20list%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%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%2FFunction%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%2FNote%20that%20the%20graph%20is%20undirected.%0A%20%20%20%20%20%20%20%20adj%5Bw%5D.add(v)%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20A%20recursive%20function%20that%20returns%20true%20if%20there%20is%20an%20articulation%0A%20%20%20%20%2F%2F%20point%20in%20given%20graph%2C%20otherwise%20returns%20false.%0A%20%20%20%20%2F%2F%20This%20function%20is%20almost%20same%20as%20isAPUtil()%20%40%20http%3A%2F%2Fgoo.gl%2FMe9Fw%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%20boolean%20isBCUtil(int%20u%2C%20boolean%20visited%5B%5D%2C%20int%20disc%5B%5D%2Cint%20low%5B%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%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%20of%20u%0A%20%20%20%20%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%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%20children%2B%2B%3B%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%0A%20%20%20%20%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%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%20%20%20%20%20%20return%20true%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%20connection%20to%0A%20%20%20%20%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%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%20u%20is%20an%20articulation%20point%20in%20following%20cases%0A%20%0A%20%20%20%20%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%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%20%20%20%20%20%20return%20true%3B%0A%20%0A%20%20%20%20%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%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20%20child%20is%20more%20than%20discovery%20value%20of%20u.%0A%20%20%20%20%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%20%20%20%20%20%20return%20true%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%20%20%20%20return%20false%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20The%20main%20function%20that%20returns%20true%20if%20graph%20is%20Biconnected%2C%0A%20%20%20%20%2F%2F%20otherwise%20false.%20It%20uses%20recursive%20function%20isBCUtil()%0A%20%20%20%20boolean%20isBC()%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%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%20if%20there%20is%20an%0A%20%20%20%20%20%20%20%20%2F%2F%20articulation%2F%20point%20in%20given%20graph.%20We%20do%20DFS%20traversal%0A%20%20%20%20%20%20%20%20%2F%2F%20starring%20from%20vertex%200%0A%20%20%20%20%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%20%20%20%20%20return%20false%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Now%20check%20whether%20the%20given%20graph%20is%20connected%20or%20not.%0A%20%20%20%20%20%20%20%20%2F%2F%20An%20undirected%20graph%20is%20connected%20if%20all%20vertices%20are%0A%20%20%20%20%20%20%20%20%2F%2F%20reachable%20from%20any%20starting%20point%20(we%20have%20taken%200%20as%0A%20%20%20%20%20%20%20%20%2F%2F%20starting%20point)%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%20return%20false%3B%0A%20%0A%20%20%20%20%20%20%20%20return%20true%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Driver%20method%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%20Graph%20g1%20%3Dnew%20Graph(2)%3B%0A%20%20%20%20%20%20%20%20g1.addEdge(0%2C%201)%3B%0A%20%20%20%20%20%20%20%20if%20(g1.isBC())%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.println(%22Yes%22)%3B%0A%20%20%20%20%20%20%20%20else%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.println(%22No%22)%3B%0A%20%0A%20%20%20%20%20%20%20%20Graph%20g2%20%3Dnew%20Graph(5)%3B%0A%20%20%20%20%20%20%20%20g2.addEdge(1%2C%200)%3B%0A%20%20%20%20%20%20%20%20g2.addEdge(0%2C%202)%3B%0A%20%20%20%20%20%20%20%20g2.addEdge(2%2C%201)%3B%0A%20%20%20%20%20%20%20%20g2.addEdge(0%2C%203)%3B%0A%20%20%20%20%20%20%20%20g2.addEdge(3%2C%204)%3B%0A%20%20%20%20%20%20%20%20g2.addEdge(2%2C%204)%3B%0A%20%20%20%20%20%20%20%20if%20(g2.isBC())%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.println(%22Yes%22)%3B%0A%20%20%20%20%20%20%20%20else%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.println(%22No%22)%3B%0A%20%0A%20%20%20%20%20%20%20%20Graph%20g3%20%3D%20new%20Graph(3)%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%20if%20(g3.isBC())%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.println(%22Yes%22)%3B%0A%20%20%20%20%20%20%20%20else%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.println(%22No%22)%3B%0A%20%0A%20%20%20%20%20%20%20%20Graph%20g4%20%3D%20new%20Graph(5)%3B%0A%20%20%20%20%20%20%20%20g4.addEdge(1%2C%200)%3B%0A%20%20%20%20%20%20%20%20g4.addEdge(0%2C%202)%3B%0A%20%20%20%20%20%20%20%20g4.addEdge(2%2C%201)%3B%0A%20%20%20%20%20%20%20%20g4.addEdge(0%2C%203)%3B%0A%20%20%20%20%20%20%20%20g4.addEdge(3%2C%204)%3B%0A%20%20%20%20%20%20%20%20if%20(g4.isBC())%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.println(%22Yes%22)%3B%0A%20%20%20%20%20%20%20%20else%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.println(%22No%22)%3B%0A%20%0A%20%20%20%20%20%20%20%20Graph%20g5%3D%20new%20Graph(3)%3B%0A%20%20%20%20%20%20%20%20g5.addEdge(0%2C%201)%3B%0A%20%20%20%20%20%20%20%20g5.addEdge(1%2C%202)%3B%0A%20%20%20%20%20%20%20%20g5.addEdge(2%2C%200)%3B%0A%20%20%20%20%20%20%20%20if%20(g5.isBC())%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.println(%22Yes%22)%3B%0A%20%20%20%20%20%20%20%20else%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.println(%22No%22)%3B%0A%20%20%20%20%7D%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>JAVA Programming &#8211; Biconnected graph,An undirected graph is called Biconnected if there are two vertex-disjoint paths between any two vertices.<\/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,78212,78214,78208,80487,80486,80229,78209],"class_list":["post-26997","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","tag-biconnected-components-of-an-undirected-graph-ppt","tag-biconnected-components-pdf","tag-biconnected-directed-graph","tag-biconnected-graph-algorithm","tag-biconnected-graph-in-data-structure","tag-biconnectivity-algorithm"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26997","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=26997"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26997\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26997"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26997"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26997"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}