贪心法进行图着色.docx

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

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

2、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++){for(j=1;j<=vertexNum;j++){prin

3、tf("%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<=n;i++){color[i]=0;}k=0;/

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

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