回溯法解决图着色问题Java代码
（该文作为我的一个学习记录，方便后续回看）
- 问题描述
图的 m- 着色判定问题 —— 给定无向连通图 G 和 m 种不同的颜色。用这些颜色为图 G 的各顶点着色，每个顶点着一种颜色，是否有一种着色法使 G 中任意相邻的 2 个顶点着不同颜色 ? - 思路及代码
color[n]存储n个顶点的着色方案，可以选择的颜色为1到m。
当x=1时，对当前第n个顶点开始着色：若x>n，则已求得一个解，输出着色方案即可。否则，依次对顶点x着色1到m， 若x与所有其它相邻顶点无颜色冲突，则继续为下一顶点着色；否则，回溯，测试下一颜色。
代码如下：
public class graphcolor {
public static int[][] c=new int[20][20]; //c存储图的邻接矩阵
public static int[] color=new int[20]; //color表示顶点颜色
public static int m,n,count=0; //m发布者：admin，转转请注明出处：http://www.yc00.com/web/1754941672a5218248.html
评论列表（0条）