目录
前言
本次解决的问题：用图模拟部分地图，对各省进行着色，要求相邻省所使用的颜色不同，并保证使用的颜色总数最少。
先来一张效果图
一、解决问题的思路
将邻接矩阵创建好了以后，通过回溯函数，在解空间树中搜索所有的可行解，如果着色有冲突，就回溯到上一个节点。一旦到达叶子节点，也就是这个解到头了，就输出这种着色方案。
二、存储结构设计
a）
抽象数据类型：
ADT Graph{
数据对象V：一个非空集合，该集合中的所有元素具有相同的特性。
数据关系R：R={VR}，VR={<x,y> | P(x,y) ∧(x,y∈V)}
基本操作：
Createmap(&G)
操作前提:已知图G不存在。
操作结果:创建图G。
}ADT Graph;
(b) 存储结构：顺序表存储结构
typedef struct{
char vertax[MAX][MAX];//顶点所属的省份
int map[MAX][MAX]; //邻接矩阵
int n; //顶点个数
int m;//边的个数
}Graph;
三、代码
1.创建图函数
这里没什么好说的，都是创建图所需要的输入。顶点个数，顶点所代表的省份也就是顶点名称，边的个数，有边相连的两个顶点。
void Createmap(Graph &G) //创建邻接矩阵
{
printf("请输入顶点(省份)个数：");
int f=scanf("%d", &G.n);
while(f!=1)
{
printf("输入值非法！\n");
printf("请重新输入顶点(省份)个数：");
fflush(stdin);
f=scanf("%d", &G.n);
}
for(int i=1;i<=G.n;i++)
{
printf("请输入第%d个顶点所代表的省份：",i);
cin>>G.vertax[i];
}
int u; //顶点1
int v; //顶点2
cout << "\n请输入边的个数：";
cin >> G.m;
cout << "请输入有边相连的两个顶点u和v："<< endl;
for (int i=1;i<=G.m;i++)//为邻接矩阵赋值
{
cin>>u>>v;
G.map[u][v]=1;
G.map[v][u]=1;
}
cout<<endl;
}2.判断色号是否相同函数
先判断是否相连，如果相连则判断两个顶点颜色是否一样。如果顶点颜色不冲突，就返回真，反之返回假。
bool Find(Graph G,int t) //判断色号是否相同的函数
{
for(int j=1;j<t;j++) //判断现在扩展点t和前面t-1个顶点有没有相连的
{
if(G.map[t][j]) //如果相连
{
if(color[j]==color[t]) //且颜色一样
{
return false; //返回false，表示需要换个色号尝试
}
}
}
return true;
}3.回溯函数
判断是否到达了叶子节点，如果没有，则开始试探这个顶点着此颜色行不行，行就向下递归，进入下一个节点开始着色试探，不行就换一种颜色继续试探，直到所有颜色被试探完。
void Backtrack(Graph G,int t) //回溯函数
{
if(t>G.n) //到达叶子节点，打印一种填色方案
{
answer=0;//找到最少的颜色个数
sum++; //方案个数+1
cout << "第"<< sum << "种方案：";
for (int i=1;i<=G.n;i++)
{
cout << color[i] << " ";
}
cout << endl;
}
else
{
for (int i=1;i<=color_nums;i++) //尝试别的色号
{
color[t]=i; //试探色号i
if(Find(G,t)) //如果色号没有撞
{
Backtrack(G,t+1); //向下递归
}
}
}
}4.整体代码
#include <iostream>
using namespace std;
const int MAX=111;//最大存储个数
typedef struct{
char vertax[MAX][MAX];//顶点所属的省份
int map[MAX][MAX]; //邻接矩阵
int n; //顶点个数
int m;//边的个数
}Graph;
int color[MAX]; //解空间，表示第i个省所填的颜色
int sum=0; //记录有多少种方案
int color_nums=0; //颜色数量
int answer=1;
void Createmap(Graph &G) //创建邻接矩阵
{
printf("请输入顶点(省份)个数：");
int f=scanf("%d", &G.n);
while(f!=1)
{
printf("输入值非法！\n");
printf("请重新输入顶点(省份)个数：");
fflush(stdin);
f=scanf("%d", &G.n);
}
for(int i=1;i<=G.n;i++)
{
printf("请输入第%d个顶点所代表的省份：",i);
cin>>G.vertax[i];
}
int u; //顶点1
int v; //顶点2
cout << "\n请输入边的个数：";
cin >> G.m;
cout << "请输入有边相连的两个顶点u和v："<< endl;
for (int i=1;i<=G.m;i++)//为邻接矩阵赋值
{
cin>>u>>v;
G.map[u][v]=1;
G.map[v][u]=1;
}
cout<<endl;
}
bool Find(Graph G,int t) //判断色号是否相同的函数
{
for(int j=1;j<t;j++) //判断现在扩展点t和前面t-1个顶点有没有相连的
{
if(G.map[t][j]) //如果相连
{
if(color[j]==color[t]) //且颜色一样
{
return false; //返回false，表示需要换个色号尝试
}
}
}
return true;
}
void Backtrack(Graph G,int t) //回溯函数
{
if(t>G.n) //到达叶子节点，打印一种填色方案
{
answer=0;//找到最少的颜色个数
sum++; //方案个数+1
cout << "第"<< sum << "种方案：";
for (int i=1;i<=G.n;i++)
{
cout << color[i] << " ";
}
cout << endl;
}
else
{
for (int i=1;i<=color_nums;i++) //尝试别的色号
{
color[t]=i; //试探色号i
if(Find(G,t)) //如果色号没有撞
{
Backtrack(G,t+1); //向下递归
}
}
}
}
void Print()
{
printf("\n最少需要%d种颜色",color_nums);
}
int main()
{
cout << "用图模拟部分地图，对各省进行着色，要求相邻省所使用的颜色不同，并保证使用的颜色总数最少\n"<< endl;
Graph G;
Createmap(G);
while(answer)
{
color_nums++;//颜色总数+1
Backtrack(G,1);
}
Print();
return 0;
}总结
回溯算法采取的是这条路走不通就返回换下一条路走的思想，我觉得是蛮力法的优化算法，它避免了蛮力法穷举式的搜索。这是一种具有深度优先的策略，也就是如果某一个节点满足约束条件，则继续向下一个节点试探，直到找到解为止。虽然回溯法有限界和剪枝函数减小了搜索范围，但本身是类似于穷举思想，所以时间复杂度仍然很高，但也因此解决问题的范围很广。
文章出处登录后可见！
