C++递归图着色分段错误

Question

我在大学学习 C++ 简介 class，我们遇到了一个问题，我已经研究了一两天，但我一直卡住了，无法弄清楚原因。该实验室旨在通过递归解决图形着色问题。我们输入一个包含顶点及其边矩阵的文件。示例-

8
0  1  0  0  0  1  1  0  
1  0  1  1  1  0  0  0  
0  1  0  0  0  0  1  0  
0  1  0  0  1  0  0  1  
0  1  0  1  0  0  1  1  
1  0  0  0  0  0  1  0  
1  0  1  0  1  1  0  1  
0  0  0  1  1  0  1  0

顶点数为 8，按行优先顺序排列，0 表示没有边，1 表示各个顶点之间有边。这是我的其余代码，目前没有评论，抱歉。代码读入一个文件，建立一个矩阵，然后使用递归算法猜测并检查可用的颜色（k）是否足以完成图形着色问题。

//  Alex Cherecwich
//  Lab7
#include <iostream>
#include <cstdlib>
#include <iomanip>
#include <fstream>
using namespace std ;

// -----------------------------------------------------------------
class graph
{
    private:
        int n;
        int k;
        int ** G;
        int the_colors[];
        bool adj_vertex(int m, int c);
    public:
        graph(int x){k = x;}
        void read_graph(char * fname);
        void set_color();
        bool graph_color(int m);
} ;
// -----------------------------------------------------------------
void graph::read_graph(char *fname)
{
    ifstream ifs;
    ifs.open(fname);
    if(!ifs.is_open())
    {
        cerr << "Can not open (read) file '" << fname <<"'"<< endl;
        exit(1);
    }
    ifs >> n;
    G = new(nothrow) int *[n];
    for(int b = 0; b < n; b++)
    {
        G[b]= new(nothrow) int [n];
        for(int j=0; j< n; j++)
        {
            ifs >> G[b][j];
        }
    }
    ifs.close();
}
// -----------------------------------------------------------------
void graph::set_color()
{
    the_colors[n];
    for(int i = 0; i < n; i++)
    {
        the_colors[i] = -1;
    }
}
// -----------------------------------------------------------------
bool graph::adj_vertex(int m, int c)
{
    for(int i = 0; i < n; i++)
    {
        if(G[m][i] == 1 && the_colors[i] == c)
        {
            return false;
        }
    }
    return true;
}
// -----------------------------------------------------------------
bool graph::graph_color(int m)
{
    if(m == n)
    {
        cout << "Solution Found" << endl;
        cout << "Vertex" << "       " << "Color" << endl;
        for(int i = 0; i < n; i++)
        {
            cout << i << "      " << the_colors[i] << endl;
        }
        return true;
    }
    else
    {
        for(int c = 0; c < k; c++)
        {
            if(adj_vertex(m, c))
            {
                the_colors[m] = c;
                bool r = graph_color(m + 1);
                if(r) return true;
                the_colors[m] = -1;
                //return false;
            }
        }
        return false;
    }
}
// -----------------------------------------------------------------

int main(int argc, char **argv)
{
    int k = atoi(argv[1]);
    graph B(k);
    B.read_graph(argv[2]);
    B.set_color();
    if(B.graph_color(0) == false)
    {
    cout << "No Solution Found" << endl;
    }
    return 0;
}

输入应该是a.outk（颜色数）和要读取的文件名。一切正常，我相信从我在纸上测试的内容中得到正确的输出，但我总是收到分段错误（核心转储）错误消息。我不确定这是为什么，也许我正在尝试访问一些不存在的索引，我不确定。另外，每当我在上面的矩阵中使用 3 作为颜色数 (k) 时，我都会得到这个输出，这是正确的。

Solution Found
Vertex          Color
0               0
1               1
2               0
3               2
4               0
5               1
6               2
7               1
Segmentation fault (core dumped)

但是，每当我在上面的同一个矩阵上有 k>=4 时，我都会得到这个输出，它仍然有效但不是最有效的解决方案，如果解决方案是，我应该每次都输出它可能。

Solution Found
Vertex          Color
0               0
1               1
2               0
3               0
4               2
5               1
6               3
7               1
Segmentation fault (core dumped)

此外，代码在没有足够颜色的情况下也能正常工作，但它仍然会给出分段错误（核心已转储）消息。无论哪种方式，我们都将不胜感激！

Answer 1

您从未为 the_colors 分配内存。它指向任何地方，你很幸运你的程序能达到它的目的。

Answer 2

int the_colors[];

这不是合法的 C++。它是您的编译器提供的扩展，它不提供根据需要神奇地调整其大小的数组。不要使用它。

C++ 有 std::vector，用它来满足你所有与数组相关的需求。

C++递归图着色分段错误

C++ Recursion Graph Coloring Segmentation Fault

c++

recursion

segmentation-fault

graph-coloring