回溯法求解K图染色问题（java版）

回溯法：K图着色问题

问题描述：

对如图 1 所示的图，采用局部搜索算法，求其对应的 3 着色方案。

问题分析：

题目的目标是用3种颜色，将图1中的每个节点着色，且保证相邻节点间颜色不同；
a) 首先我们可以建立一个颜色集合$color[9]$,存储每个节点的颜色
b) 从前向后遍历每个节点，让每个节点从3种颜色中选择一种颜色，判断是否与其相邻节点冲突；若冲突，则选则下一种颜色，没有颜色可选时，回溯至上一节点，更改其颜色
c) 当所有节点都着色，则结束程序

伪代码：

$input：g[9][9]\leftarrow NodeSet,K=3$
$output：color[9]$
$foreach$ $node$ $in$ $N$
$choose$ $a$ $color$ $for$ $node$
$if:check(node)$
$goto:nextNode$
$else$
$choose$ $another$ $color$ $for$ $node$
$if$ $no$ $color$ $can$ $choose$
$then$ $backTrace$ $frontNode$

局限性

回溯法求解K图着色问题，只能用于图节点个数较小的场景，当节点个数上百个时，回溯法的解空间过大，时间复杂度高；因此，对于上百个图节点的着色问题可以使用局部搜索法求解。
局部搜索法求解K图着色问题（java版)

具体实现

import java.util.Scanner;
public class KGraphColor{
	static final int num=9;
	static int[] color =new int[num]; 
	public static void main(String [] args){
		int m = 3;
		int[][] g= {{0,1,1,1,0,0,0,0,0},
					{1,0,0,0,1,0,0,0,1},
					{1,0,0,0,0,0,0,1,0},
					{1,0,0,0,0,0,1,1,0},
					{0,1,0,0,0,1,0,1,0},
					{0,0,0,0,1,0,0,0,0},
					{0,0,0,1,0,0,0,1,1},
					{0,0,1,1,1,0,1,0,0},
					{0,1,0,0,1,0,1,0,0}};
		graphColor(num,m,g);
	}
	public static boolean check(int k, int[][] g){
		for(int i=0;i<k;++i){
			if(g[k][i]==1 && color[i] == color[k]){
				return false;
			}
		}
		return true;
	}
	public  static boolean graphColor(int n,int m,int[][] g){
		int k=1;
		while(k>=1){
			while(color[k]<m){
				if(check(k,g)){
					break;
				}
				else{
					++color[k];
				}
			}
			if(color[k]<m&&k==n-1){
				for(int i=0;i<n;++i){
					System.out.print(color[i]+",");
				}
				System.out.println();
				return false;
			}else if(color[k]<m && k<n-1){
					++k;
			}else{
				color[k]=0;
				--k;
				++color[k];
			}
		}
		return true;
	}
	
}	

本文地址：https://blog.csdn.net/shiaiao/article/details/110245971