Tutorialspoint.dev

Biconnected Components

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.

Biconnected Components

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++

// A C++ program to find biconnected components in a given undirected graph
#include <iostream>
#include <list>
#include <stack>
#define NIL -1
using namespace std;
int count = 0;
class Edge {
public:
    int u;
    int v;
    Edge(int u, int v);
};
Edge::Edge(int u, int v)
{
    this->u = u;
    this->v = v;
}
  
// A class that represents an directed graph
class Graph {
    int V; // No. of vertices
    int E; // No. of edges
    list<int>* adj; // A dynamic array of adjacency lists
  
    // A Recursive DFS based function used by BCC()
    void BCCUtil(int u, int disc[], int low[],
                 list<Edge>* st, int parent[]);
  
public:
    Graph(int V); // Constructor
    void addEdge(int v, int w); // function to add an edge to graph
    void BCC(); // prints strongly connected components
};
  
Graph::Graph(int V)
{
    this->V = V;
    this->E = 0;
    adj = new list<int>[V];
}
  
void Graph::addEdge(int v, int w)
{
    adj[v].push_back(w);
    E++;
}
  
// 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
void Graph::BCCUtil(int u, int disc[], int low[], list<Edge>* st,
                    int parent[])
{
    // A static variable is used for simplicity, we can avoid use
    // of static variable by passing a pointer.
    static int time = 0;
  
    // Initialize discovery time and low value
    disc[u] = low[u] = ++time;
    int children = 0;
  
    // Go through all vertices adjacent to this
    list<int>::iterator i;
    for (i = adj[u].begin(); i != adj[u].end(); ++i) {
        int v = *i; // v is current adjacent of 'u'
  
        // If v is not visited yet, then recur for it
        if (disc[v] == -1) {
            children++;
            parent[v] = u;
            // store the edge in stack
            st->push_back(Edge(u, v));
            BCCUtil(v, disc, low, st, parent);
  
            // 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 ((disc[u] == 1 && children > 1) || (disc[u] > 1 && low[v] >= disc[u])) {
                while (st->back().u != u || st->back().v != v) {
                    cout << st->back().u << "--" << st->back().v << " ";
                    st->pop_back();
                }
                cout << st->back().u << "--" << st->back().v;
                st->pop_back();
                cout << endl;
                count++;
            }
        }
  
        // 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
        else if (v != parent[u]) {
            low[u] = min(low[u], disc[v]);
            if (disc[v] < disc[u]) {
                st->push_back(Edge(u, v));
            }
        }
    }
}
  
// The function to do DFS traversal. It uses BCCUtil()
void Graph::BCC()
{
    int* disc = new int[V];
    int* low = new int[V];
    int* parent = new int[V];
    list<Edge>* st = new list<Edge>[E];
  
    // Initialize disc and low, and parent arrays
    for (int i = 0; i < V; i++) {
        disc[i] = NIL;
        low[i] = NIL;
        parent[i] = NIL;
    }
  
    for (int i = 0; i < V; i++) {
        if (disc[i] == NIL)
            BCCUtil(i, disc, low, st, parent);
  
        int j = 0;
        // If stack is not empty, pop all edges from stack
        while (st->size() > 0) {
            j = 1;
            cout << st->back().u << "--" << st->back().v << " ";
            st->pop_back();
        }
        if (j == 1) {
            cout << endl;
            count++;
        }
    }
}
  
// Driver program to test above function
int main()
{
    Graph g(12);
    g.addEdge(0, 1);
    g.addEdge(1, 0);
    g.addEdge(1, 2);
    g.addEdge(2, 1);
    g.addEdge(1, 3);
    g.addEdge(3, 1);
    g.addEdge(2, 3);
    g.addEdge(3, 2);
    g.addEdge(2, 4);
    g.addEdge(4, 2);
    g.addEdge(3, 4);
    g.addEdge(4, 3);
    g.addEdge(1, 5);
    g.addEdge(5, 1);
    g.addEdge(0, 6);
    g.addEdge(6, 0);
    g.addEdge(5, 6);
    g.addEdge(6, 5);
    g.addEdge(5, 7);
    g.addEdge(7, 5);
    g.addEdge(5, 8);
    g.addEdge(8, 5);
    g.addEdge(7, 8);
    g.addEdge(8, 7);
    g.addEdge(8, 9);
    g.addEdge(9, 8);
    g.addEdge(10, 11);
    g.addEdge(11, 10);
    g.BCC();
    cout << "Above are " << count << " biconnected components in graph";
    return 0;
}

Java

// A Java program to find biconnected components in a given
// undirected graph
import java.io.*;
import java.util.*;
  
