Biconnected Graph

Problem Statement

Now let us understand biconnected components with the help of a program to know if the articulation points and biconnected components.

Explanation 

The graph below is not biconnected since removing the node with value 2 increases the number of connected components. There is no edge connecting nodes 1 and 5, 4 and 6, or any other pair of nodes, for that matter.

An Articulation Point is a node whose removal from the graph increases the number of related components. An articulation point here is represented by the node with value 2 in the graph above.

As mentioned above, node 2(articulation point) is removed and 1st graph is divided into 2 graphs named component 1 and component 2.

Two key aspects of a graph must be examined to determine whether it is biconnected or not:

• The graph is linked, meaning there must be a path connecting any two nodes.
• As shown previously, a biconnected graph has no articulation points. Accordingly, there is no articulation point in the graph.
   

So it is not a Biconnected graph.

Algorithm

In this program, we will look into the Biconnected components in a graph.

Step 1: Take input from the user of nodes and edges as a and b.

Step 2: Take input from the user of the graph. 

Initially, all vertices are unvisited, and the parents of all vertices are null.

Step 3: Initialize time = 1 and initialize an array name visited.

Step 4: Arrays to keep track of a parent, discovery time, low_values

Step 5: Then, a method (printStackTill_UV) for the stack to print till the top of the stack is not equal to the edges.

Step 6: A method(biconnected_graph_values) for graph values,
                 - Then,  Mark, the low_values value of each node as 0
                 - Mark the visited array as false 
                 - Mark, each node of a parent as -1
                 - Mark the discovery time of each node

Step 7: Multiple components may be present in a graph. Hence we must apply DFS Algorithm at each node.

Step 8: Keep track of the low values and discovery times.

Step 9: To keep track of the number of DFS calls made from a source, increase the time mark visited as a true variable.

Step 10: If a neighbor has never visited before, iterate over all of the neighbors' current edges. Identify the parent, Make a DFS call, update the low values time, and push the edge to the stack.

Step 11: Check for the Articulation point. If it's true, then print all edges.

Step 12: If the neighbor is previously visited. Update the low_values value and push the edge to stack.

Step 13: Initiate the for loop from 0 to b and puch_back y and x in graph and print the biconnected components

Pictorial Representation

Step 1: Consider the graph example and perform the dry run to the algorithm:

Step 2: Assume that the source node has the value 1. We begin by sending a DFS request to this node with an empty stack.

• We label Node-1 as visited, set the discovery time and low time to (1, 1), and now we must make a DFS call to one of its unvisited children. 
• Node-1 has two children (Node-3 and Node-4). Therefore let's say a DFS call is made to Node 3.
• The edge from Node-1 to Node-3 is pushed into the stack, and Node 3 is marked visited low time as (2, 2)and with discovery time.
   

The stack now has a single element.

Similarly, for another node,

Step 3: The control is now in the hands of Node-2. It has four children (Node-3, Node-4, Node-5, and Node-6).

• Because Node-3 has already been visited and is the parent of Node-2, we place a DFS call to Node-4. 
• The edge from Node-2 to Node-4 is then pushed into the stack, and Node-4 is marked visited with low time as (4, 4) and discovery time.
   

The stack now has three components,

Step 4: The control is now in the hands of Node-4. It has two children (Node-2 and Node-1), both of which are visited; however, because Node-1 is not the parent node for Node-4, we add the edge from Node-4 to Node-1 into the stack and return to Node-2. Also, because Node-1 has already been visited, we assign a new low[] value to Node-4, which is the low[] value of Node-1. There are now four components in the stack.

Step 5: Now that we're back at Node-2, we make a DFS call to its unvisited offspring, Node-5. Then, Node-5 is tagged as visited with discovery time and low time as (5, 5). In addition, the edge from Node-2 to Node-5 is added to the stack. The stack now has five components.

Step 6: Node-5 is in command; it has two children (Node-2 and Node-5); Node-2 is the parent and has already been visited; we have no business there. The edge from Node-5 to Node-6 is add on to the stack once a DFS call is made to Node-6, which is marked visited with discovery time and low values as (6, 6). The stack now has six elements.

Step 7: The control is now at Node-6, which has two children (Node-2 and Node-5). Node-5 is the parent node and has already been visited, but Node-2 is not the parent node but has already been visited. Therefore we assign Node-6's low value to Node-2's discovery value, which is low[6] = disc[2] => 3. The edge from Node-6 to Node-2 is also added to the stack. The stack now has seven elements.

Step 8: After visiting all of Node-6's children, we return to Node-5, where we notice that the child Node-6 of Node-5 has a lower low[] value than Node-6. We change Node-5's low[] value to Node-6's low[] value. In other words, low[5] = low[6] => 3.

Step 9: We now return to Node-2, where we print out the first biconnected component. Because low[5] >= disc[2], which is a need for Articulation point. We publish the stack's elements till we reach the edge (2-5). This removes three components from the stack and creates the related component seen below.

Implementation in C++

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

