贪心法求解着色问题。
给图的所有结点着色,限制是一条边的两个端点不能用同样的颜色,要求所使用的不同颜色的数目最少。
“贪心”算法的思想是首先 用第一种颜色对图中尽可能多的顶点着色(“尽可能多”表现出“贪心”);然后用第二种颜色对余下的顶点中尽可能多的顶点着色;如此等等,直到把所有的顶点都着完色。当用一种新颜色对余下的顶点着色时,我们采取下列步骤:
(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
下载源码:
分享到:
相关推荐
贪心法求解图的着色问题C++源代码,可直接编译运行。 greedy.
贪心方法:总是对当前的问题作最好的选择,也就是局部寻优。最后得到整体最优。应用:1:该问题可以通过“局部寻优”逐步过渡到“整体最优”,这是贪心选择性质与“动态规划”的主要差别。2:最优子结构性质:某个...
本压缩文档包含三个文件:用贪心法解决TSP问题可执行源代码,word文档报告,实验测试数据
使用贪心算法求解tsp问题,使用vc实现,资源中包含有程序的文档,包含tsp问题说明、贪心算法分析和程序源码。
基于贪心法求解单源最短路径问题 完整实验报告,结尾有实验代码
用贪心算法实现背包问题 集SSH框架,android,行业资讯,数据库,web开发,设计模式希望大家一起分享
算法设计实验报告,包括:贪心法求解背包问题的基本思想、动态规划法求解0/1背包问题的基本思想及各自的时间复杂度分析,两种问题的区别,C++实现代码,运行截图,实验心得。
为C语言课程设计写的基于贪心法的背包问题,包含全部4种贪心策略
代码中给出了用贪心法解决活动安排问题的集中方案。。用c++实现的,希望能给您帮助。
用贪心法解决背包问题的源代码,在vc++环境下也可以运行
热心学姐来送福利啦哈哈哈哈哈哈哈哈哈哈哈哈哈,西北农林科技大学的算法分析实验报告,
背包问题的贪心法求解.exe
这是用C++语言写的一个关于图着色的问题。对于初学算法的人有帮助。
背包问题的贪心算法实现,简答易懂 if(m>=weight[i]) { value=value+profit[i]; m-=weight[i]; s[i]=1; } else if(m!=0) { value=value+profit[i]*(1.0*m/weight[i]); s[i]=1.0*m...
用贪心法的思想,设计算法编程解决如下现实问题:码头上有n艘船舶同时等待装卸,而码头每次只能装卸一艘船舶。船舶i需要装卸的时间为ti,1≤i≤n。应如何安排这n艘船舶的装卸次序才能使得总的等待时间达到最小?(总...
课程的随堂作业,C语言的,用dev就能运行,萌新代码,勿喷,仅仅帮助不想写作业的朋友方便一下,反正老师也不会仔细检查的
数据结构TSP问题贪心法求解.doc
这是个利用贪心法解决存储问题,希望对你们有用,嘻嘻。
综合运用贪心算法,求解不同数目的找零钱问题的源程序