0109二分图-无向图-数据结构和算法(Java)

1 概念

二分图是一种能将所有结点分为两部分的图，其中图的每条边所连接的两个顶点都分别属于不同的部分。

2 API

public class	Bipartite
	Bipartite(Graph G)	预处理函数
public boolean	isBipartitle()	是否是二分图
public Iterable<Iteratable>	cycle()	如果不是二分图，输出同色边所在环路
public boolean	color(int v)	输出顶点v的颜色

3 分析和实现

深度优先非递归实现，源代码如下：

package com.gaogzhen.datastructure.graph.undirected;import com.gaogzhen.datastructure.stack.Stack;
import edu.princeton.cs.algs4.Graph;import java.util.Iterator;/*** 二分图* @author: Administrator* @createTime: 2023/03/10 19:27*/
public class Bipartite {/*** 标记顶点*/private boolean[] marked;/*** 记录所有顶点到起点的路径*/private int[] edgeTo;/*** 双色标记顶点颜色,true和false*/private boolean[] color;/*** 是否是二分图标志，默认true*/private boolean isBipartite = true;/*** 如果不是二分图，记录形成同色边所在环*/private Stack<Integer> cycle;/*** 染色法检测是否是二分图** @param G the undirected graph*/public Bipartite(Graph G) {// 只是检测二分图可以不进行平行边的判断；如果想找到形成同色边所在环则需要进行平行边的判断// if (hasParallelEdges(G)) {//     return;// }// don't need special case to identify self-loop as a cycle// if (hasSelfLoop(G)) return;int len = G.V();marked = new boolean[len];color = new boolean[len];edgeTo = new int[len];for (int i = 0; i < len; i++) {edgeTo[i] = -1;}dfs(G);}private void dfs(Graph G) {Stack<Node> stack = new Stack<>();for (int v = 0; v < G.V(); v++) {if (!marked[v]) {if (dfs(G, v, stack) ) {return;}}}}/*** 深度优先染色** @param G     无向图* @param v* @param stack*/private boolean dfs(Graph G, int v, Stack<Node> stack) {marked[v] = true;Iterable<Integer> adj = G.adj(v);if (adj != null) {stack.push(new Node(v,adj.iterator()));}while (!stack.isEmpty()) {Node c = stack.pop();while (c.adj.hasNext()) {Integer w = c.adj.next();if (!marked[w]) {marked[w] = true;edgeTo[w] = c.v;// 当前顶点染和其父结点相反的颜色color[w] = !color[c.v];if (c.adj.hasNext()) {stack.push(c);}Iterable<Integer> adjW = G.adj(w);if (adjW != null) {stack.push(new Node(w, adjW.iterator()));}break;}// check for cycle (but disregard reverse of edge leading to v)else if (color[w] == color[c.v]) {// 记录同色边所在环路cycle = new Stack<>();cycle.push(w);for (int x = c.v; x != w; x = edgeTo[x]) {cycle.push(x);}cycle.push(w);isBipartite = false;return true;}}}return false;}/*** 检测无向图G是否有子环* @param G* @return*/private boolean hasSelfLoop(Graph G) {for (int v = 0; v < G.V(); v++) {for (int w : G.adj(v)) {if (v == w) {cycle = new Stack<Integer>();cycle.push(v);cycle.push(v);return true;}}}return false;}/*** 检测无向图G是否有平行边* @param G* @return*/private boolean hasParallelEdges(Graph G) {marked = new boolean[G.V()];for (int v = 0; v < G.V(); v++) {// check for parallel edges incident to vfor (int w : G.adj(v)) {if (marked[w]) {cycle = new Stack<Integer>();cycle.push(v);cycle.push(w);cycle.push(v);return true;}marked[w] = true;}// reset so marked[v] = false for all vfor (int w : G.adj(v)) {marked[w] = false;}}return false;}/*** 是否是二分图* @return*/public boolean isBipartite() {return isBipartite;}public boolean color(int v) {validateVertex(v);if (!isBipartite) {throw new UnsupportedOperationException("graph is not bipartite");}return color[v];}private void validateVertex(int v) {int V = marked.length;if (v < 0 || v >= V) {throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V-1));}}/*** 如果有环，返回环路* @return a cycle if the graph {@code G} has a cycle,*         and {@code null} otherwise*/public Iterable<Integer> cycle() {return cycle;}static class Node {/*** 顶点索引*/private int v;/*** 顶点邻接表*/private Iterator<Integer> adj;public Node(int v, Iterator<Integer> adj) {this.v = v;this.adj = adj;}}
}

原理：深度优先遍历无向图，遍历顶点v，标记且颜色染为其父结点的反色。遍历顶点v邻接表顶点w时，如果w已经被标记过且颜色和顶点v的颜色相同。说明边v-w为同色边，不是二分图。重复上述过程，如果遍历完整个无向图，没有发现同色边，说明该无向图为二分图，且染色完毕。

记录同色边所在环：edgeTo[]记录所有顶点到起点的路径，为一棵由父链接表示的树。如果找到同色边v-w，说明它一也形成了环路。变量从顶点v开始遍历树，通过把x设为edgeTo[v]，直到顶点w。容器起始放入顶点w，最后放入w，记录完整环路。

双色：利用布尔值true和false表示，通过逻辑非很容易取反色。

4 测试

测试代码：

public static void testBipartite() {String path = "H:\\gaogzhen\\java\\projects\\algorithm\\asserts\\bipartite.txt";// String path = "H:\\gaogzhen\\java\\projects\\algorithm\\asserts\\maze.txt";In in = new In(path);Graph graph = new Graph(in);Bipartite bipartite = new Bipartite(graph);System.out.println("是否是二分图：" + bipartite.isBipartite());System.out.println("非二分图环：" + bipartite.cycle());
}

bipartite.txt中染色效果如下图4-1所示：

maze.txt染色效果如下图4-2所示：

5 总结

如果一幅图有环且环中顶点数为奇数，那么它就不是二分图。

• 如果一幅图没有环，那么深度优先遍历就是一棵树，从起点开始，把边两个顶点染不同的颜色，一定是二分图。
• 一幅图有环而且环中顶点数为奇数，给顶点做标记$1,2,\dots ,2k+1,k\in N$。根据我们的染色规则，那么第1和顶点和最后一个顶点由同一条边相连接，且颜色相同。所以不是二分图。

广度优先搜索算法也可以解决二分图判别染色问题，有兴趣的小伙伴自行实现吧，也可以参考算法第四版对应jar包。

后记

如果小伙伴什么问题或者指教，欢迎交流。

❓QQ:806797785

⭐️源代码仓库地址：https://gitee.com/gaogzhen/algorithm

参考链接:

[1][美]Robert Sedgewich,[美]Kevin Wayne著;谢路云译.算法：第4版[M].北京：人民邮电出版社，2012.10.p344-348.