class Solution {
private:
    // Discovery time variable starts with one, as shown below.
    int time = 1;
    
    // Visited array initiation
    vector<bool> visited;  
    
    // Arrays to keep track of parent, discovery time, and low_values.          
    vector<int> parent, discovery, low_values;    

    // Make a method to print stack till the top of the stack is 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 biconnected_graph_values(vector<vector<int>>& graph, int& n) 
    {
        // Mark, the low_values value of each node, is 0
        low_values.resize(n+1, 0);
        
        // Mark the visited array as false      
        visited.resize(n+1, false);
        
        // Mark each node as -1 of the parent
        parent.resize(n+1, -1);    
        
        // Mark the discovery time of each node
        discovery.resize(n+1, 0);    
 
        // 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 is not previously visited
            if(visited[i] == false)
            {
                //stack of edges
                stack<pair<int, int>> st; 
                
                // Call DFS
                DFS(i, graph, st);          
 
                // 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) 
    {
        // Mark the low_values time and discovery time
        discovery[src] = low_values[src] = time;
        
        // Increment the time mark visited as a true variable to keep count of DFS call made from the source
        time++;                          
        visited[src] = true;                  
        int child = 0;                  
        
        // Iterate over all neighbors
        vector<int> nbrs = graph[src];  
        for(auto& nbr: nbrs)
        {
            // Current edge if the neighbor is not previously visited
            pair<int, int> edge = {src, nbr};  
            if(visited[nbr] == false) 
            {            
                child += 1;
                
                // Mark the parent
                parent[nbr] = src;
                
                // Push edge to stack
                st.push(edge);  
                
                // Make DFS call              
                DFS(nbr, graph, st);
                
                // Update the low_values time          
                low_values[src] = min(low_values[src], low_values[nbr]);
 
                // Check for Articulation point. If it's true, then print all edges    
                if(parent[src] == -1 and child > 1) {    
                    printStackTill_UV(st, edge);
                    cout<<"Non-Biconnected Component:"<<endl;
                }
    
                // Check for Articulation point. If it's true, then print all edges
                if(parent[src] != -1 and low_values[nbr] >= discovery[src]) {  
                    printStackTill_UV(st, edge);
                    cout<<"Non-Biconnected Component:"<<endl;
                }
            }
            
            // If the neighbor is previously visited.
            else if(parent[src] != nbr and discovery[nbr] < low_values[src]) 
            {  
                // Update the low_values value
                low_values[src] = discovery[nbr];  
                
                // Push edge to stack          
                st.push(edge);  
            }
        }
    }
};

int main()
{
    // Driver code
    cout<<"Input the number of nodes and edges: ";
    int a, b;   
    cin >> a >> b;
    cout<<"Enter the each 2 nodes connected in the graph: "<<endl;
    vector<vector<int>> graph(a+1, vector<int>{});
    for(int i=0; i<b; i++) {
        int x, y;
        cin >> x >> y;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }
    cout<<"Biconnected components are:"<<endl;
    Solution obj;
    obj.biconnected_graph_values(graph, a);
}

You can also try this code with Online C++ Compiler

Run Code

Output

Example for Biconnected Graph:

Example for Non-Biconnected Graph:

Explanation for the above Non-biconnected Graph Output:

Since this graph contains non-biconnected components, it is not a biconnected graph. If a graph contains only biconnected components, we will term it as a biconnected graph according to our code done above.

Time Complexity

The time complexity of the problem "Check if the graph is Biconnceted or not" using the above approach is O(N+E), where N is the number of nodes and E is the number of edges because the node is traversing.

Space Complexity

The space complexity of the problem "Check if the graph is Biconnceted or not" using the above approach is O(N) for taking node N.

Frequently Asked Questions

What is a biconnected graph?

A biconnected undirected graph is a connected graph that is not disjointed by eliminating any one vertex (and its incident edges).

How do you construct a biconnected graph?

There is a simple cycle through any two vertices in a Biconnected Graph. A biconnected graph is formed by two nodes connected by an edge.

Why is the articulation point important in the Biconnected graph?

Articulation points are extremely important for the biconnected components. A graph without an articulation point has only one biconnected component.

What is the time complexity of the Biconnected graph?

The time complexity is O(V + E), the same as the time complexity of the Depth-first search in a graph.

Are the articulation point and the bridge the same thing?

If and only if the root ‘r’ has at least two children in the DFS tree, it is an articulation point. If deleting an edge from the graph (but preserving the vertices) increases the number of connected components, it is referred to be a bridge.

Conclusion

In this blog, we have learned about the biconnected graph and articulation point.

If you found this blog has helped you enhance your knowledge, and if you want to learn more, check out our articles below:

• Balanced Binary Search Trees 
• Rabin Karp Algorithm
• Check if an array represents in order of BST
• The longest common prefix from a suffix array
• Graph Bridge
• Data Structure
   

Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. And also, enroll in our courses and refer to the mock test and problems available. Have a look at the interview experiences and interview bundle for placement preparations.

Happy Coding!!