Go语言视频零基础入门到精通

javalearner

图的m-着色判定问题――给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色，是否有一种着色法使G中任意相邻的2个顶点着不同颜色?    图的m-着色优化问题――若一个图最少需要m种颜色才能使图中任意相邻的2个顶点着不同颜色，则称这个数m为该图的色数。求一个图的最小色数m的问题称为m-着色优化问题。

算法描述（回逆算法）
    color[n]存储n个顶点的着色方案，可以选择的颜色为1到m t=1,对当前第t个顶点开始着色：  若t>n 则已求得一个解，输出着色方案即可 否则，依次对顶点t着色1-m，若t与所有其它相邻顶点无颜色冲突，则继续为下一顶点着色；否则，回溯，测试下一颜色。

   
  
   
   

     
   

     
   
  

1. import java.util.Scanner;
   
2. //图着色问题回溯法
   
3. /*
   
4. 无向图邻接矩阵示例
   
5. 0 1 1 1 0
   
6. 1 0 1 1 1
   
7. 1 1 0 1 0
   
8. 1 1 1 0 1
   
9. 0 1 0 1 0
   
10. */
    
11. public class Gcolor{
    
12. 
    
13. int n;//顶点数
    
14. int m;//着色数
    
15. int[] color;//color[k]=m表示第k个顶点着色m
    
16. int[][] c;//邻接矩阵
    
17. public Gcolor(int n,int m,int[][]c){
    
18.     this.n=n;
    
19.     this.m=m;
    
20.     this.c=c;
    
21.     color=new int[n+1];
    
22. }
    
23. private boolean ok(int k)//判断顶点k的着色是否发生冲突
    
24. {
    
25.    
    
26.     for(int i=1;i< k;i++)
    
27.         if(c[k][i]==1&&color[i]==color[k])
    
28.             return false;
    
29.         return true;
    
30. }
    
31. private void graphcolor()
    
32. {
    
33.     for(int i=1;i<=n;i++)
    
34.         color[i]=0;//初始化
    
35.     int k=1;
    
36.     while(k>=1){
    
37.         color[k]=color[k]+1;
    
38.         while(color[k]<=m){
    
39.           if (ok(k)) break;
    
40.             else color[k]=color[k]+1;//搜索下一个颜色
    
41.         }
    
42.         if(color[k]<=m&&k==n){//求解完毕，输出解
    
43.             for(int i=1;i<=n;i++)
    
44.                System.out.printf("%d ",color[i]);
    
45.             System.out.printf("
46. ");
    
47.         //return;//return表示之求解其中一种解
    
48.         } else if(color[k]<=m&&k< n)
    
49.                 k=k+1;    //处理下一个顶点
    
50.         else {
    
51.                 color[k]=0;
    
52.                 k=k-1;//回溯
    
53.         }
    
54.     }
    
55. }
    
56. public static void main(String args[]){
    
57.     Scanner in=new Scanner(System.in);
    
58.     System.out.printf("输入顶点数n和着色数m:
59. ");
    
60.     int n=in.nextInt();
    
61.     int m=in.nextInt();
    
62.     int[][] c=new int[n+1][n+1];//存储n个顶点的无向图的数组
    
63.     System.out.printf("输入无向图的邻接矩阵:
64. ");
    
65.     for(int i=1;i<=n;i++)
    
66.         for(int j=1;j<=n;j++)
    
67.             c[i][j]=in.nextInt();;
    
68.     System.out.printf("着色所有可能的解:
69. ");
    
70.     Gcolor gc=new Gcolor(n,m,c);
    
71.     gc.graphcolor();
    
72. }
    
73. }
    
74. 运行:
75. 输入顶点数n和着色数m:
76. 5 4
77. 输入无向图的邻接矩阵:
78. 0 1 1 1 0
79. 1 0 1 1 1
80. 1 1 0 1 0
81. 1 1 1 0 1
82. 0 1 0 1 0
83. 着色所有可能的解:
84. 1 2 3 4 1
85. 1 2 3 4 3
86. 1 2 4 3 1
87. 1 2 4 3 4
88. 1 3 2 4 1
89. 1 3 2 4 2
90. 1 3 4 2 1
91. 1 3 4 2 4
92. 1 4 2 3 1
93. 1 4 2 3 2
94. 1 4 3 2 1
95. 1 4 3 2 3
96. 2 1 3 4 2
97. 2 1 3 4 3
98. 2 1 4 3 2
99. 2 1 4 3 4
100. 2 3 1 4 1
101. 2 3 1 4 2
102. 2 3 4 1 2
103. ....................
     

复制代码

另一程序:

1.   import javax.swing.JOptionPane;
   
2. public class Coloring {
   
3.     static int n,             //图的顶点数
   
4.                m;             //可用颜色数
   
5.     static boolean[][] a = {  //图的邻接矩阵
   
6.             {false,false,false,false,false,false},
   
7.             {false,false,true,true,true,false},
   
8.             {false,true,false,true,true,true},
   
9.             {false,true,true,false,true,false},
   
10.             {false,true,true,true,false,true},
    
11.             {false,false,true,false,true,false},
    
12.     };
    
13.     static int[] x;           //当前解
    
14.     static long sum;          //当前已找到的可m着色方案数
    
15.    
    
16.     public static void main(String[] args) throws Exception {
    
17.             n = a[0].length-1;
    
18.             try {
    
19.                     m = Integer.parseInt(JOptionPane.showInputDialog(null, "请输入可用的颜色数，例如：3", "输入",
    
20.                                     JOptionPane.INFORMATION_MESSAGE));
    
21.             } catch(NumberFormatException e1) {
    
22.                     JOptionPane.showMessageDialog(null, "数据格式不正确，请重新运行程序输入！", "提示",
    
23.                                     JOptionPane.WARNING_MESSAGE);
    
24.                     return;
    
25.             }
    
26.             catch(Exception e) {
    
27.                     JOptionPane.showMessageDialog(null, "程序运行过程中出现其他类型的异常！", "提示",
    
28.                                     JOptionPane.WARNING_MESSAGE);
    
29.                     return;
    
30.             }
    
31.             x = new int[n+1];
    
32.             System.out.println("可行解方案数共为：" + mColoring(m));  //输出可行解方案数
    
33.     }
    
34.    
    
35.     public static long mColoring(int mm) {
    
36.             m = mm;
    
37.             sum = 0;
    
38.             backtrack(1);
    
39.             return sum;
    
40.     }
    
41.    
    
42.     private static void backtrack(int t) {
    
43.             if(t > n) {  //搜索到叶结点
    
44.                     sum++;
    
45.                     for(int i=1; i<=n; i++)
    
46.                             System.out.print(x[i] + " ");
    
47.                     System.out.print("
48. ");
    
49.             }
    
50.             else
    
51.                     for(int i=1; i<=m; i++) {
    
52.                             x[t] = i;
    
53.                             if(ok(t)) backtrack(t+1);
    
54.                             x[t] = 0;
    
55.                     }
    
56.     }
    
57.    
    
58.     private static boolean ok(int k) {  //检查颜色可用性
    
59.             for(int j=1; j<=n; j++)
    
60.                     if(a[k][j] && (x[j]==x[k])) return false;
    
61.             return true;
    
62.     }
    
63. }
    
64.               

复制代码

  
  
   
   

     
   

     
   
  

复制代码

源码下载：http://file.javaxxz.com/2014/12/6/000715468.zip