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:
Converting Java Date to OffsetDateTime
Java Program to Perform Insertion in a BST
Java Program to Find All Pairs Shortest Path
Spring Boot - Creating Docker Image
Java Program to Implement ConcurrentSkipListMap API
Introduction to Spring MVC HandlerInterceptor
Spring REST API with Protocol Buffers
Giới thiệu java.io.tmpdir
Java Program to Compute Cross Product of Two Vectors
Guide to the Java TransferQueue
Remove HTML tags from a file to extract only the TEXT
Java Program to Implement an Algorithm to Find the Global min Cut in a Graph
The Java 8 Stream API Tutorial
Spring RestTemplate Error Handling
Simplify the DAO with Spring and Java Generics
Hướng dẫn Java Design Pattern – Service Locator
Tránh lỗi NullPointerException trong Java như thế nào?
Guide To CompletableFuture
Sử dụng Fork/Join Framework với ForkJoinPool trong Java
Introduction to Spring Cloud OpenFeign
Java Program to Implement Self Balancing Binary Search Tree
Java Program to Implement Fisher-Yates Algorithm for Array Shuffling
Adding Shutdown Hooks for JVM Applications
The SpringJUnitConfig and SpringJUnitWebConfig Annotations in Spring 5
Logging a Reactive Sequence
String Initialization in Java
Java Program to Implement Gauss Jordan Elimination
Guide to WeakHashMap in Java
Java Program to Find the Vertex Connectivity of a Graph
Java Program to Find the Nearest Neighbor Using K-D Tree Search
Spring Boot Actuator
Tìm hiểu cơ chế Lazy Evaluation của Stream trong Java 8