Java Program to Check whether Graph is Biconnected or Not

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.

  1. import java.util.HashSet;
  2. import java.util.InputMismatchException;
  3. import java.util.LinkedList;
  4. import java.util.Queue;
  5. import java.util.Scanner;
  6. import java.util.Set;
  7. import java.util.Stack;
  8.  
  9. public class BiconnectedGraph
  10. {
  11.     private Queue<Integer> queue;
  12.     private Stack<Integer> stack;
  13.     private int numberOfNodes;
  14.     private Set<Integer> articulationPoints;
  15.     private int[] parent;
  16.     private int[] visited;
  17.     private int[][] adjacencyMatrix;
  18.  
  19.     public BiconnectedGraph(int numberOfNodes)
  20.     {
  21.         queue = new LinkedList<Integer>();
  22.         this.numberOfNodes = numberOfNodes;
  23.         this.stack = new Stack<Integer>();
  24.         this.articulationPoints = new HashSet<Integer>();
  25.         this.parent = new int[numberOfNodes + 1];
  26.         this.visited = new int[numberOfNodes + 1];
  27.         this.adjacencyMatrix = new int[numberOfNodes + 1][numberOfNodes + 1];
  28.     }
  29.  
  30.     private boolean bfs(int adjacency_matrix[][], int source)
  31.     {
  32.         boolean connected = true;
  33.         int number_of_nodes = adjacency_matrix[source].length - 1;
  34.         int[] visited = new int[number_of_nodes + 1];
  35.         int i, element;
  36.         visited[source] = 1;
  37.         queue.add(source);
  38.         while (!queue.isEmpty())
  39.         {
  40.             element = queue.remove();
  41.             i = element;
  42.             while (i <= number_of_nodes)
  43.             {
  44.                 if (adjacency_matrix[element][i] == 1 && visited[i] == 0)
  45.                 {
  46.                     queue.add(i);
  47.                     visited[i] = 1;
  48.                 }
  49.                 i++;
  50.             }
  51.         } 
  52.  
  53.         for (int vertex = 1; vertex <= number_of_nodes; vertex++)
  54.         {   
  55.             if (visited[vertex] == 1)
  56.             {
  57.                 continue;
  58.             }else
  59.             {
  60.                 connected = false;
  61.                 break;
  62.             }
  63.         }
  64.  
  65.         return connected;
  66.     }
  67.  
  68.     private int numberOfArticulationPoint(int adjacencyMatrix[][], int source)
  69.     {
  70.         int children = 0;
  71.         int element, destination;
  72.         stack.push(source);
  73.         visited[source] = 1;
  74.  
  75.         for (int sourceVertex = 1; sourceVertex <= numberOfNodes; sourceVertex++)
  76.         {
  77.             for (int destinationVertex = 1; destinationVertex <= numberOfNodes; destinationVertex++)
  78.             {
  79.                 this.adjacencyMatrix[sourceVertex][destinationVertex]
  80.                      = adjacencyMatrix[sourceVertex][destinationVertex];
  81.             }
  82.         }
  83.  
  84.         while (!stack.isEmpty())
  85.         {
  86.             element = stack.peek();
  87.             destination = element;
  88.             while (destination <= numberOfNodes)
  89.             {
  90.                 if (this.adjacencyMatrix[element][destination] == 1 && visited[destination] == 0)
  91.                 {
  92.                     stack.push(destination);
  93.                     visited[destination] = 1;
  94.                     parent[destination] = element;
  95.                     if (element == source)
  96.                     {
  97.                         children++;
  98.                     }
  99.                     if (!isLeaf(this.adjacencyMatrix, destination))
  100.                     {
  101.                         if (children > 1)
  102.                         {
  103.                             articulationPoints.add(source);
  104.                         }
  105.                         if(isArticulationPoint(this.adjacencyMatrix, destination))
  106.                         {
  107.                             articulationPoints.add(destination);
  108.                         }
  109.                     }
  110.                     element = destination;
  111.                     destination = 1;
  112.                     continue;
  113.                 }
  114.                 destination++;
  115.             }
  116.             stack.pop();
  117.         }
  118.         return articulationPoints.size();
  119.     }
  120.  
  121.     public boolean isArticulationPoint(int adjacencyMatrix[][], int root)
  122.     {
  123.         int explored[] = new int[numberOfNodes + 1];
  124.         Stack<Integer> stack = new Stack<Integer>();
  125.         stack.push(root);
  126.         int element = 0,destination = 0;
  127.  
  128.         while(!stack.isEmpty())
  129.         {
  130.             element = stack.peek();
  131.             destination = 1;
  132.             while (destination <= numberOfNodes)
  133.             {
  134.                 if ( element != root)
  135.                 {
  136.                     if (adjacencyMatrix[element][destination] == 1 && visited[destination] == 1)
  137.                     {
  138.                         if (this.stack.contains(destination))
  139.                         {
  140.                             if (destination <= parent[root])
  141.                             {
  142.                                 return false;
  143.                             }
  144.                             return true;
  145.                         }
  146.                     }
  147.                 }
  148.                 if ((adjacencyMatrix[element][destination] == 1 && explored[destination] == 0 )
  149.                        && visited[destination] == 0)
  150.                 {
  151.                     stack.push(destination);
  152.                     explored[destination] = 1;
  153.                     adjacencyMatrix[destination][element] = 0;
  154.                     element = destination;
  155.                     destination = 1;
  156.                     continue;
  157.                 }
  158.                 destination++;
  159.             }
  160.             stack.pop();
  161.         }	
  162.         return true;
  163.     }
  164.  
  165.     private boolean isLeaf(int adjacencyMatrix[][], int node)
  166.     {
  167.         boolean isLeaf = true;
  168.         for (int vertex = 1; vertex <= numberOfNodes; vertex++)
  169.         {
  170.             if (adjacencyMatrix[node][vertex] == 1 && visited[vertex] == 1)
  171.             {
  172.                 isLeaf = true;
  173.             }else if (adjacencyMatrix[node][vertex] == 1 && visited[vertex] == 0)
  174.             {
  175.                 isLeaf = false;
  176.                 break;
  177.             }
  178.         }
  179.         return isLeaf;
  180.     }
  181.  
  182.     public boolean isBiconnected(int adjacencyMatrix[][], int source)
  183.     {
  184.         boolean biconnected = false;
  185.         if (bfs(adjacencyMatrix, source) && numberOfArticulationPoint(adjacencyMatrix, source) == 0)
  186.         { 
  187.             biconnected = true;
  188.         }
  189.         return biconnected;
  190.     } 
  191.  
  192.     public static void main(String... arg)
  193.     {
  194.         int number_of_nodes, source;
  195.         Scanner scanner = null;
  196.         try
  197.         {
  198.             System.out.println("Enter the number of nodes in the graph");
  199.             scanner = new Scanner(System.in);
  200.             number_of_nodes = scanner.nextInt();
  201.  
  202.             int adjacency_matrix[][] = new int[number_of_nodes + 1][number_of_nodes + 1];
  203.             System.out.println("Enter the adjacency matrix");
  204.             for (int i = 1; i <= number_of_nodes; i++)
  205.                 for (int j = 1; j <= number_of_nodes; j++)
  206.                     adjacency_matrix[i][j] = scanner.nextInt();
  207.  
  208.             System.out.println("Enter the source for the graph");
  209.             source = scanner.nextInt();
  210.  
  211.             BiconnectedGraph biconnectedGraph = new BiconnectedGraph(number_of_nodes);
  212.             if (biconnectedGraph.isBiconnected(adjacency_matrix, source))
  213.             {
  214.                 System.out.println("The Given Graph is BiConnected");
  215.             }else
  216.             {
  217.                 System.out.println("The Given Graph is Not BiConnected");
  218.             }
  219.         } catch (InputMismatchException inputMismatch)
  220.         {
  221.             System.out.println("Wrong Input format");
  222.         }
  223.         scanner.close();
  224.     }	
  225. }


$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

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement
If you wish to look at all Java Programming examples, go to Java Programs.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.