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.
Python Programming:
[pastacode lang=”python” manual=”%23%20Python%20program%20to%20find%20biconnected%20components%20in%20a%20given%0A%23%20%20undirected%20graph%0A%23Complexity%20%3A%20O(V%2BE)%0A%20%0A%20%20%0Afrom%20collections%20import%20defaultdict%0A%20%20%0A%23This%20class%20represents%20an%20directed%20graph%20%0A%23%20using%20adjacency%20list%20representation%0Aclass%20Graph%3A%0A%20%20%0A%20%20%20%20def%20__init__(self%2Cvertices)%3A%0A%20%20%20%20%20%20%20%20%23No.%20of%20vertices%0A%20%20%20%20%20%20%20%20self.V%3D%20vertices%20%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%23%20default%20dictionary%20to%20store%20graph%0A%20%20%20%20%20%20%20%20self.graph%20%3D%20defaultdict(list)%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%23%20time%20is%20used%20to%20find%20discovery%20times%0A%20%20%20%20%20%20%20%20self.Time%20%3D%200%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%23%20Count%20is%20number%20of%20biconnected%20components%0A%20%20%20%20%20%20%20%20self.count%20%3D%200%0A%20%20%0A%20%20%20%20%23%20function%20to%20add%20an%20edge%20to%20graph%0A%20%20%20%20def%20addEdge(self%2Cu%2Cv)%3A%0A%20%20%20%20%20%20%20%20self.graph%5Bu%5D.append(v)%20%0A%20%20%20%20%20%20%20%20self.graph%5Bv%5D.append(u)%0A%20%0A%20%20%20%20”’A%20recursive%20function%20that%20finds%20and%20prints%20strongly%20connected%0A%20%20%20%20components%20using%20DFS%20traversal%0A%20%20%20%20u%20–%3E%20The%20vertex%20to%20be%20visited%20next%0A%20%20%20%20disc%5B%5D%20–%3E%20Stores%20discovery%20times%20of%20visited%20vertices%0A%20%20%20%20low%5B%5D%20–%20%3E%3E%20earliest%20visited%20vertex%20(the%20vertex%20with%20minimum%0A%20%20%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%20%20%20%20%20%20%20%20%20%20%20rooted%20with%20current%20vertex%0A%20%20%20%20st%20–%20%3E%3E%20To%20store%20visited%20edges”’%0A%20%20%20%20def%20BCCUtil(self%2Cu%2C%20parent%2C%20low%2C%20disc%2C%20st)%3A%0A%20%0A%20%20%20%20%20%20%20%20%23Count%20of%20children%20in%20current%20node%20%0A%20%20%20%20%20%20%20%20children%20%3D0%0A%20%0A%20%20%20%20%20%20%20%20%23%20Initialize%20discovery%20time%20and%20low%20value%0A%20%20%20%20%20%20%20%20disc%5Bu%5D%20%3D%20self.Time%0A%20%20%20%20%20%20%20%20low%5Bu%5D%20%3D%20self.Time%0A%20%20%20%20%20%20%20%20self.Time%20%2B%3D%201%0A%20%0A%20%0A%20%20%20%20%20%20%20%20%23Recur%20for%20all%20the%20vertices%20adjacent%20to%20this%20vertex%0A%20%20%20%20%20%20%20%20for%20v%20in%20self.graph%5Bu%5D%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%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%23%20in%20DFS%20tree%20and%20recur%20for%20it%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20disc%5Bv%5D%20%3D%3D%20-1%20%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20parent%5Bv%5D%20%3D%20u%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20children%20%2B%3D%201%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20st.append((u%2C%20v))%20%23store%20the%20edge%20in%20stack%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.BCCUtil(v%2C%20parent%2C%20low%2C%20disc%2C%20st)%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23%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%23%20one%20of%20the%20ancestors%20of%20u%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20Case%201%20–%20per%20Strongly%20Connected%20Components%20Article%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20low%5Bu%5D%20%3D%20min(low%5Bu%5D%2C%20low%5Bv%5D)%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20If%20u%20is%20an%20articulation%20point%2Cpop%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20all%20edges%20from%20stack%20till%20(u%2C%20v)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20parent%5Bu%5D%20%3D%3D%20-1%20and%20children%20%3E%201%20or%20parent%5Bu%5D%20!%3D%20-1%20and%20low%5Bv%5D%20%3E%3D%20disc%5Bu%5D%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.count%20%2B%3D1%20%23%20increment%20count%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20w%20%3D%20-1%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20while%20w%20!%3D%20(u%2Cv)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20w%20%3D%20st.pop()%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20print%20w%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20print%22%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%20%20%20%20elif%20v%20!%3D%20parent%5Bu%5D%20and%20low%5Bu%5D%20%3E%20disc%5Bv%5D%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20”’Update%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%20%20%20%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%20%20%20%20Case%202%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20–%20per%20Strongly%20Connected%20Components%20Article”’%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20low%5Bu%5D%20%3D%20min(low%20%5Bu%5D%2C%20disc%5Bv%5D)%0A%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20st.append((u%2Cv))%0A%20%0A%20%0A%20%20%20%20%23The%20function%20to%20do%20DFS%20traversal.%20%0A%20%20%20%20%23%20It%20uses%20recursive%20BCCUtil()%0A%20%20%20%20def%20BCC(self)%3A%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%23%20Initialize%20disc%20and%20low%2C%20and%20parent%20arrays%0A%20%20%20%20%20%20%20%20disc%20%3D%20%5B-1%5D%20*%20(self.V)%0A%20%20%20%20%20%20%20%20low%20%3D%20%5B-1%5D%20*%20(self.V)%0A%20%20%20%20%20%20%20%20parent%20%3D%20%5B-1%5D%20*%20(self.V)%0A%20%20%20%20%20%20%20%20st%20%3D%20%5B%5D%0A%20%0A%20%20%20%20%20%20%20%20%23%20Call%20the%20recursive%20helper%20function%20to%20%0A%20%20%20%20%20%20%20%20%23%20find%20articulation%20points%0A%20%20%20%20%20%20%20%20%23%20in%20DFS%20tree%20rooted%20with%20vertex%20’i’%0A%20%20%20%20%20%20%20%20for%20i%20in%20range(self.V)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20disc%5Bi%5D%20%3D%3D%20-1%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.BCCUtil(i%2C%20parent%2C%20low%2C%20disc%2C%20st)%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%23If%20stack%20is%20not%20empty%2C%20pop%20all%20edges%20from%20stack%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20st%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.count%20%3D%20self.count%20%2B%201%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20while%20st%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20w%20%3D%20st.pop()%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20print%20w%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20print%20%22%22%0A%20%0A%23%20Create%20a%20graph%20given%20in%20the%20above%20diagram%0A%20%0Ag%20%3D%20Graph(12)%0Ag.addEdge(0%2C1)%0Ag.addEdge(1%2C2)%0Ag.addEdge(1%2C3)%0Ag.addEdge(2%2C3)%0Ag.addEdge(2%2C4)%0Ag.addEdge(3%2C4)%0Ag.addEdge(1%2C5)%0Ag.addEdge(0%2C6)%0Ag.addEdge(5%2C6)%0Ag.addEdge(5%2C7)%0Ag.addEdge(5%2C8)%0Ag.addEdge(7%2C8)%0Ag.addEdge(8%2C9)%0Ag.addEdge(10%2C11)%0A%20%0Ag.BCC()%3B%0Aprint%20(%22Above%20are%20%25d%20biconnected%20components%20in%20graph%22%20%25(g.count))%3B%0A%20%0A%23This%20code%20is%20contributed%20by%20Neelam%20Yadav” 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”]