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 = 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
Related posts:
Reactive WebSockets with Spring 5
What is Thread-Safety and How to Achieve it?
Reversing a Linked List in Java
Java Program to Compute Cross Product of Two Vectors
Java Program to Apply DFS to Perform the Topological Sorting of a Directed Acyclic Graph
Java – Combine Multiple Collections
Custom JUnit 4 Test Runners
Java Program to Compute the Area of a Triangle Using Determinants
Hướng dẫn Java Design Pattern – Chain of Responsibility
Spring Boot - Exception Handling
Java Program to Implement Splay Tree
How to Add a Single Element to a Stream
Java Program to Implement Tarjan Algorithm
Dynamic Proxies in Java
Serialization và Deserialization trong java
Java Program to Implement Suffix Tree
Converting between an Array and a List in Java
Ignore Null Fields with Jackson
How to Count Duplicate Elements in Arraylist
Immutable ArrayList in Java
Quick Guide on Loading Initial Data with Spring Boot
Java Program to implement Dynamic Array
Entity To DTO Conversion for a Spring REST API
Upload and Display Excel Files with Spring MVC
So sánh ArrayList và Vector trong Java
Spring Webflux and CORS
How to Store Duplicate Keys in a Map in Java?
Java TreeMap vs HashMap
Guide to the Synchronized Keyword in Java
Cơ chế Upcasting và Downcasting trong java
Validations for Enum Types
Java Program to Implement Multi-Threaded Version of Binary Search Tree