Java Program to Check whether Graph is a Bipartite using DFS

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 Program to Implement Brent Cycle Algorithm
StringBuilder vs StringBuffer in Java
Java Program to Implement Graph Coloring Algorithm
Java Program to Find Number of Articulation points in a Graph
Spring @RequestParam Annotation
Ép kiểu trong Java (Type casting)
Java Program to Describe the Representation of Graph using Adjacency Matrix
Java Program to Compute the Volume of a Tetrahedron Using Determinants
Tính kế thừa (Inheritance) trong java
The DAO with JPA and Spring
Java Program to Use the Bellman-Ford Algorithm to Find the Shortest Path
Prevent Brute Force Authentication Attempts with Spring Security
Java Program to Implement Floyd-Warshall Algorithm
Java Program to Implement Find all Forward Edges in a Graph
Using the Not Operator in If Conditions in Java
Registration – Password Strength and Rules
Jackson Annotation Examples
Giới thiệu Google Guice – Aspect Oriented Programming (AOP)
Hướng dẫn Java Design Pattern – Observer
Java Program to Find Number of Spanning Trees in a Complete Bipartite Graph
Java Program to Implement a Binary Search Tree using Linked Lists
Interface trong Java 8 – Default method và Static method
Introduction to the Java NIO2 File API
Java Program to Perform Polygon Containment Test
Runnable vs. Callable in Java
Compare Two JSON Objects with Jackson
Java Program to Evaluate an Expression using Stacks
Java Program to Implement Gauss Seidel Method
Java Program to Implement the linear congruential generator for Pseudo Random Number Generation
Spring Boot - Service Components
How to Round a Number to N Decimal Places in Java
Recommended Package Structure of a Spring Boot Project