Я нахожусь на вводном курсе C++ в универе, и у нас есть проблема, над которой я работаю день или два, но я застрял и не могу понять, почему. Лаборатория должна решить задачу раскраски графа с помощью рекурсии. Мы вводим файл, содержащий матрицу вершин и их ребер. Пример-
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.out k (количество цветов) и имя файла для чтения. Все работает, и я получаю правильные результаты, как я считаю, из того, что я тестировал на бумаге, но я всегда получаю сообщение об ошибке Segmentation fault (core dump). Я не уверен, почему это так, возможно, я пытаюсь получить доступ к несуществующему индексу, я не уверен. Кроме того, всякий раз, когда я использую 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)
Также код работает, когда цветов не хватает, но все равно выдает сообщение Segmentation fault(core dumped). В любом случае, любая помощь будет оценена по достоинству!
