Graph二分图检测

针对二分图即图里面所有的点和其相邻的点的颜色都是不同的， 即图中的0，2，4，5为1类， 1，3，6为另一类。如何识别一个图是否是2分图呢？ 通过深度优先遍历加上染色的方式。 设置有两种颜色分别是0和1, 然后每个点遍历观察其颜色，如果尚未被遍历，则染色（染对立的颜色）如果 已经遍历了，则观察下其颜色是否出现冲突，一旦冲突说明改点会被染两种颜色，则一定不是二分图。 设图的结构如下g3.txt

7 7 0 1 0 2 3 1 3 2 4 1 6 2 6 5

g4.txt

7 7 0 1 0 3 1 2 2 3 3 4 5 6 2 4

代码如下：

package graph; /** * 二分图检测 */ public class GraphBipartitionDetection { private Graph G; private final boolean[] visited; private final int[] colors; //染色 private boolean isBiPartition = true; public GraphBipartitionDetection(Graph g) { this.G = g; this.visited = new boolean[G.V()]; this.colors = new int[G.V()]; for (int i = 0; i < G.V(); i++) { colors[i] = -1; } for (int v = 0; v < G.V(); v++) { if (!visited[v]) { if (!dfs(v, 0)) { isBiPartition = false; break; } } } } private boolean dfs(int v, int color) { visited[v] = true; colors[v] = color; for (int w : G.adj(v)) { if (!visited[w]) { if (!dfs(w, 1 - color)) { return false; } } else { if (colors[w] == colors[v]) { // 颜色撞上了 return false; } } } return true; } public boolean isBiPartition() { return isBiPartition; } public static void main(String[] args) { Graph graph = new Graph("g4.txt"); GraphBipartitionDetection graphDFS = new GraphBipartitionDetection(graph); System.out.println(graphDFS.isBiPartition()); graph = new Graph("g3.txt"); graphDFS = new GraphBipartitionDetection(graph); System.out.println(graphDFS.isBiPartition()); } }