This Java program is to check whether graph is bipartite using dfs. 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 dfs. 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; import java.util.Stack; public class BipartiteDfs { private int numberOfVertices; private Stack<Integer> stack; public static final int NO_COLOR = 0; public static final int RED = 1; public static final int BLUE = 2; public BipartiteDfs(int numberOfVertices) { this.numberOfVertices = numberOfVertices; stack = new Stack<Integer>(); } public boolean isBipartite(int adjacencyMartix[][], int source) { int[] colored = new int[numberOfVertices + 1]; for (int vertex = 1; vertex <= numberOfVertices; vertex++) { colored[vertex] = NO_COLOR; } stack.push(source); colored = RED; int element = source; int neighbours = source; while (!stack.empty()) { element = stack.peek(); neighbours = element; while (neighbours <= numberOfVertices) { if (adjacencyMartix[element][neighbours] == 1&& colored[neighbours] == colored[element]) { return false; } if (adjacencyMartix[element][neighbours] == 1 && colored[neighbours] == NO_COLOR) { colored[neighbours] = (colored[element] == RED) ? BLUE : RED; stack.push(neighbours); element = neighbours; neighbours = 1; continue; } neighbours++; } stack.pop(); } 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(); BipartiteDfs bipartiteDfs = new BipartiteDfs(number_of_nodes); if (bipartiteDfs.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:
Java InputStream to Byte Array and ByteBuffer
Custom Thread Pools In Java 8 Parallel Streams
Java Program to Check if it is a Sparse Matrix
Tạo chương trình Java đầu tiên sử dụng Eclipse
Java Program to Implement Heap
Checked and Unchecked Exceptions in Java
Properties with Spring and Spring Boot
Introduction to Netflix Archaius with Spring Cloud
Guide to the Fork/Join Framework in Java
Sử dụng CyclicBarrier trong Java
Java Program to Implement Segment Tree
Constructor Injection in Spring with Lombok
Java Program to Implement Floyd Cycle Algorithm
Java Program to Compute Cross Product of Two Vectors
What is Thread-Safety and How to Achieve it?
Java Program to Implement Trie
Encode/Decode to/from Base64
Java Program to Implement Unrolled Linked List
Sử dụng Fork/Join Framework với ForkJoinPool trong Java
Java Program to Implement Graph Structured Stack
Java Program to Perform Naive String Matching
Difference Between Wait and Sleep in Java
Java Program to implement Bit Set
Registration – Activate a New Account by Email
Java Program to Generate All Possible Combinations of a Given List of Numbers
An Intro to Spring Cloud Contract
Debugging Reactive Streams in Java
Java Program to Generate Random Numbers Using Middle Square Method
A Guide to BitSet in Java
Java Program to Find Minimum Element in an Array using Linear Search
Send email with authentication
Clique in the Divisibility Graph