本文主要是介绍【图的dfs】—— 图的着色问题(二分图),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
把相邻结点染成不同颜色称为图的着色问题
对图进行着色的最小颜色数为2时称为二分图
思路:
这里对图的表示采取邻接表,然后就是常规的深搜。
step 1:创建邻接表的类,包含基本的API:
import java.util.ArrayList;
import java.util.List;public class GraphNode_AL {//邻接表的表示使用ArrayList来表示邻居public int val;//邻居节点private List<GraphNode_AL> neighbors;//当前的节点是否被访问public boolean checked = false;//构造方法public GraphNode_AL(int val) {this.val = val;}//增加邻居节点public void add(GraphNode_AL node){if(this.neighbors == null)neighbors = new
这篇关于【图的dfs】—— 图的着色问题(二分图)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!