采用贪心法求解着色问题（JAVA）
贪心法求解着色问题。给图的所有结点着色，限制是一条边的两个端点不能用同样的颜色，要求所使用的不同颜色的数目最少。
“贪心”算法的思想是首先用第一种颜色对图中尽可能多的顶点着色(“尽可能多”表现出“贪心”)；然后用第二种颜色对余下的顶点中尽可能多的顶点着色；如此等等，直到把所有的顶点都着完色。当用一种新颜色对余下的顶点着色时，我们采取下列步骤：
(1)选取某个未着色的顶点，并且用新颜色对它着色。
(2)扫描所有未着色的顶点集，对其中的每个顶点，确定它是否与已着新颜色的任何顶点相邻。若不相邻，则用新颜色对它着色。
while有结点未着色；
{选择一种新颜色；
在未着色的结点中,给尽可能多的彼此结点之间没有边点着色；
}
代码：
import java.util.Scanner;//图着色问题/*无向图邻接矩阵示例0 1 1 1 01 0 1 1 11 1 0 1 01 1 1 0 10 1 0 1 0*//*0 11 0*//*0 1 1 01 0 1 11 1 0 10 1 1 0*//*0 1 1 11 0 1 11 1 0 11 1 1 0*/public class GRcolor{int n;//顶点数 int[] color;//color=m表示第k个顶点着色m int[][] c;//邻接矩阵 public GRcolor(int n,int[][]c){ this.n=n; this.c=c; color=new int; } private boolean ok(int k,int r)//判断顶点k的着色是否发生冲突{ for(int i=1;i<n;i++){ if(color!=r) continue; if(c==1&&color==r ) return true; } return false;} private intgraphcolor(){ for(int i=1;i<=n;i++) color=0;//初始化 int k=1,m=0,sum=0; while(sum<n){ m++; for(int i=1;i<=n;i++){ if(color==0){ k=i; color=m; sum++; break; } } for(int i=k+1;i<=n;i++){ if(color!=0) continue; if (ok(i,m)) continue; else { color=m; sum++; } } } System.out.printf("着色方案:\n"); //求解完毕，输出着色方案 for(int i=1;i<=n;i++){ System.out.printf("%d ",color); } 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个顶点的无向图的数组 System.out.printf("输入无向图的邻接矩阵:\n"); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) c=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
下载源码：
页:
[1]