c用于涂色图的问题
发布时间
阅读量：
阅读量
问题描述：
针对包含五个顶点的无向连通图，探讨其四着色的相关问题。
思路：该问题与八皇后问题存在相似之处，同样可以采用回溯法进行逐步尝试。首先为任意一个顶点赋予颜色，随后依次为与其相邻的顶点进行染色，在此过程中不断尝试不同的颜色组合以确保相邻顶点的颜色不重复。
代码如下:
#include <stdio.h>
void visit(int g[],int n);
int canDraw(int c[][6],int n, int g[], int k)
{
int i = 1,flag = 1;//flag初始值为0的话，如果k=1,即给第一个节点涂色，下面的for循环都不满足，直接返回flag,为假，这就错了。
for(; i < k; i++)//涂第k个节点时，只要前k-1个已经涂好的节点如果有与这个节点相连颜色不同即可
{
if(c[i][k])
{
if(g[i] != g[k])
flag++;
else
{
flag = 0;
break;
}
}
}
return flag;
}全部评论 (0)
还没有任何评论哟~