# 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; } }`