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

Tags: Java

Posted on Wed, 04 Dec 2019 10:13:08 -0800 by spode