如何更改代码以便我可以获得彩色顶点图? [英] How Do I Change The Code So I Can Get A Colored Vertex Graph?
问题描述
我一般不会问这个问题,但我真的迷失了。
我试图以一种我使用尽可能少的颜色的方式为我的图形的顶点着色彼此相邻的两个顶点中没有一个具有相同的颜色。
我甚至无法理解编译时我的程序给出的答案我真的不知道我要去哪里错误!!!
I don't usually ask questions this generally but i'm really lost.
I'm trying to color the vertexes of my graph in a way that I use the least colors possible and that none of the two vertexes next to each other have the same color.
I can't even understand the answer my program gives me when I compile it and I really don't know where I'm going wrong!!!
class graphcoloring
{
int n,m;
int * Vcolor;
int **w;
public:
graphcoloring (int N)
{
n=N;
m=N;
w=new int*[n];
for(int i=0; i<=n; ++i)
{
w[i]=new int[n];
}
Vcolor=new int[m];
}
void m_coloring(int i)
{
int color;
if(promising(i))
if(i==n)
for(int i=1;i<=n;i++)
{
cout<<Vcolor[i] ;
}
else
for(color=1;color<=m;color++)
{
Vcolor[i+1]=color;
m_coloring(i+1);
}
}
bool promising(int i)
{
int j;
bool change;
change=true;
j=1;
while(j<i)
{
mode="hold";
if(w[i][j] && Vcolor[i]==Vcolor[j])
{
change=false;
j++;
}
return change;
}
}
}
void solve(){
n=1;
m=0;
m_coloring(1);
}
};
int main()
{
int n;
cout << " n ? " ; cin >> n;
graphcoloring s(n);
s.solve();
system("pause");
return EXIT_SUCCESS;
}
推荐答案
是的 - 看起来你好像迷路了。
使用指针Rethin你的代码:
Yeah - it really looks like you are lost.
Rethin your code with the pointers:
int n,m;
int * Vcolor;
int **w;
public:
graphcoloring (int N)
{
n=N;
m=N;
w=new int*[n];
for(int i=0; i<=n; ++i)
{
w[i]=new int[n];
}
Vcolor=new int[m];//nice pointer but no values
}
我的提示:首先提高你的代码质量
1.将所有变量和功能重命名为说出名字
2.使用一些简单的类对于int *的东西
3.插入一些调试输出(如果它工作就可以删除)
祝你好运; - )
My tip: first improve your code quality
1. rename all variables and funcitond to "speaking names"
2. use some simple class for the int* stuff
3. insert some debug output (if it works it can get removed)
good luck ;-)
这是一个比你想象的更大的问题!
参见顶点着色 [ ^ ]
注意(来自上面的链接):
This is a much bigger problem than you think!
See Vertex coloring[^]
Note (from the link above):
Graph coloring is computationally hard. It is NP-complete to decide if a given graph admits a k-coloring for a given k except for the cases k = 1 and k = 2. In particular, it is NP-hard to compute the chromatic number. The 3-coloring problem remains NP-complete even on planar graphs of degree 4.
这篇关于如何更改代码以便我可以获得彩色顶点图?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!