福州网站建设设计,学计算机哪个培训机构好,网站开发网站开发公司哪家好,中国建材建设网站文章目录1 概念2 API3 分析和实现4 测试5 总结后记1 概念 二分图是一种能将所有结点分为两部分的图#xff0c;其中图的每条边所连接的两个顶点都分别属于不同的部分。 2 API
public classBipartiteBipartite(Graph G)预处理函数public booleanisBipartitle()是否是二分图pub…
文章目录1 概念2 API3 分析和实现4 测试5 总结后记1 概念 二分图是一种能将所有结点分为两部分的图其中图的每条边所连接的两个顶点都分别属于不同的部分。 2 API
public classBipartiteBipartite(Graph G)预处理函数public booleanisBipartitle()是否是二分图public IterableIteratablecycle()如果不是二分图输出同色边所在环路public booleancolor(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 StackInteger cycle;/*** 染色法检测是否是二分图** param G the undirected graph*/public Bipartite(Graph G) {// 只是检测二分图可以不进行平行边的判断如果想找到形成同色边所在环则需要进行平行边的判断// if (hasParallelEdges(G)) {// return;// }// dont 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) {StackNode 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, StackNode stack) {marked[v] true;IterableInteger 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);}IterableInteger 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 StackInteger();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 StackInteger();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 IterableInteger cycle() {return cycle;}static class Node {/*** 顶点索引*/private int v;/*** 顶点邻接表*/private IteratorInteger adj;public Node(int v, IteratorInteger 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,…,2k1,k∈N1,2,\dots,2k1,k\in N1,2,…,2k1,k∈N。根据我们的染色规则那么第1和顶点和最后一个顶点由同一条边相连接且颜色相同。所以不是二分图。
广度优先搜索算法也可以解决二分图判别染色问题有兴趣的小伙伴自行实现吧也可以参考算法第四版对应jar包。
后记
如果小伙伴什么问题或者指教欢迎交流。 ❓QQ:806797785 ⭐️源代码仓库地址https://gitee.com/gaogzhen/algorithm 参考链接:
[1][美]Robert Sedgewich,[美]Kevin Wayne著;谢路云译.算法第4版[M].北京人民邮电出版社2012.10.p344-348.
