Chinaunix首页 | 论坛 | 博客
  • 博客访问: 474253
  • 博文数量: 117
  • 博客积分: 3195
  • 博客等级: 中校
  • 技术积分: 1156
  • 用 户 组: 普通用户
  • 注册时间: 2009-08-04 01:44
文章分类

全部博文(117)

文章存档

2012年(5)

2011年(5)

2010年(46)

2009年(61)

我的朋友

分类:

2009-09-04 16:29:51

图的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;
}


阅读(3127) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~