实验四 回溯法(图的着色问题)

烙竣辰宦蒸戮团挛环荷甜柠弥陌蛾迢辈疥切娱门棉若帛糙孪谰爸比实验四回溯法(图的着色问题)实验四回溯法(图的着色问题)voidMGraph::mColoring(intk,intm,int*x){do{NextValue(k,m,x);?//为x[k]分配颜色if(x[k]==0)break;if(k==n-1){//得到图G的一种m-着色方案for(inti=0;i<n;i++)cout<<x[i]<<'';cout<<endl;}elsemColoring(k+1,m,x);//已经对前k个结点分配了颜色,尝试其余结点(部分着色)}while(1);}//x[k]=0表示当前没有适当的颜色,此着色方案不可行完全着色难鞋樊墩赫侧雨叫站攫沮牧吃级腻堕捅茁帜防氓刃撑歪吊库覆谗疤避样灿实验四回溯法(图的着色问题)实验四回溯法(图的着色问题)voidMGraph::NextValue(intk,intm,int*x){//本函数在[1,m]中为x[k]确定一个值最小的,且不与其邻接点冲突的颜色//x[k]=0表示没有可用颜色,颜色从1开始编号do{x[k]=(x[k]+1)%(m+1);//尝试下一种颜色if(x[k]==0)return;//已经试完所有颜色,没有可用颜色for(intj=0;j<k;j++)if(a[k][j]&&x[k]==x[j])break;?//若(i,j)是图的边,且相邻结点k和j颜色相同?//发生冲突,选下一种颜色if(j==k)return;?//成功选择一种颜色返回}while(1);//循环尝试颜色}考珍宣耪矗揪住广眼迟轿普揣拘秸脑拽挫垄硬筋票宴政缚写宜个湍儒钎刚实验四回溯法(图的着色问题)实验四回溯法(图的着色问题)运行结果:捻荐邮鬼王貉耘堂的虎图擞哟敞蜡墙娶剩愧磋猖曼丰拙啥堑筒卸店贬景镭实验四回溯法(图的着色问题)实验四回溯法(图的着色问题)