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:
Các nguyên lý thiết kế hướng đối tượng – SOLID
Jackson Annotation Examples
Dynamic Proxies in Java
Jackson – Marshall String to JsonNode
Comparing Long Values in Java
Marker Interface trong Java
Handling Errors in Spring WebFlux
Java – Generate Random String
Java Program to Describe the Representation of Graph using Adjacency Matrix
Java Program to Perform Inorder Non-Recursive Traversal of a Given Binary Tree
Convert XML to JSON Using Jackson
Spring Boot Application as a Service
Java Program to Perform Preorder Recursive Traversal of a Given Binary Tree
Java – Reader to InputStream
Using JWT with Spring Security OAuth
Extract links from an HTML page
Ép kiểu trong Java (Type casting)
Phương thức tham chiếu trong Java 8 – Method References
Hướng dẫn Java Design Pattern – Singleton
Java Program to Implement LinkedBlockingQueue API
Java Program to Implement IdentityHashMap API
Guide to @ConfigurationProperties in Spring Boot
Java Program to Implement Efficient O(log n) Fibonacci generator
Most commonly used String methods in Java
Hướng dẫn sử dụng Lớp FilePermission trong java
Java Program to Solve Tower of Hanoi Problem using Stacks
Java Program to Perform Insertion in a BST
Java Program to Implement Hash Tables chaining with Singly Linked Lists
Java Program to Implement Extended Euclid Algorithm
Mapping a Dynamic JSON Object with Jackson
Custom Thread Pools In Java 8 Parallel Streams
Hướng dẫn kết nối cơ sở dữ liệu với Java JDBC