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:
Spring Boot With H2 Database
Java Program to Encode a Message Using Playfair Cipher
HTTP Authentification and CGI/Servlet
How to Use if/else Logic in Java 8 Streams
A Guide to Queries in Spring Data MongoDB
Java Program to Check if a Directed Graph is a Tree or Not Using DFS
Java Program to Implement Red Black Tree
Java Convenience Factory Methods for Collections
Java Program to Implement Strassen Algorithm
Java Program to Implement ArrayList API
Vòng lặp for, while, do-while trong Java
Java Program to Implement ConcurrentHashMap API
Sorting in Java
Java Program to Implement Queue using Two Stacks
Java Program to Find SSSP (Single Source Shortest Path) in DAG (Directed Acyclic Graphs)
Concurrent Test Execution in Spring 5
An Intro to Spring Cloud Security
Extract links from an HTML page
Lập trình đa luồng với Callable và Future trong Java
The Modulo Operator in Java
Java Program to Solve the 0-1 Knapsack Problem
A Guide to ConcurrentMap
Java Program to Implement Uniform-Cost Search
Java Program to Find the Longest Subsequence Common to All Sequences in a Set of Sequences
Giới thiệu Design Patterns
Java Program to Implement the String Search Algorithm for Short Text Sizes
New in Spring Security OAuth2 – Verify Claims
Spring Boot - Introduction
Wrapper Classes in Java
Hướng dẫn sử dụng luồng vào ra ký tự trong Java
Java Program to Implement Tarjan Algorithm
Java Program to Implement Traveling Salesman Problem using Nearest neighbour Algorithm