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

javalearner

着色问题。
    给一个无向图的所有结点着色，限制是一条边的两个端点不能用同样的颜色，要求所使用的不同颜色的数目最少。    “贪心”算法的思想是首先 用第一种颜色对图中尽可能多的顶点着色(“尽可能多”表现出“贪心”)；然后用第二种颜色对余下的顶点中尽可能多的顶点着色；如此等等，直到把所有的顶点都着完色。当用一种新颜色对余下的顶点着色时，我们采取下列步骤：  (1)选取某个未着色的顶点，并且用新颜色对它着色。  (2)扫描所有未着色的顶点集，对其中的每个顶点，确定它是否与已着新颜色的任何顶点相邻。若不相邻，则用新颜色对它着色。  while 有结点未着色； {
    选择一种新颜色；
    在未着色的结点中,给尽可能多的彼此结点之间没有边点着色； }

   
  
   
   

     
   

     
   
  
代码：

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. /*
    
12. 0 1
    
13. 1 0
    
14. */
    
15. /*
    
16. 0 1 1 0
    
17. 1 0 1 1
    
18. 1 1 0 1
    
19. 0 1 1 0
    
20. */
    
21. /*
    
22. 0 1 1 1
    
23. 1 0 1 1
    
24. 1 1 0 1
    
25. 1 1 1 0
    
26. */
    
27. public class GRcolor{
    
28. 
    
29. int n;//顶点数
    
30. int[] color;//color[k]=m表示第k个顶点着色m
    
31. int[][] c;//邻接矩阵
    
32. public GRcolor(int n,int[][]c){
    
33.     this.n=n;
    
34.     this.c=c;
    
35.     color=new int[n+1];
    
36. }
    
37. private boolean ok(int k,int r)//判断顶点k的着色是否发生冲突
    
38. {
    
39.    
    
40.     for(int i=1;i< n;i++){
    
41.         if(color[i]!=r) continue;
    
42.         if(c[k][i]==1&&color[i]==r )
    
43.             return true;
    
44.     }
    
45.     return false;
    
46. }
    
47. private int  graphcolor()
    
48. {
    
49.     for(int i=1;i<=n;i++)
    
50.         color[i]=0;//初始化
    
51.     int k=1,m=0,sum=0;
    
52.     while(sum< n){
    
53.             m++;
    
54.         for(int i=1;i<=n;i++){
    
55.           if(color[i]==0){
    
56.                 k=i;
    
57.                 color[k]=m;
    
58.                 sum++;
    
59.                 break;
    
60.           }
    
61.          }
    
62.          
    
63.          for(int i=k+1;i<=n;i++){
    
64.             if(color[i]!=0) continue;
    
65.             if (ok(i,m)) continue;
    
66.             else {
    
67.              color[i]=m;
    
68.              sum++;
    
69.               
    
70.             }
    
71.         }
    
72.       
    
73.      }
    
74.    
    
75.     System.out.printf("着色方案:
76. ");
    
77.      //求解完毕，输出着色方案
    
78.      for(int i=1;i<=n;i++){
    
79.                System.out.printf("%d ",color[i]);
    
80.             
    
81.     }
    
82.     System.out.println();
    
83.      return m;
    
84. }
    
85. public static void main(String args[]){
    
86.     Scanner in=new Scanner(System.in);
    
87.     System.out.printf("输入顶点数n
88. ");
    
89.     int n=in.nextInt();
    
90.      int[][] c=new int[n+1][n+1];//存储n个顶点的无向图的数组
    
91.     System.out.printf("输入无向图的邻接矩阵:
92. ");
    
93.     for(int i=1;i<=n;i++)
    
94.         for(int j=1;j<=n;j++)
    
95.             c[i][j]=in.nextInt();;
    
96.    
    
97.     GRcolor gc=new GRcolor(n,c);
    
98.     int m=gc.graphcolor();
    
99.     System.out.println("最小着色数="+m);
    
100. }
     
101. }
     

复制代码

运行：
输入顶点数n
5
输入无向图的邻接矩阵:
0 1 1 1 0
1 0 1 1 1
1 1 0 1 0
1 1 1 0 1
0 1 0 1 0
着色方案:
1 2 3 4 1
最小着色数=4

C:java>java   GRcolor
输入顶点数n
2
输入无向图的邻接矩阵:
0 1
1 0
着色方案:
1 2
最小着色数=2

C:java>java?? GRcolor
输入顶点数n
4
输入无向图的邻接矩阵:
0 1 1 0
1 0 1 1
1 1 0 1
0 1 1 0
着色方案:
1 2 3 1
最小着色数=3




  
  
   
   

     
   

     
   
  

复制代码

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