admin管理员组

文章数量:1130349

回溯法解决图着色问题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代码

（该文作为我的一个学习记录，方便后续回看）

  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

版权声明：本文标题：回溯法解决图着色问题Java代码 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://it.en369.cn/jiaocheng/1754941673a2744394.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。