测试例图：
程序输出结果图：
效率对比测试图：
程序输出图：
多次实验证明：回溯法比贪心法略快
源码奉上：
#include#include #include using namespace std; #define MVNum 29 typedef char VerTexType; typedef int ArcType; typedef int Status; static int color[100]; static string color_word[100]; static int BTcolor[100]; typedef struct { VerTexType vexs[MVNum]; //顶点表 ArcType arcs[MVNum][MVNum]; //邻接矩阵 int vexnum, arcnum; //图的当前点数和边数 }ALGraph; Status LocateVex(ALGraph G, VerTexType v) {//确定顶点在无向图G中的位置 int i; for (i = 0; i < G.vexnum; i++) if (G.vexs[i] == v) break; return i; } Status CreateUDG(ALGraph& G) {//采用邻接矩阵表示法，创建无向图G cout << "****************构建无向图****************" << endl; int i, j, k; char v1, v2; cout << "请输入总顶点数,总边数(以空格隔开)："; cin >> G.vexnum >> G.arcnum; //输入总顶点数，总边数 cout << "请输入点："; for (i = 0; i < G.vexnum; ++i) { cin >> G.vexs[i]; //依次输入点的信息 for (j = 0; j < G.vexnum; j++) G.arcs[i][j] = 0; ///矩阵的每个元素即边初始化为0 } cout << "请输入边依附的顶点(例如a b)" << endl; for (k = 0; k < G.arcnum; ++k) //构造邻接矩阵 { cout << "请输入第" << k + 1 << "条边："; cin >> v1 >> v2; //输入一条边依附的顶点及权值 i = LocateVex(G, v1); j = LocateVex(G, v2);//确定点v1和点v2在无向图G中的位置，即顶点数组下标 G.arcs[i][j] = 1; G.arcs[j][i] = G.arcs[i][j]; //对称边也设为1 } return 0; } int Ok(ALGraph& G, int i) //判断顶点i的着色是否发生冲突 { for (int j = 0; j < G.vexnum; j++) //分别与前面的已着色快进行比较 if (G.arcs[i][j] == 1 && color[i] == color[j]) return 0; //发生冲突 return 1; } void GAColorGraph(ALGraph& G) //贪心法求解图着色 { cout << "*************(贪心法)开始着色*************" << endl; int k = 0, flag = 1, n = G.vexnum; while (flag == 1) { k++; flag = 0; for (int i = 0; i < n; i++) { if (color[i] == 0) { color[i] = k; if (!Ok(G, i)) color[i] = 0; flag = 1; } } } } void BTColorGraph(ALGraph& G, int m) //回溯法求解图着色 { cout << "*************(回溯法)开始着色*************" << endl; int i, k, n = G.vexnum; for (i = 0; i < n; i++) //将数组color[n]初始化为0 color[i] = 0; k = 0; while (k >= 0) { color[k] = color[k] + 1; //取下一种颜色 while (color[k] <= m) if (Ok(G, k)) break; else color[k] = color[k] + 1; //搜索下一个颜色 if (color[k] <= m && k == n - 1) //求解完毕，退出循环去打印结果 break; if (color[k] <= m && k < n - 1) k = k + 1; //处理下一个顶点 else color[k--] = 0; //回溯到上一个顶点 } } void Stringsplit(const string& str, const string& split, vector & res)//使用正则分割字符串 { std::regex reg(split); // 匹配split std::sregex_token_iterator pos(str.begin(), str.end(), reg, -1); //第四个参数为-1时，表明该迭代器不会匹配所有捕捉组内的内容,不处理中间的空格 decltype(pos) end; // 自动推导类型(选择并返回操作数的数据类型) for (; pos != end; ++pos) { res.push_back(pos->str()); //往res数组里加入分割后的字串 } } void print(ALGraph& G, int choice) { cout << "着色结果如下:" << endl; if (choice == 1) { for (int i = 0; i < G.vexnum; i++) cout << "点" << G.vexs[i] << "着色：" << color_word[color[i] - 1] << endl; } else { for (int i = 0; i < G.vexnum; i++) cout << "点" << G.vexs[i] << "着色：" << color[i] << endl; } } int main() { //计时模块所需代码 double run_time = 0; //程序运行时间 //计时所需的相关变量 LARGE_INTEGER start_time; //开始时间 LARGE_INTEGER end_time; //结束时间 double dqFreq; //计时器频率 LARGE_INTEGER freq; //计时器频率 QueryPerformanceFrequency(&freq); dqFreq = (double)freq.QuadPart; cout << "请选择着色算法（1 贪心法； 2 回溯法）："; int choice; cin >> choice; if (choice == 1) { vector strList; // strList接收子串 string str; int i = 0; cout << "请输入颜色(例如：红 蓝 绿)："; int r = getchar(); getline(cin, str); //接收带空格输入 Stringsplit(str, " ", strList); for (auto s : strList) { color_word[i] = s; //string转int i++; } ALGraph G; //定义无向图G CreateUDG(G); //创建无向图G QueryPerformanceCounter(&start_time); //计时开始 GAColorGraph(G); //贪心法着色 QueryPerformanceCounter(&end_time); //计时结束 print(G, 1); //打印结果 run_time = (end_time.QuadPart - start_time.QuadPart) / dqFreq; //计时时间计算 cout << "n贪心法耗时：" << run_time * 1000.0 * 1000.0 << "皮秒" << endl; } else if (choice == 2) { cout << "请设定颜色的最大总数："; int m; cin >> m; ALGraph G; //定义无向图G CreateUDG(G); //创建无向图G QueryPerformanceCounter(&start_time); //计时开始 BTColorGraph(G, m); //回溯法着色 QueryPerformanceCounter(&end_time); //计时结束 print(G, 2); //打印结果 run_time = (end_time.QuadPart - start_time.QuadPart) / dqFreq; //计时时间计算 cout << "n回溯法耗时：" << run_time * 1000.0 * 1000.0 << "皮秒" << endl; } cout << endl; int r = getchar(); return 0; }
