目錄
前言
一、解決問題的思路
二、存儲結(jié)構(gòu)設計
三、代碼
1.創(chuàng)建圖函數(shù)
2.判斷色號是否相同函數(shù)
3.回溯函數(shù)
4.整體代碼
總結(jié)
前言
本次解決的問題：用圖模擬部分地圖，對各省進行著色，要求相鄰省所使用的顏色不同，并保證使用的顏色總數(shù)最少。
先來一張效果圖
一、解決問題的思路
將鄰接矩陣創(chuàng)建好了以后，通過回溯函數(shù)，在解空間樹中搜索所有的可行解，如果著色有沖突，就回溯到上一個節(jié)點。一旦到達葉子節(jié)點，也就是這個解到頭了，就輸出這種著色方案。
二、存儲結(jié)構(gòu)設計
a）
抽象數(shù)據(jù)類型：
????????ADT Graph{
????????數(shù)據(jù)對象V：一個非空集合，該集合中的所有元素具有相同的特性。
????????數(shù)據(jù)關系R：R={VR}，VR={<x,y> | P(x,y) ∧(x,y∈V)}
基本操作：
????????Createmap(&G)
????????操作前提:已知圖G不存在。
????????操作結(jié)果:創(chuàng)建圖G。
????????}ADT Graph;
(b) 存儲結(jié)構(gòu)：順序表存儲結(jié)構(gòu)
????????typedef struct{
?? ????????char vertax[MAX][MAX];//頂點所屬的省份
?? ????????int map[MAX][MAX]; //鄰接矩陣
?????????? int n; //頂點個數(shù)
?????????? int m;//邊的個數(shù)
????????}Graph;
三、代碼
1.創(chuàng)建圖函數(shù)
這里沒什么好說的，都是創(chuàng)建圖所需要的輸入。頂點個數(shù)，頂點所代表的省份也就是頂點名稱，邊的個數(shù)，有邊相連的兩個頂點。
void Createmap(Graph &G) //創(chuàng)建鄰接矩陣
{
printf("請輸入頂點(省份)個數(shù)：");
int f=scanf("%d", &G.n);
while(f!=1)
{
printf("輸入值非法！\n");
printf("請重新輸入頂點(省份)個數(shù)：");
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請輸入邊的個數(shù)：";
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.判斷色號是否相同函數(shù)
先判斷是否相連，如果相連則判斷兩個頂點顏色是否一樣。如果頂點顏色不沖突，就返回真，反之返回假。
bool Find(Graph G,int t) //判斷色號是否相同的函數(shù)
{
for(int j=1;j<t;j++) //判斷現(xiàn)在擴展點t和前面t-1個頂點有沒有相連的
{
if(G.map[t][j]) //如果相連
{
if(color[j]==color[t]) //且顏色一樣
{
return false; //返回false，表示需要換個色號嘗試
}
}
}
return true;
}3.回溯函數(shù)
判斷是否到達了葉子節(jié)點，如果沒有，則開始試探這個頂點著此顏色行不行，行就向下遞歸，進入下一個節(jié)點開始著色試探，不行就換一種顏色繼續(xù)試探，直到所有顏色被試探完。文章來源：http://www.zghlxwxcb.cn/news/detail-766812.html
void Backtrack(Graph G,int t) //回溯函數(shù)
{
if(t>G.n) //到達葉子節(jié)點，打印一種填色方案
{
answer=0;//找到最少的顏色個數(shù)
sum++; //方案個數(shù)+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;//最大存儲個數(shù)
typedef struct{
char vertax[MAX][MAX];//頂點所屬的省份
int map[MAX][MAX]; //鄰接矩陣
int n; //頂點個數(shù)
int m;//邊的個數(shù)
}Graph;
int color[MAX]; //解空間，表示第i個省所填的顏色
int sum=0; //記錄有多少種方案
int color_nums=0; //顏色數(shù)量
int answer=1;
void Createmap(Graph &G) //創(chuàng)建鄰接矩陣
{
printf("請輸入頂點(省份)個數(shù)：");
int f=scanf("%d", &G.n);
while(f!=1)
{
printf("輸入值非法！\n");
printf("請重新輸入頂點(省份)個數(shù)：");
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請輸入邊的個數(shù)：";
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) //判斷色號是否相同的函數(shù)
{
for(int j=1;j<t;j++) //判斷現(xiàn)在擴展點t和前面t-1個頂點有沒有相連的
{
if(G.map[t][j]) //如果相連
{
if(color[j]==color[t]) //且顏色一樣
{
return false; //返回false，表示需要換個色號嘗試
}
}
}
return true;
}
void Backtrack(Graph G,int t) //回溯函數(shù)
{
if(t>G.n) //到達葉子節(jié)點，打印一種填色方案
{
answer=0;//找到最少的顏色個數(shù)
sum++; //方案個數(shù)+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 << "用圖模擬部分地圖，對各省進行著色，要求相鄰省所使用的顏色不同，并保證使用的顏色總數(shù)最少\n"<< endl;
Graph G;
Createmap(G);
while(answer)
{
color_nums++;//顏色總數(shù)+1
Backtrack(G,1);
}
Print();
return 0;
}總結(jié)
回溯算法采取的是這條路走不通就返回換下一條路走的思想，我覺得是蠻力法的優(yōu)化算法，它避免了蠻力法窮舉式的搜索。這是一種具有深度優(yōu)先的策略，也就是如果某一個節(jié)點滿足約束條件，則繼續(xù)向下一個節(jié)點試探，直到找到解為止。雖然回溯法有限界和剪枝函數(shù)減小了搜索范圍，但本身是類似于窮舉思想，所以時間復雜度仍然很高，但也因此解決問題的范圍很廣。文章來源地址http://www.zghlxwxcb.cn/news/detail-766812.html
到了這里，關于數(shù)據(jù)結(jié)構(gòu)：地圖著色問題——圖的應用——回溯法的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
