Java Program to Check whether Graph is Biconnected

This Java program is to check whether graph is Biconnected. In graph theory, a biconnected graph is a connected and “nonseparable” graph, meaning that if any vertex were to be removed, the graph will remain connected. Therefore a biconnected graph has no articulation vertices.

Here is the source code of the Java program to check whether graph is biconnected. The Java program is successfully compiled and run on a Linux system. The program output is also shown below.

import java.util.HashSet;
import java.util.InputMismatchException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;
import java.util.Stack;
 
public class BiconnectedGraph
{
    private Queue<Integer> queue;
    private Stack<Integer> stack;
    private int numberOfNodes;
    private Set<Integer> articulationPoints;
    private int[] parent;
    private int[] visited;
    private int[][] adjacencyMatrix;
 
    public BiconnectedGraph(int numberOfNodes)
    {
        queue = new LinkedList<Integer>();
        this.numberOfNodes = numberOfNodes;
        this.stack = new Stack<Integer>();
        this.articulationPoints = new HashSet<Integer>();
        this.parent = new int[numberOfNodes + 1];
        this.visited = new int[numberOfNodes + 1];
        this.adjacencyMatrix = new int[numberOfNodes + 1][numberOfNodes + 1];
    }
 
    private boolean bfs(int adjacency_matrix[][], int source)
    {
        boolean connected = true;
        int number_of_nodes = adjacency_matrix.length - 1;
        int[] visited = new int[number_of_nodes + 1];
        int i, element;
        visited = 1;
        queue.add(source);
        while (!queue.isEmpty())
        {
            element = queue.remove();
            i = element;
            while (i <= number_of_nodes)
            {
                if (adjacency_matrix[element][i] == 1 && visited[i] == 0)
                {
                    queue.add(i);
                    visited[i] = 1;
                }
                i++;
            }
        } 
 
        for (int vertex = 1; vertex <= number_of_nodes; vertex++)
        {   
            if (visited[vertex] == 1)
            {
                continue;
            }else
            {
                connected = false;
                break;
            }
        }
 
        return connected;
    }
 
    private int numberOfArticulationPoint(int adjacencyMatrix[][], int source)
    {
        int children = 0;
        int element, destination;
        stack.push(source);
        visited = 1;
 
        for (int sourceVertex = 1; sourceVertex <= numberOfNodes; sourceVertex++)
        {
            for (int destinationVertex = 1; destinationVertex <= numberOfNodes; destinationVertex++)
            {
                this.adjacencyMatrix[sourceVertex][destinationVertex]
                     = adjacencyMatrix[sourceVertex][destinationVertex];
            }
        }
 
        while (!stack.isEmpty())
        {
            element = stack.peek();
            destination = element;
            while (destination <= numberOfNodes)
            {
                if (this.adjacencyMatrix[element][destination] == 1 && visited[destination] == 0)
                {
                    stack.push(destination);
                    visited[destination] = 1;
                    parent[destination] = element;
                    if (element == source)
                    {
                        children++;
                    }
                    if (!isLeaf(this.adjacencyMatrix, destination))
                    {
                        if (children > 1)
                        {
                            articulationPoints.add(source);
                        }
                        if(isArticulationPoint(this.adjacencyMatrix, destination))
                        {
                            articulationPoints.add(destination);
                        }
                    }
                    element = destination;
                    destination = 1;
                    continue;
                }
                destination++;
            }
            stack.pop();
        }
        return articulationPoints.size();
    }
 
    public boolean isArticulationPoint(int adjacencyMatrix[][], int root)
    {
        int explored[] = new int[numberOfNodes + 1];
        Stack<Integer> stack = new Stack<Integer>();
        stack.push(root);
        int element = 0,destination = 0;
 
        while(!stack.isEmpty())
        {
            element = stack.peek();
            destination = 1;
            while (destination <= numberOfNodes)
            {
                if ( element != root)
                {
                    if (adjacencyMatrix[element][destination] == 1 && visited[destination] == 1)
                    {
                        if (this.stack.contains(destination))
                        {
                            if (destination <= parent[root])
                            {
                                return false;
                            }
                            return true;
                        }
                    }
                }
                if ((adjacencyMatrix[element][destination] == 1 && explored[destination] == 0 )
                       && visited[destination] == 0)
                {
                    stack.push(destination);
                    explored[destination] = 1;
                    adjacencyMatrix[destination][element] = 0;
                    element = destination;
                    destination = 1;
                    continue;
                }
                destination++;
            }
            stack.pop();
        }	
        return true;
    }
 
