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
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
I’m Manish - Founder and CTO at Sanfoundry. I’ve been working in tech for over 25 years, with deep focus on Linux kernel, SAN technologies, Advanced C, Full Stack and Scalable website designs.

You can connect with me on LinkedIn, watch my Youtube Masterclasses, or join my Telegram tech discussions.

If you’re in your 40s–60s and exploring new directions in your career, I also offer mentoring. Learn more here.