Java Program to Check whether a Graph is Bipartite using 2 Color Algorithm

«
»
This Java program is to Check whether Graph is a Bipartite using 2 Color Algorithm.In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint sets and such that every edge connects a vertex in to one in ; that is, and are each independent sets.
The two sets and may be thought of as a coloring of the graph with two colors: if one colors all nodes in blue, and all nodes in green, each edge has endpoints of differing colors, as is required in the graph coloring problem.In contrast, such a coloring is impossible in the case of a non-bipartite graph, such as a triangle.

Here is the source code of the Java program to Check whether Graph is a Bipartite using 2 Color Algorithm. The Java program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. import java.util.InputMismatchException;
  2. import java.util.Scanner;
  3. public class CheckBipartite
  4. {
  5.     private int numberOfNodes;
  6.     private static final int NO_OF_COLOR = 2;
  7.  
  8.     private boolean isSafe(int vertex,int[][] adjacencyMatrix, int [] colored, int color)
  9.     {
  10.         for (int destination = 1; destination <= numberOfNodes; destination++)
  11.         {
  12.             if (adjacencyMatrix[vertex][destination] == 1 && colored[destination] == color)
  13.             {
  14.                 return false;
  15.             }
  16.         }
  17.         return true;
  18.     }
  19.  
  20.     private boolean checkBipartiteUtil(int adjacencyMatrix[][], int[] colored, int vertex)
  21.     {
  22.         if (vertex > numberOfNodes)
  23.         {
  24.             return true;
  25.         }
  26.  
  27.         for (int colorNum = 1; colorNum <= NO_OF_COLOR; colorNum++)
  28.         {
  29.             if (isSafe(vertex, adjacencyMatrix, colored, colorNum))
  30.             {
  31.                 colored[vertex] = colorNum;
  32.                 if (checkBipartiteUtil(adjacencyMatrix, colored, vertex + 1))
  33.                 {  
  34.                     return true;
  35.                 }
  36.                 else
  37.                 {
  38.                     return false;
  39.                 }
  40.             }	
  41.         }
  42.         return false;
  43.     }
  44.  
  45.     public boolean checkBipartite(int adjacencyMatrix[][])
  46.     {
  47.         boolean bipartite = true;
  48.         numberOfNodes = adjacencyMatrix[1].length - 1;
  49.         int[] colored = new int[numberOfNodes + 1];
  50.  
  51.         for (int vertex = 1; vertex <= numberOfNodes; vertex++)
  52.         {
  53.             colored[vertex] = 0;
  54.         }
  55.  
  56.         if (!checkBipartiteUtil(adjacencyMatrix, colored, 1))
  57.         {
  58.             bipartite = false;
  59.         }
  60.         return bipartite;
  61.     }
  62.  
  63.     public static void main(String... arg)
  64.     {
  65.         int number_of_nodes;
  66.         Scanner scanner = null;
  67.  
  68.         try
  69.         {
  70.             System.out.println("Enter the number of nodes in the graph");
  71.             scanner = new Scanner(System.in);
  72.             number_of_nodes = scanner.nextInt();
  73.  
  74.             int adjacency_matrix[][] = new int[number_of_nodes + 1][number_of_nodes + 1];
  75.             System.out.println("Enter the adjacency matrix");
  76.             for (int i = 1; i <= number_of_nodes; i++)
  77.             {
  78.                 for (int j = 1; j <= number_of_nodes; j++)
  79.                 {	
  80.                     adjacency_matrix[i][j] = scanner.nextInt();
  81.                 }
  82.             }
  83.  
  84.             for (int i = 1; i <= number_of_nodes; i++)
  85.             {
  86.                 for (int j = 1; j <= number_of_nodes; j++)
  87.                 {	
  88.                     if (adjacency_matrix[i][j] == 1 && adjacency_matrix[j][i] == 0)
  89.                     {
  90.                         adjacency_matrix[j][i] = 1;
  91.                     }
  92.                 }
  93.             }			
  94.  
  95.             CheckBipartite bipartite = new CheckBipartite();
  96.             if (bipartite.checkBipartite(adjacency_matrix))
  97.             {
  98.                 System.out.println("the given graph is bipartite");
  99.             }
  100.             else
  101.             {
  102.                 System.out.println("the given graph is not bipartite");
  103.             }
  104.         }
  105.         catch (InputMismatchException inputMismatch)
  106.         {
  107.             System.out.println("Wrong Input format");
  108.         }
  109.         scanner.close();
  110.     }	
  111. }


$javac CheckBipartite.java
$java CheckBipartite
 
Enter the number of nodes in the graph
6
Enter the adjacency matrix
0 1 0 1 0 1
1 0 1 0 1 0
0 1 0 1 0 1
1 0 1 0 1 0
0 1 0 1 0 1
1 0 1 0 1 0
the given graph is bipartite

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

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

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 & technical discussions at Telegram SanfoundryClasses.