贪心法进行图着色

算法设计利用贪心法对图着色班级：110401班姓名：孟贺学号：201126382利用贪心法对图着色程序代码如下：#includestdio.hintarc[100][100];intn;//图中结点的总数intcolor[100];intbuildGraph()//构建图的邻接矩阵{intvertexNum;intarcNum;inti,j,k;printf(请输入结点总数！\n);scanf(%d,&vertexNum);n=vertexNum;printf(请输入图中边的总数！\n);scanf(%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(\n该图的邻接矩阵为：\n);for(i=1;i=vertexNum;i++){3for(j=1;j=vertexNum;j++){printf(%d,arc[i][j]);}printf(\n);}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;//############################################while(m1){k++;4for(i=2;i=n;i++){if(color[i]!=0){continue;}intflag=test(i,k);if(flag){color[i]=k;m--;}elsecontinue;}}//######################################################printf(\n着色结果如下：\n);for(i=1;i=n;i++){printf(结点颜色\n);printf(%d%d\n,i,color[i]);}}intmain(){buildGraph();drawColor();return0;}实验示例如下：374651285程序运行结果如下：即着色结果如右图所示：37465128