欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-06-28 17:07:05
回溯法解决图着色问题Java代码(该文作为我的一个学习记录,方便后续回看)问题描述图的 m- 着色判定问题 —— 给定无向连通图 G 和 m 种不同的颜色。用这些颜色为图 G 的各顶点着色,每个顶点着一种颜色,是否有一种着色法使 G 中任意相邻的 2 个顶点着不同颜色 ?思路及代码color[n]存储n个顶点的着色方案,可以选择的颜色为1到m。当x=1时,对当前第n个顶点开始着色:若x>n,则已求得一个解,输出着色方案即可。否则,依次对顶点x着色1到m, 若x与所有其它相邻顶点无颜色冲突...

回溯法解决图着色问题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--颜色数     n-顶点数   count--方案数
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		m=sc.nextInt();	
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				c[i][j]=sc.nextInt();
			}
		}
		graphColor(1);         //从第一个顶点开始
		System.out.println(count);
		sc.close();
	}

	public static void graphColor(int x) {
		if (x<=n) {
			for (int i = 1; i <= m; i++) {  
				color[x]=i;           //将这个顶点颜色换为i
				if (isok(x)) {         //检查颜色是否合理
					graphColor(x+1);    //合理即走下一步
				}
				color[x]=0;        //不合理回溯
			}
		}
		else {
			for (int i = 1; i <= n; i++) {
				System.out.print(color[i]+" ");		
			}
			System.out.println();
			count++;
		}	
	}

	public static boolean isok(int x) {
		for (int i = 1; i <= x; i++) {
			if (c[x][i]==1&&color[i]==color[x]) {
				return false;
			}
		}
		return true;
	}

}

本文地址:https://blog.csdn.net/m0_48372408/article/details/109630790

相关标签: 算法