Блог

Я должен написать программу на C , которая определит, сколько цветов я должен использовать для раскрашивания неориентированного графика.

Кроме того, я должен сделать это, используя алгоритм из книги «Основы алгоритмов с использованием псевдокода C «.

Описание проблемы: Определите все способы, которыми вершины в неориентированном графе могут быть окрашены, используя только m цветов, чтобы смежные вершины не были одного цвета.

Входные данные: целые положительные числа n и m и неориентированный граф, содержащий n вершин. Граф представлен двумерным массивом W, строки и столбцы которого проиндексированы от 1 до n, где W [i] [j] равно true, если между i-й вершиной и j-й вершиной есть ребро, и false в противном случае.

Вывод: все возможные раскраски графика с использованием не более m цветов, так что никакие две смежные вершины не будут одинакового цвета. Выходные данные для каждой раскраски представляют собой массив vcolor, индексированный от 1 до n, где vcolor [i] — это цвет (целое число от 1 до m), присвоенный i-й вершине.

Здесь у нас есть алгоритм:

 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 amp;amp; switch){                       // Check if an
        if (W[i][j] amp;amp; 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(), следующий запуск promising() и … это конец. Я трачу последние три часа, чтобы выяснить, что я делаю не так, возможно, любой более опытный программист сможет объяснить мне, что я должен делать и / или что я делаю не так…

Пожалуйста, помогите, большое вам спасибо.

Мой программный код:

 #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 amp;amp; switcher)
    {   
        if ( W[i][j] amp;amp; 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;
}
  

У вас целая куча проблем, в основном в promising. Главное, что нужно помнить, это то, что вы хотите сравнивать только узлы, для которых был установлен свой цвет, а не сравнивать какой-либо узел с самим собой. Также вы можете использовать тот факт, что массив обещал на одну рекурсию меньше, и использовать индуктивные рассуждения, чтобы избежать сравнения всех пар.

Спойлер:

http://ideone.com/Lk0mg

В алгоритме есть ошибка. В функции promising наблюдается хороший перерасход границы массива. Вероятно, они имели в виду что-то вроде j < n или j <= n в условии while statement . Как написано, условие не имеет смысла.

первый раз, когда функция m_coloring вызывается с i=1, vcolor[i 1] = color значением vcolor[2]=color и vcolor[1] , пропускается .. поэтому в следующий раз, когда она получит проверку с помощью promising switch, всегда будет возвращено значение true..

Алгоритм неверен…. Посмотрите на алгоритм:

  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..................................*/
}
  

У нас должно быть другое утверждение else в нижней части алгоритма, чтобы выбрать для prodius другой цвет для w [i], Но это переходит на следующий уровень!!!!!!!!!.Я думаю, что это проблема