Мне нужно написать программу на C ++, которая определит, сколько цветов мне нужно использовать для окраски неориентированного графика.
Кроме того, я должен сделать это, используя алгоритм из книги «Основы алгоритмов с использованием псевдокода C ++».
Описание проблемы: Определить все способы, которыми можно окрашивать вершины в неориентированном графе, используя только m цветов, чтобы смежные вершины не были одного цвета.
Входные данные: натуральные числа n и m и неориентированный граф, содержащий n вершин. Граф представлен двумерным массивом W, в котором строки и столбцы имеют индексы от 1 до n, где W [i] [j] истинно, если существует ребро между i-й вершиной и j-й вершиной, и ложь в противном случае. .
Вывод: все возможные раскраски графа, использующие не более 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 && 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 (), следующий запуск 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 && 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;
}