Definition

Bipartite graph is a special model in graph theory. If a graph can be divided into two parts: green and blue, and each line is connected with a green vertex and a blue fixed point, it is called a bipartite graph. The following figure is a bipartite graph

Bipartite detection

An example is shown as follows: It's hard for the naked eye to distinguish the two parts, which can only be distinguished by using certain algorithms. Here's the detection method -- dyeing

dyeing

First, select a node, set it to blue (green is OK), then set the node connected with it to the opposite color - green, set the nodes to the opposite color in turn according to the logic of depth first (breadth first is OK), if the final result is: each edge is connected to this blue and a green node, then the binary graph detection is successful

Code implementation (java)

import java.util.ArrayList;

public class BipartitionDetection {

    /**
     * Class of Graphs
     * public class Graph {
     * private int V; // vertex
     * private TreeSet<Integer>[] adj; // Array of vertex trees connected to each vertex
     * }
     */
    private Graph G;
    /**
     * Array of visited vertices
     */
    private boolean[] visited;
    /**
     * 0->Blue, 1 - > Green
     */
    private int[] colors;
    /**
     * Is it a bipartite graph
     */
    private boolean isBipartite = true;

    public BipartitionDetection(Graph G) {
        this.G = G;
        visited = new boolean[G.V()];
        colors = new int[G.V()];
        for (int i = 0; i < G.V(); i++)
            // Initialization
            colors[i] = -1;

        for (int v = 0; v < G.V(); v++)
            if (!visited[v])
                if (!dfs(v, 0)) {
                    isBipartite = false;
                    break;
                }
    }

    /**
     * Recursive traversal node
     *
     * @param v     vertex
     * @param color Color, 0 - > blue, 1 - > Green
     */
    private boolean dfs(int v, int color) {
        visited[v] = true;
        colors[v] = color;
        // Traverse every vertex connected to v
        for (int w : G.adj(v))
            // Judge whether to traverse / dye
            if (!visited[w]) {
                // Dye in the opposite color of v
                if (!dfs(w, 1 - color)) return false;
            } else if (colors[w] == colors[v]) {
                // Colored, judge whether the vertex color connected with v is the same as v, if it is the same, it does not meet the bipartite graph
                return false;
            }
        return true;
    }

    /**
     * Is it a bipartite graph
     */
    public boolean isBipartite() {
        return isBipartite;
    }
}