3

無向グラフの色付けに使用する色数を決定する C++ プログラムを作成する必要があります。

また、本「C++疑似コードを使用したアルゴリズムの基礎」のアルゴリズムを使用してこれを行う必要があります。

問題の説明:隣接する頂点が同じ色にならないように、無向グラフの頂点を m 色のみを使用して色付けできるすべての方法を決定します。

入力:正の整数 n と m、および n 個の頂点を含む無向グラフ。グラフは 2 次元配列 W で表され、行と列の両方に 1 から n までのインデックスが付けられます。ここで、i 番目の頂点と j 番目の頂点の間にエッジがある場合は W [i] [j] が true であり、そうでない場合は false です。 .

出力: 2 つの隣接する頂点が同じ色にならないように、最大​​で m 色を使用する、グラフのすべての可能な色付け。各カラーリングの出力は、1 から n までのインデックスが付けられた配列 vcolor です。ここで、vcolor [i] は i 番目の頂点に割り当てられた色 (1 から m までの整数) です。

そこにアルゴリズムがあります：

void m_coloring (index i)
{
    int color;
    if (promising (i))
        if (i == n)
            cout << vcolor [1] through vcolor [n];
        else
            for (color = 1; color <= m; color++){ // Try every
                vcolor [i + 1] = color;           // color for
                m_coloring (i + 1);               // next vertex.
            }
}

bool promising (index i)
{
    index j;
    bool switch;

    switch = true;
    j = 1;
    while (j && switch){                       // Check if an
        if (W[i][j] && vcolor[i] == vcolor[j]) // adjacent vertex
            switch = false;                    // is already
        j++;                                   // this color.
    }
    return switch;
}

そして最後にコメントしてください:通常の規則に従って、n、m、W、および vcolor はどちらのルーチンにも入力されません。アルゴリズムの実装では、ルーチンは、n、m、および W を入力として持つ単純な手順でローカルに定義され、vcolor はローカルで定義されます。m_coloring の最上位呼び出しはm_coloring( 0 ) です。

私は自分自身の実装を書き始めます。最初に言いたいのは、私は C++ プログラマーが得意ではないということです。さらに、普段は JS や PHP などの弱い型付け言語を使用しているので、もっとうまくできることがたくさんあると確信しています。しかし、それは主な問題ではありません。

問題は:上記のプログラムが動作し始め、簡単なグラフを書きます:

4 つの頂点、4 つのエッジ

1 2
1 3 2 3 3 4

次に、プログラムはcheckFor()を使用し始めます(次の色数ごとに for() で使用する予定でしたが、テスト目的で静的に使用するため、4 を使用しました。

残念ながら、プログラムは m_coloring() を起動し、次に promise() を起動し、そして...これで終わりです。私は最後の 3 時間を費やして、自分が何を間違っているかを調べました。経験豊富なプログラマーなら、私が何をすべきか、および/または何が間違っているかを説明できるかもしれません...

助けてください、どうもありがとう。

私のプログラムコード:

#include <iostream>

using namespace std;

bool **W;
int n, m = 0;
int v, e = 0;
int x, y = 0;
int *vcolor;

bool promising (int i)
{
    int j = 1;
    bool switcher = true;

    while (j && switcher)
    {   
        if ( W[i][j] && vcolor[i] == vcolor[j] )
        {
            switcher = false;
        }

        j++;
    }

    return switcher;
}

void m_coloring (int i)
{
    int color;
    if ( promising (i) )
    {
        if (i == n)
        {
            cout << vcolor [1] << " through " << vcolor [n];
        }
        else
        {
            for (color = 1; color <= m; color++)
            {      
                vcolor [i + 1] = color;
                m_coloring(i + 1);
            }
        }
    }
}

void initArrays()
{
    for( int i = 0; i < n; i++ )
    {
        W[ i ] = new bool[ n ];
        vcolor[ i ] = 0;
    }
}

void fillW()
{
    for( int i = 0; i < n; i++ )
    {
        for( int j = 0; j < n; j++ )
        {
            if( !W[i][j] )
            {
                W[i][j] = false;
            }
        }
    }
}

void askForEdges()
{
    cout << "How many edges? ";
    cin >> e;
    cout << endl << "Write edges with pattern: [vertex_x][space][vertex_y]:" << endl;

    for( int i = 0; i < e; i++ )
    {
        cin >> x >> y;

        W[x][y] = true;
        W[y][x] = true;
    }
}

void specialMatrixPrint()
{
    cout << endl;
    int i, j;
    for( i = 0; i < n; i++ )
    {
        for( int j = 0; j < n; j++ )
        {
            cout << W[i][j] << " ";
        }
        cout << endl;
    }
}

void showEdgesMatrix()
{
    int i, j = 0;

    cout << endl << "    "; for( i = 1; i < n; i++ ) { cout << i << " "; } cout << endl;
    cout << endl << "    "; for( i = 1; i < n; i++ ) { cout << "# "; } cout << endl;

    for( i = 1; i < n; i++ )
    {
        cout << i << " # ";
        for( int j = 1; j < n; j++ )
        {
            if( W[i][j] == true ) { cout << "1 "; }
            else { cout << "0 "; }
        }

        cout << endl;
    }
}

void showVcolor()
{
    cout << endl;
    for( int i = 1; i < n; i++ )
    {
        cout << i << ": " << vcolor[ i ] << endl;
    }
}

void checkFor( int i )
{
    m = i;
    m_coloring( 0 );
}

int main()
{
    cout << "How many vertexes? " ;
    cin >> n;

    n += 1;

    W = new bool *[ n ];
    vcolor = new int[ n ];

    initArrays();
    askForEdges();
    showEdgesMatrix();

    checkFor( 4 );
    showVcolor();

    cin >> y;

    return 0;
}
4

4 に答える 4

1

主に有望な問題がたくさんあります。覚えておくべき主なことは、色が設定されているノードのみを比較し、ノードをそれ自体と比較しないことです。また、配列が1つの再帰をより浅いものにすることを約束していたという事実を使用し、帰納的推論を使用してすべてのペアを比較しないようにすることもできます。

ネタバレ：

http://ideone.com/Lk0mg

于 2011-05-30T21:18:47.470 に答える
0

アルゴリズムにバグがあります。関数promisingには、適切な配列境界のオーバーランがあります。彼らはおそらく、j < nまたはj <= nその間の状態のようなものを意味していましたstatement. 書かれているように、条件は意味がありません。

于 2011-05-30T20:25:08.040 に答える
-1

アルゴリズムが間違っています.... アルゴリズムを見てください:

 void m_coloring (index i)
{
    int color;
    if (promising (i))
        if (i == n)
            cout << vcolor [1] through vcolor [n];
        else
            for (color = 1; color <= m; color++){ // Try every
                vcolor [i + 1] = color;           // color for
                m_coloring (i + 1);               // next vertex.
            }
/* HERE..................................*/
}

w[i] の prodius の別の色に行くには、アルゴリズムの最後に別の else ステートメントが必要ですが、次のレベルに進みます!!!!!!!!!.

于 2016-01-18T16:49:03.013 に答える
-1

関数m_coloringが最初に呼び出されたときに、 i=1, vcolor[i+1] = colorisvcolor[2]=colorとvcolor[1]is が欠落しています..次回、promise switch によってチェックされると、値 true が常に返されます..

于 2013-12-31T15:29:08.630 に答える