An undirected graph is called Biconnected if there are two vertex-disjoint paths between any two vertices. In a Biconnected Graph, there is a simple cycle through any two vertices.
By 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.
Following are some examples.
How to find if a given graph is Biconnected or not?
A connected graph is Biconnected if it is connected and doesn’t have any Articulation Point. We mainly need to check two things in a graph.
1) The graph is connected.
2) There is not articulation point in graph.
We start from any vertex and do DFS traversal. In DFS traversal, we check if there is any articulation point. If we don’t 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.
[ad type=”banner”]Java programming:
[pastacode lang=”java” manual=”%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–%3E%20The%20vertex%20to%20be%20visited%20next%0A%20%20%20%20%2F%2F%20visited%5B%5D%20–%3E%20keeps%20tract%20of%20visited%20vertices%0A%20%20%20%20%2F%2F%20disc%5B%5D%20–%3E%20Stores%20discovery%20times%20of%20visited%20vertices%0A%20%20%20%20%2F%2F%20parent%5B%5D%20–%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” message=”” highlight=”” provider=”manual”/]Output:
Yes Yes No No Yes[ad type=”banner”]