我必须编写 C++ 程序,它将确定我应该使用多少种颜色来为无向图着色。
此外,我必须使用“使用 C++ 伪代码的算法基础”一书中的算法来执行此操作。
问题描述:确定无向图中顶点可以着色的所有方式,只使用m种颜色,使得相邻顶点颜色不一样。
输入:正整数 n 和 m,以及包含 n 个顶点的无向图。该图由一个二维数组 W 表示,其行和列的索引从 1 到 n,其中 W [i] [j] 如果在第 i 个顶点和第 j 个顶点之间存在边,则为真,否则为假.
输出:图的所有可能的颜色,最多使用 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() 并且......这就是结束。我花了最后三个小时来找出我做错了什么,也许任何更有经验的程序员能够解释我应该做什么和/或我做错了什么......
请帮忙,非常感谢。
我的程序代码:
#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;
}