// This class represents a directed graph using adjacency
// list representation
class Graph {
    private int V, E; // No. of vertices & Edges respectively
    private LinkedList<Integer> adj[]; // Adjacency List
  
    // Count is number of biconnected components. time is
    // used to find discovery times
    static int count = 0, time = 0;
  
    class Edge {
        int u;
        int v;
        Edge(int u, int v)
        {
            this.u = u;
            this.v = v;
        }
    };
  
    // Constructor
    Graph(int v)
    {
        V = v;
        E = 0;
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i)
            adj[i] = new LinkedList();
    }
  
    // Function to add an edge into the graph
    void addEdge(int v, int w)
    {
        adj[v].add(w);
        E++;
    }
  
    // 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
    void BCCUtil(int u, int disc[], int low[], LinkedList<Edge> st,
                 int parent[])
    {
  
        // Initialize discovery time and low value
        disc[u] = low[u] = ++time;
        int children = 0;
  
        // Go through all vertices adjacent to this
        Iterator<Integer> it = adj[u].iterator();
        while (it.hasNext()) {
            int v = it.next(); // v is current adjacent of 'u'
  
            // If v is not visited yet, then recur for it
            if (disc[v] == -1) {
                children++;
                parent[v] = u;
  
                // store the edge in stack
                st.add(new Edge(u, v));
                BCCUtil(v, disc, low, st, parent);
  
                // Check if the subtree rooted with 'v' has a
                // connection to one of the ancestors of 'u'
                // Case 1 -- per Strongly Connected Components Article
                if (low[u] > low[v])
                    low[u] = low[v];
  
                // If u is an articulation point,
                // pop all edges from stack till u -- v
                if ((disc[u] == 1 && children > 1) || (disc[u] > 1 && low[v] >= disc[u])) {
                    while (st.getLast().u != u || st.getLast().v != v) {
                        System.out.print(st.getLast().u + "--" + st.getLast().v + " ");
                        st.removeLast();
                    }
                    System.out.println(st.getLast().u + "--" + st.getLast().v + " ");
                    st.removeLast();
  
                    count++;
                }
            }
  
            // Update low value of 'u' only if 'v' is still in stack
            // (i.e. it's a back edge, not cross edge).
            // Case 2 -- per Strongly Connected Components Article
            else if (v != parent[u] && disc[v] < disc[u] ) {
                if (low[u] > disc[v])
                    low[u] = disc[v];
  
                st.add(new Edge(u, v));
            }
        }
    }
  
    // The function to do DFS traversal. It uses BCCUtil()
    void BCC()
    {
        int disc[] = new int[V];
        int low[] = new int[V];
        int parent[] = new int[V];
        LinkedList<Edge> st = new LinkedList<Edge>();
  
        // Initialize disc and low, and parent arrays
        for (int i = 0; i < V; i++) {
            disc[i] = -1;
            low[i] = -1;
            parent[i] = -1;
        }
  
        for (int i = 0; i < V; i++) {
            if (disc[i] == -1)
                BCCUtil(i, disc, low, st, parent);
  
            int j = 0;
  
            // If stack is not empty, pop all edges from stack
            while (st.size() > 0) {
                j = 1;
                System.out.print(st.getLast().u + "--" + st.getLast().v + " ");
                st.removeLast();
            }
            if (j == 1) {
                System.out.println();
                count++;
            }
        }
    }
  
    public static void main(String args[])
    {
        Graph g = new Graph(12);
        g.addEdge(0, 1);
        g.addEdge(1, 0);
        g.addEdge(1, 2);
        g.addEdge(2, 1);
        g.addEdge(1, 3);
        g.addEdge(3, 1);
        g.addEdge(2, 3);
        g.addEdge(3, 2);
        g.addEdge(2, 4);
        g.addEdge(4, 2);
        g.addEdge(3, 4);
        g.addEdge(4, 3);
        g.addEdge(1, 5);
        g.addEdge(5, 1);
        g.addEdge(0, 6);
        g.addEdge(6, 0);
        g.addEdge(5, 6);
        g.addEdge(6, 5);
        g.addEdge(5, 7);
        g.addEdge(7, 5);
        g.addEdge(5, 8);
        g.addEdge(8, 5);
        g.addEdge(7, 8);
        g.addEdge(8, 7);
        g.addEdge(8, 9);
        g.addEdge(9, 8);
        g.addEdge(10, 11);
        g.addEdge(11, 10);
  
        g.BCC();
  
        System.out.println("Above are " + g.count + " biconnected components in graph");
    }
}
// This code is contributed by Aakash Hasija

Python

# 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));
  
# This code is contributed by Neelam Yadav

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


This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter