图的m着色问题：
给定无量连通图g和m种颜色，用这些颜色为图g的各个顶点着色，每个顶点着一种，是否有一种着色法使图中每条边的两个顶点着有不同的颜色。
算法设计：
给定图g（v，e）和m种颜色，如果这个图不是m可着色，给出否定回答，是的话找出所有不同着色法。
分析：
用邻接矩阵表示图g，如果顶点i跟j之间有边，则g[i][j] = 1,否则g[i][j] = 0.用整数1，2，...，m表示m种颜色，顶点i的颜色用x[i]表示，所以x[1：n]是一种着色方案。
在算法traceback中，当i>n时，就是所有顶点都上了色，得到新的m着色方案，当前m着色方案总数sum增一，输出方案。
当i
代码如下：
|
#include <stdio.h>
#include <conio.h>
#define N 20
int n, sum = 0, m;
int x[N+1];
int g[N+1][N+1];
int ok(int t)
{
for(int j = 1; j<=n; j++)
if(t != j)
{
if(g[t][j] == 1 && x[t] == x[j])
return 0;
}
return 1;
}
void back_track(int t)
{
int i;
if(t > n)
{
sum++;
for(i=1; i<=n; i++)
printf("%d ", x[i]);
printf("\n");
}
else
{
for(int i = 1; i <= m; i++)
{
x[t] = i;
if(ok(t))
back_track(t+1);
x[t] = 0;
}
}
}
int main()
{
int k, i, j;
freopen("in.txt", "r", stdin);
scanf("%d%d", &n, &m); //n个顶点，m种颜色
for(i=1; i<=n; i++)
for(j=1; j<=n; j++)
{
scanf("%d", &g[i][j]);
g[j][i] = g[i][j];
}
back_track(1);
printf("sum ：%d\n", sum);
getch();
return 0;
}
|
input：
4 4
0 1 1 0
1 0 1 1
1 1 0 1
0 1 1 0
output：
1 2 3 1
1 2 3 4
1 2 4 1
....... //太多了，省略输出几种
4 3 2 1
4 3 2 4
sum ：48
----------------------------------------
最近重新学习搜索，dfs喜欢用非递归的， 补充在后面吧；
这是poj1129
#include <stdio.h>
#include <string.h>
#define N 27
int g[N][N];
int c[N]; //放每个点的颜色
char *is[5] = {" ", "channel", "channels", "channels", "channels"};
int isok(int x, int k)
{
int i;
for(i=0; i<k; i++)
{
if(g[i][k] && c[i] == x)
return 0;
}
return 1;
}
int solve(int n, int m)
{
int k;
memset(c, 0, sizeof(c));
k = 0;
c[k] = 0;
while(k >= 0)
{
c[k]++;
for(; c[k]<=m; c[k]++)
{
if(isok(c[k], k))
break;
}
if(c[k] <= m)
{
if(k == n-1)
return 1;
else
k++;
}
else
{
c[k] = 0;
k--;
}
}
return 0;
}
int main()
{
int n, i;
char a, c;
freopen("1129.in", "r", stdin);
while(scanf("%d", &n), n)
{
memset(g, 0, sizeof(g));
for(i=0; i<n; i++)
{
scanf(" %c:", &a);
while(scanf("%c", &c), c!='\n')
{
g[a-'A'][c-'A'] = 1;
}
}
for(i=1; i<5; i++)
if(solve(n, i))
{
printf("%d %s needed.\n", i, is[i]);
break;
}
}
return 0;
}
|
阅读(3119) | 评论(0) | 转发(0) |
