c++ - 使用邻接矩阵进行图形着色

Question

我正在尝试通过回溯解决着色问题。我无法获得正确的输出，但我的逻辑是正确的。我应该得到 1 2 3 2，但我得到的是 1 2 2 2。出了什么问题？

#include <iostream>

using namespace std;

#define V 4


bool isitsafetocolourVwiththisC(bool graph[V][V], int v, int c, int color[V])
{
    for (int i = 0; i < V; i++)
    {
        if(graph[v][i] && (c == color[i]))
            return false;
        return true;        
    }
}


bool graphColoring(bool graph[V][V], int m, int v, int color[V])
{
    if (v == V)
        return true;

    for (int i = 1; i <= m; i++) {
        if (isitsafetocolourVwiththisC(graph, v, i, color))
        {
            color[v] = i;
            if (graphColoring(graph, m, v+1, color))
                return true;
            color[v] = 0;
        }
    }
    return false;
}


void printcolours(int color[V])
{
    for (int i = 0; i < V; i++)
        cout << color[i] << " ";
}


int main()
{

    bool graph[V][V] = {{0, 1, 1, 1},
                        {1, 0, 1, 0},
                        {1, 1, 0, 1},
                        {1, 0, 1, 0}};
    int m = 3; // Number of colors
    int color[V];
    memset(color, 0, sizeof color);
    bool flag = graphColoring(graph, m, 0, color);
    if (flag)
        printcolours(color);
    else 
        cout << "Solution doesn't exist.";
    return 0;
}

Answer 1

如果你的逻辑是正确的，你的输出就会是正确的。 ;)

在我将 return true 移出 for 循环之后，我自己运行了这个来确认。它现在可以正常工作。

bool isitsafetocolourVwiththisC(bool graph[V][V], int v, int c, int color[V])
{
    for(int i=0;i<V;i++)
    {
        if(graph[v][i] &&  (c == color[i]))
            return false;
        // Not returning here anymore!
    }
    return true;
}

原因是在另一个地方，您永远不会处理列表的任何其他元素。您必须在第一个元素之后返回 true 或 false。

我不知道您使用的是哪个编译器，但是 clang 会提示您的原始代码 — 让编译器帮助您。

myfile.cpp:15:1: warning: control may reach end of non-void function
      [-Wreturn-type]
}