A biconnected component is a maximal biconnected subgraph.
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.
In above graph, following are the biconnected components:
- 4–2 3–4 3–1 2–3 1–2
- 8–9
- 8–5 7–8 5–7
- 6–0 5–6 1–5 0–1
- 10–11
Algorithm is based on Disc and Low Values discussed in Strongly Connected Components Article.
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.
If there is no Articulation Point in graph, then graph is biconnected and so there will be one biconnected component which is the graph itself.
Java Programming:
[pastacode lang=”java” manual=”%2F%2F%20A%20Java%20program%20to%20find%20biconnected%20components%20in%20a%20given%0A%2F%2F%20undirected%20graph%0Aimport%20java.io.*%3B%0Aimport%20java.util.*%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%2C%20E%3B%20%2F%2F%20No.%20of%20vertices%20%26%20Edges%20respectively%0A%20%20%20%20private%20LinkedList%3CInteger%3E%20adj%5B%5D%3B%20%20%20%20%2F%2F%20Adjacency%20List%0A%20%0A%20%20%20%20%2F%2F%20Count%20is%20number%20of%20biconnected%20components.%20time%20is%0A%20%20%20%20%2F%2F%20used%20to%20find%20discovery%20times%0A%20%20%20%20static%20int%20count%20%3D%200%2C%20time%20%3D%200%3B%0A%20%0A%20%20%20%20class%20Edge%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20int%20u%3B%0A%20%20%20%20%20%20%20%20int%20v%3B%0A%20%20%20%20%20%20%20%20Edge(int%20u%2C%20int%20v)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20this.u%20%3D%20u%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20this.v%20%3D%20v%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%3B%0A%20%0A%20%20%20%20%2F%2FConstructor%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%20E%20%3D%200%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%2Cint%20w)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20adj%5Bv%5D.add(w)%3B%0A%20%20%20%20%20%20%20%20E%2B%2B%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20A%20recursive%20function%20that%20finds%20and%20prints%20strongly%20connected%0A%20%20%20%20%2F%2F%20components%20using%20DFS%20traversal%0A%20%20%20%20%2F%2F%20u%20–%3E%20The%20vertex%20to%20be%20visited%20next%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%20low%5B%5D%20–%20%3E%3E%20earliest%20visited%20vertex%20(the%20vertex%20with%20minimum%0A%20%20%20%20%2F%2F%20%20%20%20%20%20%20%20%20%20%20%20%20discovery%20time)%20that%20can%20be%20reached%20from%20subtree%0A%20%20%20%20%2F%2F%20%20%20%20%20%20%20%20%20%20%20%20%20rooted%20with%20current%20vertex%0A%20%20%20%20%2F%2F%20*st%20–%20%3E%3E%20To%20store%20visited%20edges%0A%20%20%20%20void%20BCCUtil(int%20u%2C%20int%20disc%5B%5D%2C%20int%20low%5B%5D%2C%20LinkedList%3CEdge%3Est%2C%0A%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%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%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%20Go%20through%20all%20vertices%20adjacent%20to%20this%0A%20%20%20%20%20%20%20%20Iterator%3CInteger%3E%20it%20%3D%20adj%5Bu%5D.iterator()%3B%0A%20%20%20%20%20%20%20%20while%20(it.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%20it.next()%3B%20%20%2F%2F%20v%20is%20current%20adjacent%20of%20’u’%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%20recur%20for%20it%0A%20%20%20%20%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%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%20store%20the%20edge%20in%20stack%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20st.add(new%20Edge(u%2Cv))%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20BCCUtil(v%2C%20disc%2C%20low%2C%20st%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%20’v’%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%20’u’%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Case%201%20–%20per%20Strongly%20Connected%20Components%20Article%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20(low%5Bu%5D%20%3E%20low%5Bv%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20low%5Bu%5D%20%3D%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%20u%20is%20an%20articulation%20point%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20pop%20all%20edges%20from%20stack%20till%20u%20–%20v%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20(%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%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%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%20while%20(st.getLast().u%20!%3D%20u%20%7C%7C%20st.getLast().v%20!%3D%20v)%0A%20%20%20%20%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%20%20%20%20%20System.out.print(st.getLast().u%20%2B%20%22–%22%20%2B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20st.getLast().v%20%2B%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%20%20%20%20%20st.removeLast()%3B%0A%20%20%20%20%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%20%20%20%20%20System.out.println(st.getLast().u%20%2B%20%22–%22%20%2B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20st.getLast().v%20%2B%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.removeLast()%3B%0A%20%0A%20%20%20%20%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%20%20%20%20%7D%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%20’u’%20only%20of%20’v’%20is%20still%20in%20stack%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20(i.e.%20it’s%20a%20back%20edge%2C%20not%20cross%20edge).%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Case%202%20–%20per%20Strongly%20Connected%20Components%20Article%0A%20%20%20%20%20%20%20%20%20%20%20%20else%20if%20(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%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20(low%5Bu%5D%3Edisc%5Bv%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20low%5Bu%5D%3Ddisc%5Bv%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20st.add(new%20Edge(u%2Cv))%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%20%7D%0A%20%0A%20%20%20%20%2F%2F%20The%20function%20to%20do%20DFS%20traversal.%20It%20uses%20BCCUtil()%0A%20%20%20%20void%20BCC()%0A%20%20%20%20%7B%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%20%20%20%20%20%20%20LinkedList%3CEdge%3E%20st%20%3D%20new%20LinkedList%3CEdge%3E()%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Initialize%20disc%20and%20low%2C%20and%20parent%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%20disc%5Bi%5D%20%3D%20-1%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20low%5Bi%5D%20%3D%20-1%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20parent%5Bi%5D%20%3D%20-1%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%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%20if%20(disc%5Bi%5D%20%3D%3D%20-1)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20BCCUtil(i%2C%20disc%2C%20low%2C%20st%2C%20parent)%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20int%20j%20%3D%200%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20If%20stack%20is%20not%20empty%2C%20pop%20all%20edges%20from%20stack%0A%20%20%20%20%20%20%20%20%20%20%20%20while%20(st.size()%20%3E%200)%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%20j%20%3D%201%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20System.out.print(st.getLast().u%20%2B%20%22–%22%20%2B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20st.getLast().v%20%2B%20%22%20%22)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20st.removeLast()%3B%0A%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%20if%20(j%20%3D%3D%201)%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%20System.out.println()%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%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%20Graph%20g%20%3D%20new%20Graph(12)%3B%0A%20%20%20%20%20%20%20%20g.addEdge(0%2C1)%3B%0A%20%20%20%20%20%20%20%20g.addEdge(1%2C0)%3B%0A%20%20%20%20%20%20%20%20g.addEdge(1%2C2)%3B%0A%20%20%20%20%20%20%20%20g.addEdge(2%2C1)%3B%0A%20%20%20%20%20%20%20%20g.addEdge(1%2C3)%3B%0A%20%20%20%20%20%20%20%20g.addEdge(3%2C1)%3B%0A%20%20%20%20%20%20%20%20g.addEdge(2%2C3)%3B%0A%20%20%20%20%20%20%20%20g.addEdge(3%2C2)%3B%0A%20%20%20%20%20%20%20%20g.addEdge(2%2C4)%3B%0A%20%20%20%20%20%20%20%20g.addEdge(4%2C2)%3B%0A%20%20%20%20%20%20%20%20g.addEdge(3%2C4)%3B%0A%20%20%20%20%20%20%20%20g.addEdge(4%2C3)%3B%0A%20%20%20%20%20%20%20%20g.addEdge(1%2C5)%3B%0A%20%20%20%20%20%20%20%20g.addEdge(5%2C1)%3B%0A%20%20%20%20%20%20%20%20g.addEdge(0%2C6)%3B%0A%20%20%20%20%20%20%20%20g.addEdge(6%2C0)%3B%0A%20%20%20%20%20%20%20%20g.addEdge(5%2C6)%3B%0A%20%20%20%20%20%20%20%20g.addEdge(6%2C5)%3B%0A%20%20%20%20%20%20%20%20g.addEdge(5%2C7)%3B%0A%20%20%20%20%20%20%20%20g.addEdge(7%2C5)%3B%0A%20%20%20%20%20%20%20%20g.addEdge(5%2C8)%3B%0A%20%20%20%20%20%20%20%20g.addEdge(8%2C5)%3B%0A%20%20%20%20%20%20%20%20g.addEdge(7%2C8)%3B%0A%20%20%20%20%20%20%20%20g.addEdge(8%2C7)%3B%0A%20%20%20%20%20%20%20%20g.addEdge(8%2C9)%3B%0A%20%20%20%20%20%20%20%20g.addEdge(9%2C8)%3B%0A%20%20%20%20%20%20%20%20g.addEdge(10%2C11)%3B%0A%20%20%20%20%20%20%20%20g.addEdge(11%2C10)%3B%0A%20%0A%20%20%20%20%20%20%20%20g.BCC()%3B%0A%20%0A%20%20%20%20%20%20%20%20System.out.println(%22Above%20are%20%22%20%2B%20g.count%20%2B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22%20biconnected%20components%20in%20graph%22)%3B%0A%20%20%20%20%7D%0A%7D%0A%2F%2F%20This%20code%20is%20contributed%20by%20Aakash%20Hasija” message=”” highlight=”” provider=”manual”/]Output:
4--2 3--4 3--1 2--3 1--2 8--9 8--5 7--8 5--7 6--0 5--6 1--5 0--1 10--11 Above are 5 biconnected components in graph[ad type=”banner”]