欢迎加入【企鹅之家交流群】,交流建站经验,共享热门影视资源,分享网赚经验。

回溯算法求解图的着色问题

问题描述:
给定一个无向图,用邻接矩阵表示,用回溯算法给图的顶点染色,使用颜色数目最少,并且有边相连的顶点不能染同一种颜色。
算法描述:
利用一个完全n叉树来表示解空间,用数组记录解向量,从根节点开始,每个顶点染一种颜色,并将此颜色记录到解向量中,然后判断子树根节点可染颜色,去除不可燃颜色的分支,直到叶子节点,生成一个解向量,判断该解向量是否是最优解,保存或弃之。直到所有解空间遍历完全;
由于问题求使用的颜色数目,无关乎具体颜色,所以a染红b染绿和a染绿b染红是一样的,采用第几个节点最多有几个颜色选择来减少遍历空间。

#include<iostream>
#include<fstream>
using namespace std;
ifstream in("in.txt");

class Color
{
public:
 void mcoloring();
private:
 void CreatGraph();
 void show();
 bool OK(int k);
 void Backtrack(int t);
 void showcolor();
 int n, //图的顶点数
 y, //图的边数
 c, //当前所用颜色数
 b, //最少颜色数
 **edge, //图的邻接矩阵
 *best, //最优解
 *x; //当前解
 char *node; //图的节点
};

void Color::CreatGraph()
{
 //cout << "please enter the number of node and edge" << endl;
 in >> n >> y;
 node = new char[n];
 edge = new int*[n];
 for (int i = 0; i<n; i++)
 edge[i] = new int[n];
 //cout << "please enter the node:" << endl;
 for (int i = 0; i<n; i++)
 {
 in >> node[i];//图节点
 }
 for (int i = 0; i<n; i++)
 {
 for (int j = 0; j<n; j++)
 {
 edge[i][j] = 0;//初始化图的所有边
 }
 }
 // cout << "please enter the edge(example:a b):" << endl;
 char m, x;
 int gx, gy;
 best = new int();
 for (int i = 0; i<y; i++)
 {
 in >> m >> x;
 for (int j = 0; j<n; j++)//找出有边的点所在的位置
 {
 if (node[j] == m) gx = j;
 if (node[j] == x) gy = j;
 }
 edge[gx][gy] = edge[gy][gx] = 1;//1表示gx、gy有边相连
 }
}

void Color::show()
{
 cout << "您创建的图如下:" << endl;
 for (int i = 0; i<n; i++)
 cout << " " << node[i];
 for (int i = 0; i<n; i++)
 {
 cout << "n" << node[i] << ":";
 for (int j = 0; j<n; j++)
 {
 cout << edge[i][j] << " ";//输出图边的情况 1表示相连
 }
 }
 cout << endl;
}

bool Color::OK(int k)
{
 for(int j=0; j<k; j++)
 {
 if((edge[k][j]==1)&&(x[j]==x[k])) return false;
 }
 return true;
}

void Color::Backtrack(int t)
{
 if(t>=n)//到达叶节点
 {
 if (c < b)//当前颜色数少于最少颜色数
 {
 for (int i = 0; i<n; i++)
 {
 best[i] = x[i];
 b = c;
 }
 }
 }
 else
 {
 for(int i=1; i<=t+1; i++)//染色
 {
 x[t]=i;
 if(i>c) c=i;
 if(OK(t)) Backtrack(t+1);
 x[t] = 0;//重置染色情况
 }
 }
}

void Color::showcolor()
{
 cout << "最少需要的颜色数为:" << b <<endl;
 for(int i=1;i<=b;i++)
 {
 cout << "结点";
 for(int j=0;j<n;j++)
 {
 if(best[j]==i)
 {
 cout << node[j];
 }
 }
 cout << "涂第" << i << "种颜色" << endl;
 }
}
void Color::mcoloring()
{
 CreatGraph();
 show();
 c = 0;
 b = n;
 x = new int[n];
 best = new int[n];
 for (int i = 0; i<n; i++)
 {
 x[i] = 0;
 best[i] = 0;
 }
 Backtrack(0);
 showcolor();
}

int main()
{
 Color color;
 color.mcoloring();
 return 0;
}

若无特别说明,本站所有文章均为企鹅之家原创,为了尊重站长的劳动成果,转载请注明本文固定链接:http://qiezhijia.wang/hui_su_suan_fa_qiu_jie_tu_de_zhe_se_wen_ti/良好的网络环境由你我共创!
喜欢 (0)or分享 (0)

您必须 登录 才能发表评论!