admin 管理员组

文章数量: 1184232

回溯法解决图着色问题Java代码

(该文作为我的一个学习记录,方便后续回看)

  1. 问题描述
    图的 m- 着色判定问题 —— 给定无向连通图 G 和 m 种不同的颜色。用这些颜色为图 G 的各顶点着色,每个顶点着一种颜色,是否有一种着色法使 G 中任意相邻的 2 个顶点着不同颜色 ?
  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

本文标签: 代码 java