回溯法解决图的m着色问题

package guoxin;
//图的m着色问题
public class Zuose {

/**
* @param args
*/
public static void main(String[] args) {
int p[][]= new int[6][6];
p[1][2]=1;
p[1][3]=1;
p[2][1]=1;
p[2][3]=1;
p[2][4]=1;
p[2][5]=1;
p[3][2]=1;
p[3][1]=1;
p[3][5]=1;
p[4][2]=1;
p[4][5]=1;
p[5][4]=1;
p[5][3]=1;
graph(p,5,3);

}
/**
*
* @param p表示图中点之间的关系，p[i][j]=0表示点i与j之间没有连线，p[i][j]=1表示有连线,下表从1开始
* @param n图中顶点的个数，
* @param m//最多允许使用的颜色数
*/
private static void graph(int p[][],int n,int m){
int c[]=new int[n+1];
for(int i=0;i<=n;i++){
c[i]=0;
}
int k=1;
while(k>=1){
c[k]=c[k]+1;
while(c[k]<=m){
if(isPermit(p,c,k))break;
else{
c[k]+=1;
}
}
if(k==n&&c[k]<=m){
for(int i=1;i<=n;i++){
System.out.println(c[i]);

}
return;
}else if(c[k]<=m){
k=k+1;

}else{
c[k]=0;
k=k-1;
}
}
}
//判断对指定顶点着色后是否与前面已经着色的顶点放生冲突
private static boolean isPermit(int p[][],int c[],int k){
for(int i=1;i<k;i++){
if(p[i][k]==1&&c[i]==c[k])return false;
}
return true;
}


}

package guoxin;
//图的m着色问题
public class Zuose {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int p[][]= new int[6][6];
		p[1][2]=1;
		p[1][3]=1;
		p[2][1]=1;
		p[2][3]=1;
		p[2][4]=1;
		p[2][5]=1;
		p[3][2]=1;
		p[3][1]=1;
		p[3][5]=1;
		p[4][2]=1;
		p[4][5]=1;
		p[5][4]=1;
		p[5][3]=1;
		graph(p,5,3);

	}
	/**
	 * 
	 * @param p表示图中点之间的关系，p[i][j]=0表示点i与j之间没有连线，p[i][j]=1表示有连线,下表从1开始
	 * @param n图中顶点的个数，
	 * @param m//最多允许使用的颜色数
	 */
	private static void graph(int p[][],int n,int m){
		int c[]=new int[n+1];
		for(int i=0;i<=n;i++){
			c[i]=0;
		}
		int k=1;
		while(k>=1){
			c[k]=c[k]+1;
			while(c[k]<=m){
				if(isPermit(p,c,k))break;
				else{
					c[k]+=1;
				}
			}
			if(k==n&&c[k]<=m){
				for(int i=1;i<=n;i++){
					System.out.println(c[i]);
					
				}
				return;
			}else if(c[k]<=m){
				k=k+1;
				
			}else{
				c[k]=0;
				k=k-1;
			}
		}	
	}
	//判断对指定顶点着色后是否与前面已经着色的顶点放生冲突
	private static boolean isPermit(int p[][],int c[],int k){
		for(int i=1;i<k;i++){
			if(p[i][k]==1&&c[i]==c[k])return false;
		}
		return true;
	}
	

}