This Java program is to check whether graph is bipartite using bfs. 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. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.

Here is the source code of the Java program to check whether a graph is biparite using bfs. 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.LinkedList;

import java.util.Queue;

import java.util.Scanner;

public class BipartiteBfs

`{`

private int numberOfVertices;

private Queue<Integer> queue;

public static final int NO_COLOR = 0;

public static final int RED = 1;

public static final int BLUE = 2;

public BipartiteBfs(int numberOfVertices)

`{`

this.numberOfVertices = numberOfVertices;

queue = new LinkedList<Integer>();

`}`

public boolean isBipartite(int adjacencyMatrix[][], int source)

`{`

int[] colored = new int[numberOfVertices + 1];

for (int vertex = 1; vertex <= numberOfVertices; vertex++)

`{`

colored[vertex] = NO_COLOR;

`}`

colored[source] = RED;

queue.add(source);

int element, neighbour;

while (!queue.isEmpty())

`{`

element = queue.remove();

neighbour = 1;

while (neighbour <= numberOfVertices)

`{`

if (adjacencyMatrix[element][neighbour] == 1 && colored[element]== colored[neighbour])

`{`

return false;

`}`

if (adjacencyMatrix[element][neighbour] == 1 && colored[neighbour]== NO_COLOR)

`{`

colored[neighbour] = (colored[element] == RED ) ? BLUE :RED;

queue.add(neighbour);

`}`

`neighbour++;`

`}`

`}`

return true;

`}`

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();

`}`

`}`

for (int i = 1; i <= number_of_nodes; i++)

`{`

for (int j = 1; j <= number_of_nodes; j++)

`{`

if(adjacency_matrix[i][j] == 1 && adjacency_matrix[j][i] == 0)

`{`

adjacency_matrix[j][i] = 1;

`}`

`}`

`}`

System.out.println("Enter the source for the graph");

source = scanner.nextInt();

BipartiteBfs bipartiteBfs = new BipartiteBfs(number_of_nodes);

if (bipartiteBfs.isBipartite(adjacency_matrix, source))

`{`

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 BipartiteBfs.java $java BipartiteBfs Enter the number of nodes in the graph 4 Enter the adjacency matrix 0 1 0 1 1 0 1 0 0 1 0 1 1 0 1 0 Enter the source for the graph 1 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.

**Next Steps:**

- Get Free Certificate of Merit in Java Programming
- Participate in Java Programming Certification Contest
- Become a Top Ranker in Java Programming
- Take Java Programming Tests
- Chapterwise Practice Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
- Chapterwise Mock Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

**Related Posts:**

- Buy Java Books
- Practice Information Technology MCQs
- Apply for Information Technology Internship
- Apply for Java Internship
- Buy Programming Books