当前位置:首页 » 操作系统 » 图的着色算法

图的着色算法

发布时间: 2024-10-08 16:08:42

1. 图的着色4个顶点 给了3种颜色 如何给4个顶点着色 使之有连边关系的顶点颜色不同有多少种着色方法 编程解决

设计说明:
1 四个顶点用 0,1,2,3表示,三种颜色用A,B,C表示。
2 输出结果 0 -- ABAC ,表示 从0 顶点向1,2,3 方向着色方案为0-A,1-B,2-A,3-C。有连边 关系但顶点不同颜色。
3 用 char c[4][5]={{'A','B','A','C','\0'},{'B','A','B','C','\0'},{'C','A','C','B','\0'}};
先给出连边不同色三种基本方案,用以简化问题。
4 用三重循环分别模拟确定第一点、输出方案、改变着色方案三个事件。
5 用
t=c[i][i];c[i][i]=c[i][(i+1)%4];c[i][(i+1)%4]=c[i][(i+2)%4];c[i][(i+2)%4]=c[i][(i+3)%4];c[i][(i+3)%4]=t;
实现 ABAC-->BACA 转换,巧妙地解决了‘连边不同色’的算法难题。
程序如下:
#include <stdio.h>
main(void)
{
int i,j,k,n=0;
char c[4][5]={{'A','B','A','C','\0'},{'B','A','B','C','\0'},{'C','A','C','B','\0'}};
char t;
for(i=0;i<3;i++)
for(j=0;j<4;j++)
{
for(k=0;k<4;k++)
{ printf("%d -- %s\t",k,c[i]); /*(k+3)%4,c[(k+3)%4]);*/
n++; }
printf("\n");
t=c[i][i];c[i][i]=c[i][(i+1)%4];c[i][(i+1)%4]=c[i][(i+2)%4];c[i][(i+2)%4]=c[i][(i+3)%4];c[i][(i+3)%4]=t;
}
printf("\n total = %d",n);
getchar();
}

热点内容
低温存储测试 发布:2025-03-14 12:10:22 浏览:244
c语言二维数组的输出 发布:2025-03-14 11:58:10 浏览:25
安卓脚本自动运行 发布:2025-03-14 11:49:35 浏览:354
yii页面缓存 发布:2025-03-14 11:45:51 浏览:798
c语言算法书 发布:2025-03-14 11:45:26 浏览:264
安卓动漫插件在哪里 发布:2025-03-14 11:41:11 浏览:660
linux复制系统文件到 发布:2025-03-14 11:29:45 浏览:40
腰2椎体压缩性骨折多久能干活 发布:2025-03-14 11:29:34 浏览:168
脚本挖图全自动 发布:2025-03-14 11:28:51 浏览:77
redis缓存有效期 发布:2025-03-14 11:28:45 浏览:739