图的m着色问题-回溯法-深度搜索

2023-05-25 22:04

短信预约 -IT技能 免费直播动态提醒

问题描述：

给定无向连通图G=(V, E)和m种不同的颜色，用这些颜色为图G的各顶点着色，每个顶点着一种颜色。是否有一种着色法使G中相邻的两个顶点有不同的颜色。这个问题是图的m可着色判定问题。若一个图最少需要m种颜色才能使图中每条边连接的两个顶点着不同颜色，则称这个数m为该图的色数。求一个图的色数m的问题称为图的m可着色优化问题。

算法设计：

回溯法: 如果会了装载问题和 0-1背包的回溯解法，这个题目容易解出。代码如下：

代码：

#include <bits/stdc++.h>
using namespace std;
int m;
int pointnum;
int edgenum;
int sum = 0;
int Graph[100][100];
int x[100];
void InPut()
{
    int pos1, pos2;
    scanf("%d %d", &pointnum, &m);
    scanf("%d", &edgenum);
    memset(Graph, 0, sizeof(Graph));
    for(int i = 1; i <= edgenum; ++i)
    {
        scanf("%d %d", &pos1, &pos2);
        Graph[pos1][pos2] = Graph[pos2][pos1] = 1;
    }
}
bool IsOk(int i)
{
    for(int j = 1; j < i; ++j)
        if(Graph[i][j] == 1 && x[j] == x[i])
            return false;
    return true;
}
void BackTrack(int i)
{
    if(i > pointnum)
    {
        sum += 1;
        printf("方法 %d : ", sum);
        for(int j = 1; j <= pointnum; ++j)
        {
            printf("%d ", x[j]);
        }
        printf("\n");
        return;
    }
    else
    {
        for(int j = 1; j <= m; ++j)
        {
            x[i] = j;
            if(IsOk(i))
                BackTrack(i + 1);
            x[i] = 0;
        }
    }
}
void OutPut()
{
    printf("一共有 %d 中绘色方案", sum);
}
int main()
{
    InPut();
    BackTrack(1);
    OutPut();
}

免责声明：

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的，并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据，供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

图的m着色问题回溯法深度搜索 Graph c++

阅读原文内容投诉