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.
C++ Programming:
[pastacode lang=”cpp” manual=”%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–%3E%20The%20vertex%20to%20be%20visited%20next%0A%2F%2F%20disc%5B%5D%20–%3E%20Stores%20discovery%20times%20of%20visited%20vertices%0A%2F%2F%20low%5B%5D%20–%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–%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’u’%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’v’%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’u’%0A%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%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–%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–%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–%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’u’%20only%20of%20’v’%20is%20still%20in%20stack%0A%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%2F%2F%20Case%202%20–%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–%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” 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”]