# Java Program to Check whether Graph is a 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.

import java.util.InputMismatchException;
import java.util.Scanner;
public class CheckBipartite
{
private int numberOfNodes;
private static final int NO_OF_COLOR = 2;

private boolean isSafe(int vertex,int[][] adjacencyMatrix, int [] colored, int color)
{
for (int destination = 1; destination <= numberOfNodes; destination++)
{
if (adjacencyMatrix[vertex][destination] == 1 && colored[destination] == color)
{
return false;
}
}
return true;
}

private boolean checkBipartiteUtil(int adjacencyMatrix[][], int[] colored, int vertex)
{
if (vertex > numberOfNodes)
{
return true;
}

for (int colorNum = 1; colorNum <= NO_OF_COLOR; colorNum++)
{
{
colored[vertex] = colorNum;
if (checkBipartiteUtil(adjacencyMatrix, colored, vertex + 1))
{
return true;
}
else
{
return false;
}
}
}
return false;
}

{
boolean bipartite = true;
int[] colored = new int[numberOfNodes + 1];

for (int vertex = 1; vertex <= numberOfNodes; vertex++)
{
colored[vertex] = 0;
}

{
bipartite = false;
}
return bipartite;
}

public static void main(String... arg)
{
int number_of_nodes;
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];
for (int i = 1; i <= number_of_nodes; i++)
{
for (int j = 1; j <= number_of_nodes; j++)
{
}
}

for (int i = 1; i <= number_of_nodes; i++)
{
for (int j = 1; j <= number_of_nodes; j++)
{
{
}
}
}

CheckBipartite bipartite = new CheckBipartite();
{
System.out.println("the given graph is bipartite");
}
else
{
System.out.println("the given graph is not bipartite");
}
}
catch (InputMismatchException inputMismatch)
{
System.out.println("Wrong Input format");
}
scanner.close();
}
}


$javac CheckBipartite.java$java CheckBipartite

Enter the number of nodes in the graph
6