Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction 🚀
1.1.
Problem Statement
1.2.
Articulation Points
1.3.
Biconnected Graph
1.4.
Biconnected Components 💡
2.
Algorithm🤖
2.1.
Code Implementation🗒️
2.1.1.
Time complexity
2.1.2.
Space Complexity
3.
Frequently Asked Questions
3.1.
Why an articulation point gives one biconnected component?
3.2.
What is the run time complexity of the DFS algorithm?
3.3.
How to pass arguments by reference?
3.4.
What is a connected component?
3.5.
What is an adjacency list?
4.
Conclusion
Last Updated: Mar 27, 2024
Hard

Biconnected Components in Graph

Author Manish Kumar
1 upvote
Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

 

Introduction 🚀

Hey Ninja!! You have come pretty far reading graphs 🧑‍💻. In the domain of computer science, we always want to build robust systems and make sure that there is no point of failure. Therefore we take extra precautions to make our system fault-proof. Having knowledge of articulation points and biconnected components reduces our risk. 

Biconnected Components in Graph

This article will discuss how to find biconnected components in graphs. We will learn how to apply the idea of articulation points to come up with an algorithm to find biconnected components. 

Problem Statement

Given a graph with V vertices and E edges, your task is to print all the biconnected components present in the graph.
 

For example, look at the graph below:

Input

 

The output for the above graph should be :
 

7–5  8–7 6–8 6–4 5–6 4–5
4–3 2–4 2–0 3–2 1–3 0–1  

Articulation Points

An articulation point is a node in a graph that, when removed, divides the graph into two or more components.

 

Articulation Points

In the above image, the node with value ‘3’ is an articulation point because its removal will break the graph into three separate components.

Biconnected Graph

For any graph to qualify as a biconnected graph, it must satisfy the following constraints:

  • Connected Graph: It means that it is possible to reach any node starting from any random node, i.e. there are no two components without an edge between them.
  • No articulation points: The existence of articulation points makes the graph not biconnected.
     
Biconnected Graph

Biconnected Components 💡

 

A biconnected component is a subgraph which always has a path between two nodes in the component even after removing a node.


For example, the image below shows a graph with two biconnected components:

 

Example

 

Biconnected components can be determined with an algorithm similar to that of finding articulation points. We will go through the algorithm in the section below. 😁
 

Algorithm🤖

Image

Let us go through the steps needed to find biconnected components :

  • Initialise an empty stack to store edges.
  • Run a DFS and look for articulation points.
  • At each node, keep track of low values and discovery time.
  • If an articulation point is found, all the edges visited from this point onwards will form the biconnected component.
  • If there are no articulation points, then the entire graph is one single biconnected component.

Code Implementation🗒️

Image

 

In this section, we will walk through the code implementation in C++. Proper comments are added for ease of understanding:

#include<bits/stdc++.h>
using namespace std;


//graph structure definition
class Graph {
    int Vertices; // vertices count
    int Edges; //number of edges
    vector<int>* adj; //adjacency list
 
   // private helper function to run the dfs
    void helper(int u, vector<int>&discoveryTime, vector<int>&low,
                 stack<pair<int,int>> &stackk, vector<int>&parent){
                     static int time = 0;
 
    discoveryTime[u] = low[u] = ++time;
    int children = 0;
 
        for(auto v:adj[u]){
            
        if (discoveryTime[v] == -1) {
            children++;
            parent[v] = u;
          
            stackk.push({u,v});
            helper(v, discoveryTime, low, stackk, parent);
 
            low[u] = min(low[u], low[v]);
 
            
            if ((discoveryTime[u] == 1 && children > 1) || (discoveryTime[u] > 1 && low[v] >= discoveryTime[u])) {
                while (stackk.top().first != u || stackk.top().second != v) {
                    cout << stackk.top().first << "--" << stackk.top().second << " ";
                    stackk.pop();
                }
                cout << stackk.top().first << "--" << stackk.top().second;
                stackk.pop();
                cout << endl;
            }
        }
 
        else if (v != parent[u]) {
            low[u] = min(low[u], discoveryTime[v]);
            if (discoveryTime[v] < discoveryTime[u]) {
                stackk.push({u,v});
            }
        }
    }
                 }
 
public:
    //constructor to initialise members of the class
    Graph(int V){
        Vertices=V;
        Edges=0;
        adj = new vector<int>[V];
    }
 
    void addEdge(int a, int b){
    adj[a].push_back(b);
    adj[b].push_back(a);
    Edges++;
    } 


   //Function to print biconnected components
    void biconnectedComponents(){
    vector<int>discoveryTime(Vertices,-1);
    vector<int>low(Vertices,-1);
    vector<int>parent(Vertices,-1);
    
    stack<pair<int,int>> stackk;
    for (int i = 0; i < Vertices; i++) {
        if (discoveryTime[i] == -1)
            helper(i, discoveryTime, low, stackk, parent);
 


        while (stackk.size() > 0) {
            cout << stackk.top().first << "--" << stackk.top().second << " ";
            stackk.pop();
        }
        cout<<endl;
    }
    }
};


//main function definition
int main()
{
    Graph g(9);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 3);
    g.addEdge(2, 3);
    g.addEdge(2, 4);
    g.addEdge(3, 4);
    g.addEdge(4, 5);
    g.addEdge(4, 6);
    g.addEdge(5, 6);
    g.addEdge(5, 7);
    g.addEdge(6, 8);
    g.addEdge(7,8);
    g.biconnectedComponents();
    return 0;
}

 

Input Visualisation :

Input

Output:

Output

Time complexity

The time complexity of the above logic is O(V+E). The code runs a simple depth search that goes to each and every element in the adjacency list. Therefore the complexity is O(V+E).
 

Space Complexity

Since, in one instance, all the edges can be in a stack of edges, the space complexity is  O(V).

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

Why an articulation point gives one biconnected component?

The articulation point is the weakest link in a graph, which divides the graph into different components when removed. Thus it is the point from where the biconnected component emerges.

What is the run time complexity of the DFS algorithm?

Depth First Search runs in O(V+E), where V is the number of vertices and E is the number of Edges.

How to pass arguments by reference?

To pass arguments by reference, use the ‘&’ symbol before the parameter declaration in the function signature.

What is a connected component?

A connected component represents a group of nodes that can be visited, starting from any node to any other node belonging to the same connected component. 

What is an adjacency list?

An adjacency list is a 2-D array of dynamic sizes to represent the graph. It can be built using a vector of arrays or vectors. It is the best way to store graphs.

Conclusion

In this blog, we learned how to find biconnected components in a graph. We went through the algorithm and implemented the code. We also analysed the time and space complexities of our code. We hope you enjoyed reading our blog on biconnected components. To read other graph-related topics refer to these pages star graphnodes within k-distanceminimum edges between two vertices etc.

Recommended Problems:

Refer to our Guided Path on Coding Ninjas Studio to upskill ourselves in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem DesignMachine learning, and many more! But suppose we have just started our learning process and are looking for questions from tech giants like Amazon, Microsoft, Uber, etc. In that case, we must look at the problemsinterview experiences, and interview bundles for placement preparations.
 

Nevertheless, we may consider our paid courses to give our career an edge over others!

Do upvote this blog if you find it helpful and engaging!

Happy Learning!!

Previous article
Minimum Edges Required to Make Euler Circuit
Next article
The Seven Bridges of Königsberg
Live masterclass