图着色问题回溯法

///图着色问题回溯法
/**
无向图邻接矩阵示例
1 0 0 0
1 0 1 0
0 0 1 0
0 0 1 0
1 1 0 0
https://www.cnblogs.com/kimsimple/p/6664299.html

 与教材P157思路相通 教材是找一个解 治理是找所有的解
*/

#include "cstdio"
#include "cstring"
int color[500];
bool ok(int k,int c[][100]) //顶点k的着色与其他顶点的着色是否发生冲突
{
    for(int i=1;i<k;i++)
    {
        if(c[k][i]==1&&color[i]==color[k]) //结合线性代数矩阵进行理解
            return false; //冲突
    }
    return true; //不冲突
}
int graphColor(int n,int m,int c[][100])
{
    int cnt=0;
    memset(color,0,sizeof(color));
    int k=1;
    while(k>=1)
    {
        color[k]+=1;///染第一种颜色
        while(color[k]<=m)
        {
            if(ok(k,c))
                break;
            else
                color[k]++;///搜索下一个颜色
        }///挑选合适颜色
        if(color[k]<=m&&k==n)///找完  输出
        {
            for(int i=1;i<=n;i++)
                printf("%d ",color[i]);
            printf("\n");
            cnt++;
        }
        else if(color[k]<=m&&k<n)
        {
            k++;///染下一个顶点
        }
        else
        {
            color[k]=0;///回溯 找其他方法 ？？？？ 这一点始终不理解
            k--;
        }
    }
    return cnt;
}
int main()
{
    int n,m,i,j;
    int c[100][100];//为避免函数之间的参数传递，可以置为全局变量
    printf("输入顶点数n和着色数m:\n");
    scanf("%d %d",&n,&m);
    printf("输入无向图的邻接矩阵:\n");
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            scanf("%d",&c[i][j]);
    printf("着色所有可能的解:\n");
    int cnt=graphColor(n,m,c);
    printf("方案数: %d\n",cnt);
}

/**
5
7
1 2
1 5
1 4
2 5
2 3
3 4
4 5
 5个点   7个边   然后是7个边的两端
 递归  为什么结果是多组解？？
 */
#include <iostream>
#include <memory.h>
#define COLOR_COUNT 3
bool graph[100][100];		// 点的编号从1开始
int colors[100] = { 0 };	// 每个点已经选择的颜色, 默认0
int point_count;

// 对c节点及其子节点尝试每一种着色方案
void dg(int c) {
    if (c == point_count + 1) {
        for (int i = 1; i <= point_count; ++i) {
            printf("%d ", colors[i]);
        }
        printf("\n");
        return;
    }
    // 找到与该节点相连的点用过的颜色
    bool* flag = new bool[COLOR_COUNT + 1];
    memset(flag, false, (COLOR_COUNT + 1) * sizeof(bool));
    for (int i = 1; i < c; ++i) {
        if (graph[c][i] && colors[i]) {
            flag[colors[i]] = true;
        }
    }
    // 依次尝试每一种颜色
    for (int i = 1; i <= COLOR_COUNT; ++i) {
        if (flag[i]) continue;	// 如果颜色被用过 取消
        colors[c] = i;			// 使用颜色i
        dg(c + 1);				// 递归
        colors[c] = 0;			// 取消颜色
    }
    delete[] flag;
}

int main() {
    memset(graph, false, sizeof(graph));
    scanf("%d", &point_count);
    int edge_connt;
    scanf("%d", &edge_connt);
    for (int i = 0; i < edge_connt; ++i) {
        int a, b;
        scanf("%d%d", &a, &b);
        graph[a][b] = true;
        graph[b][a] = true;
    }
    dg(1);
    return 0;
}