贪心法进行图着色

《贪心法进行图着色》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、算法设计利用贪心法对图着色班级：110401班姓名：孟贺学号：201126385利用贪心法对图着色程序代码如下：#includeintarc[100][100];intn;//图中结点的总数intcolor[100];intbuildGraph()//构建图的邻接矩阵{intvertexNum;intarcNum;inti,j,k;printf("请输入结点总数！");scanf("%d",&vertexNum);n=vertexNum;printf("请输入图中边的总数！");sc

2、anf("%d",&arcNum);for(i=1;i<=vertexNum;i++)//初始化邻接矩阵{for(j=1;j<=vertexNum;j++){arc[i][j]=0;}}for(k=1;k<=arcNum;k++){if(k<=arcNum)printf("请输入图中相连接的两个结点");scanf("%d%d",&i,&j);arc[i][j]=1;arc[j][i]=1;}printf("该图的邻接矩阵为：");for(i=1;i<=vertexNum;i++){5for(j=1;

3、j<=vertexNum;j++){printf("%d",arc[i][j]);}printf("");}return0;}inttest(intm,intt)//判断是否冲突{intflag=1;for(intj=1;j<=n;j++){if(arc[m][j]==1&&color[j]==t)flag=0;}if(flag==0)return0;elsereturn1;}intdrawColor()//对结点进行着色{intk;intm=n;inti;color[1]=1;for(inti=2;i<

4、=n;i++){color[i]=0;}k=0;//############################################while(m>1){k++;5for(i=2;i<=n;i++){if(color[i]!=0){continue;}intflag=test(i,k);if(flag){color[i]=k;m--;}elsecontinue;}}//######################################################printf("着色结

5、果如下：");for(i=1;i<=n;i++){printf("结点颜色");printf("%d%d",i,color[i]);}}intmain(){buildGraph();drawColor();return0;}37465128实验示例如下：5程序运行结果如下：37465128即着色结果如右图所示：5