A bioconnected component
of a graph is a connected subgraph that cannot be broken into disconnected pieces by deleting any single node (and its incident links). An articulation point is a node of a graph whose removal would cause an increase in the number of connected components.
Scope
- This article does not discuss the syntax of writing code in C++ language. Although this article discusses the articulation point, the program to find articulation points in a graph is out of the scope of this article.
Big-O
notation is used to define the time complexity of the algorithms discussed in this article.- Basic knowledge of graph data structure, depth-first search(DFS) technique, articulation points in the graph and how to calculate the time complexity of recursive programs is expected to fully understand this article.
**Before diving into Biconnected components
let’s first understand what is a *Biconnected Graph* and how to check whether a graph is Biconnected or not.**
Takeaways
Complexities of the nim’s game:
Time Complexity
:$O(V + E)$Space Complexity
:$O(V)$
‘v’: No of nodes
‘E’: No of edges
Biconnected Graph
A graph is a Biconnected graph
if:
- There is a path from any node to any other node, i.e. the graph must be connected.
- After removing any node and all the associated edges from the graph, it still remains connected, i.e. there is always a path between any two nodes even after removing any node from the graph.
- For example consider the graphs below,
You can try and remove every possible node from any graph, it always remains connected. And also all of the graphs are one single component, there is a path from any node to any other node.
- Consider the graph shown below, it is not a
Biconnected graph
because if we remove the node withvalue 2
, it increases the number of connected components and there is no edge betweennode 1
andnode 5
, ornode 4
andnode 6
etc.
- A node whose removal from the graph increases the number of connected components is called an Articulation Point. In the above graph, the node with
value 2
is an articulation point. - A graph can contain multiple articulation points. We will also discuss the algorithm to detect the articulation points in a graph.
- To check whether a graph is
Biconnected
or not, we mainly need to check two things in a graph,- The graph is connected, i.e. there must be a path between any two nodes in the graph.
- There is no articulation point in graph, as discussed above that a
Biconnected graph
has no articulation points.
Algorithm to Detect Articulation Point in a Graph
The algorithm to detect the articulation point
in a graph is purely based on depth-first-search(DFS)
which is a common traversal algorithm in graph data structure. Let’s discuss some terminologies that we will be using to detect the articulation point,
- Discovery Time(
disc[node]
): It is the time when a particular node is visited in aDFS
call. It always starts with1
(for the sake of implementation, since all we care about is which node is discovered when) and is incremented by1
as we visit a new node in theDFS
call.- To record the discovery time of each node in the graph we will be using an array
disc[]
of size equal to the number of nodes in the graph. - In the graph below, we assign discovery time to each node if a
DFS
call is made to sourcenode 1
. TheDFS
tree explains the order in which the nodes are visited inDFS
call.
- To record the discovery time of each node in the graph we will be using an array
- Parent Array(
par[node]
): We will also maintain a parent array to keep track of the parent of each node.Parent[i]
for anode i
determines from which node did the DFS call has been made tonode i
. Source node has parent = -1.- In the below graph value written to the side of the node are the parent values of that node.
Node 2
has a parent value equal to1
, which is indeed the node that made the DFS call tonode 2
.Node 2
then made DFS call tonode 5
andnode 3
, that’s why their parent values are2
.
- Lowest Reachable Ancestor(
low[node]
): The low value of a node is the lowest possible discovery time of a previously discovered node if we ignore the currentDFS
path.
- Consider the above graph, if the source node is
1
thenLow[1] = 1
, because it is the first node to be discovered inDFS
callLow[2] = 2
, because there is no other path leading to any other previously discovered node except the current path.Low[3] = 3
, because there is no other path leading to any other previously discovered node except the current path.Low[4] = 1
, because there is a path from node4
to node1
, which is not the current DFS path and is leading to a previously discovered node.Low[5] = 5
, because there is no other path leading to any other previously discovered node except the current path.
Algorithm to find the Articulation Point
- Take a source node and make a DFS call, assign both the
low[]
value anddisc[]
time equal to time, asdisc[]
will not change butlow[]
value might change when we backtrack from a node in DFS call. In graph there are multiple paths to visit the same node and it might affect the discovery time of the node, so to make sure that we always keep the lowestlow[]
time for each node we update thelow[]
value while returning from DFS call. - When we visit a neighbor in the DFS call one of the three conditions will be true,
- If the neighbor is the parent node, then
- Continue to next neighbor, because we don’t want to visit the node again which is already visited and the parent is already visited.
- If the neighbor is not a parent but already visited
- Reassign the low value of the current node with the minimum of
low[]
value of the current node anddisc[]
value of neighbor. low[current_node]
= minimim_of(low[current_node], disc[neighbour])
- The reason why we did this is that there might be a possibility to get a less
low[i]
time for a current nodei
andlow[i]
is the lowest possible discovery time ofnode i
.
- Reassign the low value of the current node with the minimum of
- Neighbour is not visited, of course, not a parent as well
- Make
DFS
call to the neighborDFS(neighbour)
- While returning from
DFS
call, updatelow[]
valuelow[current_node] = minimim_of(low[current_node], low[neighbour])
, same as we discussed in the first step.
- Now it’s time to detect the articulation point
- If the current node is the parent node, (
par[current_node] = -1
), then count the number ofDFS
calls made from the parent. If the count is greater than1
, then the current node is an Articulation point. - Because if it’s a parent node and count of
DFS
calls is greater than1
, then more than1
DFS
call is being made from the source node, which is only possible when source node is the only junction between two components of a graph. - If the current node is not the parent node, then check if (
low[neighbout] >= disc[current_node]
) if this is true then, current node is an Articulation point.
- If the current node is the parent node, (
- Make
- If the neighbor is the parent node, then
Time Complexity of detecting Articulation Points: If you closely observe we are only visiting each node once and in depth-first-search
manner. So the time complexity to detect the articulation points
in a graph is O(V + E)
, which is the same as the time complexity of DFS traversal in a graph. V
is the number of nodes and E
is the number of edges in the graph.
Below is a DFS tree
for the graph along with the discovery time and low value for each node.
Clearly node 2 and it’s neighbour 5, low[5] >= disc[2]
, so that mean node 2 is an Articulation point and our algorithm returns true.
Now let’s head back to Biconnected components
, I promise things will be much easier now.
Biconnected Components
- For a given graph, a
Biconnected Component
is one of its subgraphs that is Biconnected. This means there is always a path between any two nodes in the component, even after removing any node from the component.
For example, for the graph given, it has 2 bioconnected components
.
Biconnected components
in a graph can be easily determined with the help of the same algorithm we used to detect the Articulation point. Remember we return true as soon as we detect an Articulation point, let’s take advantage of this fact.- We maintain a
stack
of edges. Why only stack? because we want quick insertion and deletion operations and stack provides both insertion and deletion in constant time. Each element in the stack will refer to an edgeU -> V
, whereU
is the source andV
is the destination. - Keep adding edges to the stack in the order they are visited and when an articulation point is detected i.e. say a node
U
has a childV
such that no node in the subtree rooted atV
has a back edge (low[V] >= disc[U]
) then pop and print all the edges in the stack till the edgeU-V
is found, as all those edges including the edgeU-V
will form onebiconnected component
.
Example of Biconnected Components Algorithm
- Consider the graph shown below, let’s do a dry run of the algorithm we discussed above.
- Suppose the source node is the node with the value
1
. First, we make a DFS call to this node with an empty stack. We markNode-1
as visited, discovery time, and low time as(1, 1)
and now we have to make a DFS call to one of its unvisited children.Node-1
has two children(Node-4
andNode-3
), suppose DFS call is then made toNode 4
.Node 4
is marked visited with discovery time and low time as(2, 2)
and the edge fromNode-1
toNode-4
is pushed into the stack. The stack now contains one element,
- Now the control is at the
Node-4
. It has two children (Node-1
andNode-2
),Node-1
is already visited so we make DFS call toNode-2
.Node-2
is then marked visited with discovery time and low time as(3, 3)
and the edge fromNode-4
toNode-2
is pushed onto the stack. The stack now contains two elements,
- Now the control is at the
Node-2
. It has four children (Node-4
,Node-3
,Node-5
andNode-6
),Node-4
is already visited and is the parent ofNode-2
so we make DFS call toNode-3
.Node-3
is then marked visited with discovery time and low time as(4, 4)
, and the edge fromNode-2
toNode-3
is pushed into the stack. The stack now contains three elements,
- Now the control is at the node
Node-3
. It has two children (Node-1
andNode-2
), both of the children are visited butNode-1
is not the parent node forNode-3
, so we add the edge fromNode-3
toNode-1
into the stack and backtrack toNode-2
. Also, we assign a newlow[]
value toNode-3
that is thelow[]
value of nodeNode-1
asNode-1
is already visited and not the parent node ofNode-3
. The stack now contains four elements,
- Now we are again at
Node-2
, we make DFS call to its childNode-5
as it is unvisited.Node-5
is then marked visited with discovery time and low time as(5, 5)
. Also, the edge fromNode-2
toNode-5
is pushed into the stack. Stack now contains 5 elements,
- Control is at
Node-5
, it has two children (Node-2
andNode-5
),Node-2
is the parent and already visited we have no business to do there. DFS call is then made toNode-6
it is marked visited with discovery time and low values as(6, 6)
and the edge fromNode-5
toNode-6
is added to the stack. Stack now contains six elements,
- Now the control is at
Node-6
, it has two children(Node-2
andNode-5
).Node-5
is the parent node and already visited butNode-2
is not the parent node but it is already visited, so we mark the low value ofNode-6
to discovery value ofNode-2
that islow[6] = disc[2] => 3
. We also add the edge fromNode-6
toNode-2
into the stack. Stack now contains seven elements,
- Now all the children of
Node-6
are visited, we then backtrack toNode-5
, here we see that the childNode-6
ofNode-5
have lesslow[]
value than theNode-6
. We update thelow[]
value ofNode-5
tolow[]
value ofNode-6
. That is,low[5] = low[6] => 3
.
- Now we backtrack to
Node-2
, this is the moment where we print out first biconnected component. Sincelow[5] >= disc[2]
, which is indeed a condition for Articulation point. We print the elements of the stack until we reach the edge(2-5)
. This pops3
elements from the stack and forms a connected component shown below,
- When all the nodes are visited starting from the source node DFS call return to the source node and finally the
4
elements left in the stack form anotherBiconnected component
. The twoBiconnected components
in the graph are shown below,
Implementation of Biconnected Components in C++
- In the main function, we take input of the number of nodes(
n
) and the number of edges(m
) in the graph. After that, we create the adjacency list to represent the graph. Once we are done with the input work, we create an object of class Solution. - This
sol
object has access to a public method of classSolution
print_biconnected_component()
. We simply call this method passing the graph and the number of nodes. The rest is the same as discussed in the algorithm above.
#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
int time = 1; // discovery time variable, it starts with 1 as discussed above
vector<bool> vis; // visited array
vector<int> par, disc, low; // arrays to keep track for parent, discovery time, low values
private:
// method to print stack till the top of the stack not equal to an edge
void printStackTill_UV(stack<pair<int, int>>& st, pair<int, int>& p) {
while(!st.empty()) {
cout << st.top().first << "-" << st.top().second <<", ";
if(st.top() == p) {
st.pop();
break;
}
st.pop();
}
cout << endl;
}
public:
void print_biconnected_component(vector<vector<int>>& graph, int& n) {
low.resize(n+1, 0); // mark the low value of each node is 0
vis.resize(n+1, false); // mark the visited array as false
par.resize(n+1, -1); // mark the parent of each node as -1
disc.resize(n+1, 0); // mark the discovery time of each node
// greaph can have multiple components, so we need to go to each
// node and apply DFS
for(int i=1; i<=n; i++)
{
// if the current is not previously visited
if(vis[i] == false)
{
stack<pair<int, int>> st; // stack of edges
DFS(i, graph, st); // call DFS
// print the stack when DFS call returns
while(!st.empty()) {
cout << st.top().first << "-" << st.top().second <<", ";
st.pop();
}
}
}
}
void DFS(int src, vector<vector<int>>& graph, stack<pair<int, int>>& st) {
disc[src] = low[src] = time; // mark the low time and discovery time
time++; // increment the time
vis[src] = true; // mark visited as true
int child = 0; // varible to keep count of DFS call made from source
vector<int> nbrs = graph[src]; // iterate over all neighbours
for(auto& nbr: nbrs)
{
pair<int, int> edge = {src, nbr}; // current edge
if(vis[nbr] == false) { // if the neighbour is not previously visited
child += 1;
par[nbr] = src; // mark the parent
st.push(edge); // push edge to stack
DFS(nbr, graph, st); // make DFS call
low[src] = min(low[src], low[nbr]); // update the low time
if(par[src] == -1 and child > 1) { // check for Articulation point, if it's true then print all edges
printStackTill_UV(st, edge);
}
if(par[src] != -1 and low[nbr] >= disc[src]) { // check for Articulation point, if it's true then print all edges
printStackTill_UV(st, edge);
}
}
else if(par[src] != nbr and disc[nbr] < low[src]) { // if the neighbour is previously visited
low[src] = disc[nbr]; // update the low value
st.push(edge); // push edge to stack
}
}
}
};
int main()
{
// Driver code
int n, m; cin >> n >> m;
vector<vector<int>> graph(n+1, vector<int>{});
for(int i=0; i<m; i++) {
int u, v;
cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
}
Solution sol;
sol.print_biconnected_component(graph, n);
}
Implementation of Biconnected Components in Java
import java.util.*;
public class Main{
// Pair class
static class Pair{
int x,y;
Pair(int x,int y){
this.x=x;
this.y=y;
}
}
// Discovery time variable, it starts with 1 as discussed above
static int time;
// Visited Array
static boolean visited[];
// Arrays to keep track for parent,
// discovery time, low values.
static int par[], disc[], low[];
static boolean isEqual(Pair p1, Pair p2){
return p1.x==p2.x&&p1.y==p2.y;
}
// Method to print stack till the top of
// the stack not equal to an edge
static void printStackTill_UV(Stack<Pair> st,
Pair p){
while(!st.isEmpty()){
System.out.print(st.peek().x+" - "+
st.peek().y+" ");
if(isEqual(st.peek(),p)){
st.pop();
break;
}
st.pop();
}
System.out.println();
}
static void printBiConnectedComponents(int n){
// Initialize all the variables like
// 1. time = 1
// 2. low - Array of size n+1 with all entries as 0.
// 3. visited - Boolean array of size n+1 with
// all elements as false
// 4. par - Array of size n+1 with all entries as -1.
time=1;
low=new int[n+1];
visited=new boolean[n+1];
disc=new int[n+1];
par=new int[n+1];
Arrays.fill(par, -1);
// Graph can have multiple components, so
// we need to go to each node and apply DFS
for(int i=1;i<=n;i++){
// If the current node is not previously visited
if(!visited[i]){
// Stack of edges
Stack<Pair> st=new Stack<>();
// Call DFS
DFS(i, st);
// Print the stack when DFS call returns
while(!st.isEmpty()){
System.out.print(st.peek().x+" - "+
st.pop().y+" ");
}
}
}
}
static void DFS(int src, Stack<Pair> st){
// mark the low time and discovery time,
// increment the time and mark src as visited
disc[src]=low[src]=time++;
visited[src]=true;
// Varible to keep count of
// DFS call made from source
int child=0;
// Iterate over all neighbours
for(int nbr:adj.get(src)){
// Current edge
Pair edge=new Pair(src, nbr);
// If the neighbour is not
// unvisited still.
if(!visited[nbr]){
child++;
// Mark the parent.
par[nbr]=src;
// Push into stack.
st.push(edge);
// Make DFS call
DFS(nbr, st);
// Update the low time
low[src]=Math.min(low[src], low[nbr]);
// Check for Articulation point, if it's true
// then print all edges
if((par[src]==-1&&child>1)||
(par[src]!=-1 && low[nbr]>=disc[src]))
printStackTill_UV(st, edge);
} else if(par[src]!=nbr &&
disc[nbr]<low[src]){
// if the neighbour is previously visited
// Update the low value.
low[src]=disc[nbr];
// Push edge to stack.
st.push(edge);
}
}
}
// Adjacency List.
static List<List<Integer>> adj;
// Method to add edge.
static void addEgde(int u, int v){
adj.get(u).add(v);
adj.get(v).add(u);
}
// Drive function.
public static void main(String args[]){
adj=new ArrayList<>();
int V=6;
for(int i=0;i<=V;i++)
adj.add(new ArrayList<>());
/*
Making the following graph
1
/ \
4 3
\ /
2
/ \
5-6
*/
addEgde(1,4);
addEgde(1,3);
addEgde(4,2);
addEgde(3,2);
addEgde(2,5);
addEgde(2,6);
addEgde(5,6);
printBiConnectedComponents(V);
System.out.println();
}
}
Implementation of Biconnected Components in C
using System;
using System.Collections;
using System.Collections.Generic;
public class main{
// Pair class
class Pair{
public int x,y;
public Pair(int x,int y){
this.x=x;
this.y=y;
}
}
// Discovery time variable, it starts with 1 as discussed above
static int time;
// Visited Array
static bool[] visited;
// Arrays to keep track for parent,
// discovery time, low values.
static int[] par;
static int[] disc;
static int[] low;
static bool isEqual(Pair p1, Pair p2){
return p1.x==p2.x&&p1.y==p2.y;
}
// Method to print stack till the top of
// the stack not equal to an edge
static void printStackTill_UV(Stack<Pair> st,
Pair p){
while(st.Count!=0){
Console.Write(st.Peek().x+" - "+
st.Peek().y+" ");
if(isEqual(st.Peek(),p)){
st.Pop();
break;
}
st.Pop();
}
Console.WriteLine();
}
static void printBiConnectedComponents(int n){
// Initialize all the variables like
// 1. time = 1
// 2. low - Array of size n+1 with all entries as 0.
// 3. visited - bool array of size n+1 with
// all elements as false
// 4. par - Array of size n+1 with all entries as -1.
time=1;
low=new int[n+1];
visited=new bool[n+1];
disc=new int[n+1];
par=new int[n+1];
for(int i=0;i<=n;i++)
par[i]=-1;
// Graph can have multiple components, so
// we need to go to each node and apply DFS
for(int i=1;i<=n;i++){
// If the current node is not previously visited
if(!visited[i]){
// Stack of edges
Stack<Pair> st=new Stack<Pair>();
// Call DFS
DFS(i, st);
// Print the stack when DFS call returns
while(st.Count!=0){
Console.Write(st.Peek().x+" - "+
st.Pop().y+" ");
}
}
}
}
static void DFS(int src, Stack<Pair> st){
// mark the low time and discovery time,
// increment the time and mark src as visited
disc[src]=low[src]=time++;
visited[src]=true;
// Varible to keep count of
// DFS call made from source
int child=0;
// Iterate over all neighbours
foreach(int nbr in adj[src]){
// Current edge
Pair edge=new Pair(src, nbr);
// If the neighbour is not
// unvisited still.
if(!visited[nbr]){
child++;
// Mark the parent.
par[nbr]=src;
// Push into stack.
st.Push(edge);
// Make DFS call
DFS(nbr, st);
// Update the low time
low[src]=Math.Min(low[src], low[nbr]);
// Check for Articulation point, if it's true
// then print all edges
if((par[src]==-1&&child>1)||
(par[src]!=-1 && low[nbr]>=disc[src]))
printStackTill_UV(st, edge);
} else if(par[src]!=nbr &&
disc[nbr]<low[src]){
// if the neighbour is previously visited
// Update the low value.
low[src]=disc[nbr];
// Push edge to stack.
st.Push(edge);
}
}
}
// Adjacency List.
static List<List<int>> adj;
// Method to add edge.
static void addEgde(int u, int v){
adj[u].Add(v);
adj[v].Add(u);
}
// Drive function.
public static void Main(){
adj=new List<List<int>>();
int V=6;
for(int i=0;i<=V;i++)
adj.Add(new List<int>());
/*
Making the following graph
1
/ \
4 3
\ /
2
/ \
5-6
*/
addEgde(1,4);
addEgde(1,3);
addEgde(4,2);
addEgde(3,2);
addEgde(2,5);
addEgde(2,6);
addEgde(5,6);
printBiConnectedComponents(V);
Console.WriteLine();
}
}
Output –
6 - 2 5 - 6 2 - 5
3 - 1 2 - 3 4 - 2 1 - 4
- Time Complexity : We are doing no fancy work except the Depth first Search. So the time complexity of this program will be
O(V + E)
, where V is the number of nodes and E is the number of edges. Which is same as the time complexity ofDepth first search
. - Space Complexity : We are using total 5 arrays here namely vis, disc, low, graph, par. So the space complexity is
O(5 * N)
. We also need aO(N)
recursion stack space to makeDFS
calls. N is the number of nodes in the graph.
Conclusion
- For a given graph, a
Biconnected Component
is one of its subgraphs which is Biconnected. A graph can have manybiconnected components
. Biconnected components
are strongly dependent on Articulation points. A graph with no articulation point forms a singlebiconnected component
.- Stack is used along with the algorithm to find the articulation point. We keep on adding the edges into the stack as we visit them in the DFS call until we hit the articulation point.
- Once the articulation point is detected, we pop the edges from the stack till we reach the edge where the parent has lesser or equal discovery time than the neighbor. All of the edges popped till now form a
biconnected component
. - The time complexity is the same as the time complexity of Depth-first search in a graph, that is
O(V + E)
.