采用贪心法求解着色问题（JAVA）

贪心法求解着色问题。
  给图的所有结点着色，限制是一条边的两个端点不能用同样的颜色，要求所使用的不同颜色的数目最少。

“贪心”算法的思想是首先  用第一种颜色对图中尽可能多的顶点着色(“尽可能多”表现出“贪心”)；然后用第二种颜色对余下的顶点中尽可能多的顶点着色；如此等等，直到把所有的顶点都着完色。当用一种新颜色对余下的顶点着色时，我们采取下列步骤：

(1)选取某个未着色的顶点，并且用新颜色对它着色。

(2)扫描所有未着色的顶点集，对其中的每个顶点，确定它是否与已着新颜色的任何顶点相邻。若不相邻，则用新颜色对它着色。

while  有结点未着色；

   {  选择一种新颜色；

      在未着色的结点中,给尽可能多的彼此结点之间没有边点着色；

    }
代码：

import java.util.Scanner;
//图着色问题
/*
无向图邻接矩阵示例
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
*/

/*
0 1
1 0
*/

/*
0 1 1 0
1 0 1 1
1 1 0 1
0 1 1 0
*/

/*
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0
*/
public class GRcolor{
 
 int n;//顶点数
 int[] color;//color[k]=m表示第k个顶点着色m
 int[][] c;//邻接矩阵

 public GRcolor(int n,int[][]c){
    this.n=n;
    this.c=c;
    color=new int[n+1];
 }

 private boolean ok(int k,int r)//判断顶点k的着色是否发生冲突
{
   
    for(int i=1;i<n;i++){
        if(color[i]!=r) continue;
        if(c[k][i]==1&&color[i]==r )
            return true;
    }
    return false;
}

 private int  graphcolor()
{
    for(int i=1;i<=n;i++)
        color[i]=0;//初始化
    int k=1,m=0,sum=0;
    while(sum<n){
            m++;
        for(int i=1;i<=n;i++){
          if(color[i]==0){
                k=i;
                color[k]=m;
                sum++;
                break;
          }
         }
         
         for(int i=k+1;i<=n;i++){
            if(color[i]!=0) continue;
            if (ok(i,m)) continue;
            else {
             color[i]=m;
             sum++;
              
            }
        }
      
     }
   
    System.out.printf("着色方案:\n");
     //求解完毕，输出着色方案
     for(int i=1;i<=n;i++){
               System.out.printf("%d ",color[i]);
            
    }
    System.out.println();
     return m;
}


public static void main(String args[]){
    Scanner in=new Scanner(System.in);
    System.out.printf("输入顶点数n\n");
    int n=in.nextInt();
     int[][] c=new int[n+1][n+1];//存储n个顶点的无向图的数组
    System.out.printf("输入无向图的邻接矩阵:\n");
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            c[i][j]=in.nextInt();;
    
    GRcolor gc=new GRcolor(n,c);
    int m=gc.graphcolor(); 
    System.out.println("最小着色数="+m);
 }

}

运行：
输入顶点数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

下载源码：