    private boolean isLeaf(int adjacencyMatrix[][], int node)
    {
        boolean isLeaf = true;
        for (int vertex = 1; vertex <= numberOfNodes; vertex++)
        {
            if (adjacencyMatrix[node][vertex] == 1 && visited[vertex] == 1)
            {
                isLeaf = true;
            }else if (adjacencyMatrix[node][vertex] == 1 && visited[vertex] == 0)
            {
                isLeaf = false;
                break;
            }
        }
        return isLeaf;
    }
 
    public boolean isBiconnected(int adjacencyMatrix[][], int source)
    {
        boolean biconnected = false;
        if (bfs(adjacencyMatrix, source) && numberOfArticulationPoint(adjacencyMatrix, source) == 0)
        { 
            biconnected = true;
        }
        return biconnected;
    } 
 
    public static void main(String... arg)
    {
        int number_of_nodes, source;
        Scanner scanner = null;
        try
        {
            System.out.println("Enter the number of nodes in the graph");
            scanner = new Scanner(System.in);
            number_of_nodes = scanner.nextInt();
 
            int adjacency_matrix[][] = new int[number_of_nodes + 1][number_of_nodes + 1];
            System.out.println("Enter the adjacency matrix");
            for (int i = 1; i <= number_of_nodes; i++)
                for (int j = 1; j <= number_of_nodes; j++)
                    adjacency_matrix[i][j] = scanner.nextInt();
 
            System.out.println("Enter the source for the graph");
            source = scanner.nextInt();
 
            BiconnectedGraph biconnectedGraph = new BiconnectedGraph(number_of_nodes);
            if (biconnectedGraph.isBiconnected(adjacency_matrix, source))
            {
                System.out.println("The Given Graph is BiConnected");
            }else
            {
                System.out.println("The Given Graph is Not BiConnected");
            }
        } catch (InputMismatchException inputMismatch)
        {
            System.out.println("Wrong Input format");
        }
        scanner.close();
    }	
}
$javac BiConnectedGraph.java
$java BiConnectedGraph
Enter the number of nodes in the graph
5
Enter the adjacency matrix
0 1 1 1 0
1 0 1 0 0
1 1 0 0 1
1 0 0 0 1
0 0 1 1 0
Enter the source for the graph
1
The Given Graph is BiConnected

Related posts:

Java Optional as Return Type
Guide to the Java Clock Class
Java Program to Solve Set Cover Problem assuming at max 2 Elements in a Subset
Hướng dẫn Java Design Pattern – Chain of Responsibility
Java Program to Find Shortest Path Between All Vertices Using Floyd-Warshall’s Algorithm
Prevent Cross-Site Scripting (XSS) in a Spring Application
Phân biệt JVM, JRE, JDK
Java Program to Implement Traveling Salesman Problem using Nearest neighbour Algorithm
Java Program to Perform integer Partition for a Specific Case
Java Program to Implement Attribute API
Tính đóng gói (Encapsulation) trong java
Java Program to Perform Preorder Recursive Traversal of a Given Binary Tree
Serve Static Resources with Spring
Java Program to Implement Min Hash
Java Program to Implement Queue using Linked List
Java Program to Implement Ternary Search Tree
Allow user:password in URL
Working With Maps Using Streams
Java Program to Solve Knapsack Problem Using Dynamic Programming
String Operations with Java Streams
Java Program to Implement Adjacency List
Apache Tiles Integration with Spring MVC
Java Program to Compare Binary and Sequential Search
Java Program to Implement Circular Doubly Linked List
Java Program to Implement Hash Tables with Linear Probing
Exploring the New Spring Cloud Gateway
New Features in Java 9
Reactive Flow with MongoDB, Kotlin, and Spring WebFlux
Implementing a Runnable vs Extending a Thread
Java Program to Check the Connectivity of Graph Using BFS
Java Program to Implement Rolling Hash
Setting the Java Version in Maven