私はuniのイントロC++クラスに入っています。私は1日か2日作業していましたが、問題がありました。ラボは、再帰を使用してグラフ着色の問題を解決することです。私たちは、頂点の行列とそのエッジを持つファイルを入力します。例 -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(色数)と読み込むファイルの名前でなければなりません。すべてが動作し、私が紙でテストしたものから信じる正しい出力が得られますが、私は常にセグメンテーションフォールト(コアダンプされた)エラーメッセージを受け取ります。私はなぜこれが、おそらく私は存在しないいくつかのインデックスにアクセスしようとしているのか分からない、私はわからない。また、上記の行列の色数(k)を3にすると、この出力が得られます。これは正しいです。
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)
また、コードは十分な色がない場合でも機能しますが、それでもセグメンテーションフォルト(コアダンプ)メッセージが表示されます。いずれにしても、すべての助けをいただければ幸いです!
これは私が上記のマトリックスを視覚的に表すページです。 http://menehune.opt.wfu.edu/csc112/Labs/Lab7/g.png –