二分图问题
2023-03-14 09:44:37 时间
一、问题描述
给定一个具有n个顶点的图,要给图上每个顶点染色并且要使相邻的顶点的颜色不同,问是否最多用2种颜色进行染色?没有重边和自环。把相邻顶点染成不同颜色的问题叫做图的着色问题。对图进行染色所需的最小颜色数,称为最小着色数。最小着色数为2的图称为二分图,如下图所示就是一个二分图。下面代码是用来判断是否二分图。
二、思路
直接DFS即可,要注意代码里面的一些细节。
三、代码
1 public class 图的着色_二分图 { 2 static boolean dfs(MyNode node, int c) { 3 node.color = c;// 同时标记已访问和具体颜色 4 for (int i = 0; i < node.size(); i++) {// 遍历所有neighbor 5 MyNode neighbor = (MyNode) node.getNeighbor(i);// 具体的neighbor 6 // 如果相邻节点颜色一样,返回false 7 if (neighbor.color == c) 8 return false; 9 // 没有被染色,就染不同颜色进行递归 10 if (neighbor.color == 0) { 11 boolean res = dfs(neighbor, -c); 12 if (!res) 13 return false; 14 } 15 } 16 return true; 17 } 18 19 public static void main(String[] args) { 20 // 下面的数据表示的就是上面的图 21 MyNode n1 = new MyNode(1); 22 MyNode n2 = new MyNode(2); 23 MyNode n3 = new MyNode(3); 24 MyNode n4 = new MyNode(4); 25 26 n1.add(n2); 27 n1.add(n4); 28 29 n2.add(n1); 30 n2.add(n3); 31 32 n3.add(n2); 33 n3.add(n4); 34 35 n4.add(n1); 36 n4.add(n3); 37 38 // 任意顶点都可以 39 System.out.println(dfs(n1, 1)); // 输出 true 40 } 41 42 // GraphNode_AL这个类在前面博客 邻接表表示图 43 static class MyNode extends GraphNode_AL { 44 int color; 45 46 public MyNode(int val) { 47 super(val); 48 } 49 50 public MyNode(int val, int color) { 51 super(val); 52 this.color = color; 53 } 54 } 55 }
相关文章
- 在 Go 里用 CGO?这 7 个问题你要关注!
- 9款优秀的去中心化通讯软件 Matrix 的客户端
- 求职数据分析,项目经验该怎么写
- 在OKR中,我看到了数据驱动业务的未来
- 火山引擎云原生大数据在金融行业的实践
- OpenHarmony富设备移植指南(二)—从postmarketOS获取移植资源
- 《数据成熟度指数》报告:64%的企业领袖认为大多数员工“不懂数据”
- OpenHarmony 小型系统兼容性测试指南
- 肯睿中国(Cloudera):2023年企业数字战略三大趋势预测
- 适用于 Linux 的十大命令行游戏
- GNOME 截图工具的新旧截图方式
- System76 即将推出的 COSMIC 桌面正在酝酿大变化
- 2GB 内存 8GB 存储即可流畅运行,Windows 11 极致精简版系统 Tiny11 发布
- 迎接 ecode:一个即将推出的具有全新图形用户界面框架的现代、轻量级代码编辑器
- loongarch架构介绍(三)—地址翻译
- Go 语言怎么解决编译器错误“err is shadowed during return”?
- 敏捷:可能被开发人员遗忘的部分
- Denodo预测2023年数据管理和分析的未来
- 利用数据推动可持续发展
- 在 Vue3 中实现 React 原生 Hooks(useState、useEffect),深入理解 React Hooks 的