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
[ad type=”banner”]

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:

# Python program to find biconnected components in a given
#  undirected graph
#Complexity : O(V+E)
 
  
from collections import defaultdict
  
#This class represents an directed graph 
# using adjacency list representation
class Graph:
  
    def __init__(self,vertices):
        #No. of vertices
        self.V= vertices 
         
        # default dictionary to store graph
        self.graph = defaultdict(list)
         
        # time is used to find discovery times
        self.Time = 0
         
        # Count is number of biconnected components
        self.count = 0
  
    # function to add an edge to graph
    def addEdge(self,u,v):
        self.graph[u].append(v) 
        self.graph[v].append(u)
 
    '''A recursive function that finds and prints strongly connected
    components using DFS traversal
    u --> The vertex to be visited next
    disc[] --> Stores discovery times of visited vertices
    low[] -- >> earliest visited vertex (the vertex with minimum
               discovery time) that can be reached from subtree
               rooted with current vertex
    st -- >> To store visited edges'''
    def BCCUtil(self,u, parent, low, disc, st):
 
        #Count of children in current node 
        children =0
 
        # Initialize discovery time and low value
        disc[u] = self.Time
        low[u] = self.Time
        self.Time += 1
 
 
        #Recur for all the vertices adjacent to this vertex
        for v in self.graph[u]:
            # If v is not visited yet, then make it a child of u
            # in DFS tree and recur for it
            if disc[v] == -1 :
                parent[v] = u
                children += 1
                st.append((u, v)) #store the edge in stack
                self.BCCUtil(v, parent, low, disc, st)
 
                # Check if the subtree rooted with v has a connection to
                # one of the ancestors of u
                # Case 1 -- per Strongly Connected Components Article
                low[u] = min(low[u], low[v])
 
                # If u is an articulation point,pop 
                # all edges from stack till (u, v)
                if parent[u] == -1 and children > 1 or parent[u] != -1 and low[v] >= disc[u]:
                    self.count +=1 # increment count
                    w = -1
                    while w != (u,v):
                        w = st.pop()
                        print w,
                    print""
             
            elif v != parent[u] and low[u] > disc[v]:
                '''Update low value of 'u' only of 'v' is still in stack
                (i.e. it's a back edge, not cross edge).
                Case 2 
                -- per Strongly Connected Components Article'''
 
                low[u] = min(low [u], disc[v])
     
                st.append((u,v))
 
 
    #The function to do DFS traversal. 
    # It uses recursive BCCUtil()
    def BCC(self):
         
        # Initialize disc and low, and parent arrays
        disc = [-1] * (self.V)
        low = [-1] * (self.V)
        parent = [-1] * (self.V)
        st = []
 
        # Call the recursive helper function to 
        # find articulation points
        # in DFS tree rooted with vertex 'i'
        for i in range(self.V):
            if disc[i] == -1:
                self.BCCUtil(i, parent, low, disc, st)
 
            #If stack is not empty, pop all edges from stack
            if st:
                self.count = self.count + 1
 
                while st:
                    w = st.pop()
                    print w,
                print ""
 
# Create a graph given in the above diagram
 
g = Graph(12)
g.addEdge(0,1)
g.addEdge(1,2)
g.addEdge(1,3)
g.addEdge(2,3)
g.addEdge(2,4)
g.addEdge(3,4)
g.addEdge(1,5)
g.addEdge(0,6)
g.addEdge(5,6)
g.addEdge(5,7)
g.addEdge(5,8)
g.addEdge(7,8)
g.addEdge(8,9)
g.addEdge(10,11)
 
g.BCC();
print ("Above are %d biconnected components in graph" %(g.count));
[ad type=”banner”]

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

Categorized in:

CodingConnectivityGraph Algorithms

Tagged in:

, , , , , , ,