回溯法解决图的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;}}