練習2.
/*最短路徑問題：從A城市出發到大目標城市求最短的路線：
解題思路：首先使用陣列a記錄途徑城市，用陣列b記錄所經過的城市，陣列c記錄哪些城市走過哪些沒走過
每當a記錄一次所經的城市時，陣列b都會將該城市的前驅城市記錄下來...當找到目標城市時，最短路線就已經
儲存在b陣列中了，逆序輸出一下b陣列就是我們所要的答案， */
#include<bits/stdc++.h>
using namespace std;
//使用鄰接矩陣來表示城市，只有8個城市所以需要開辟8*8的二維陣列，在這里不使用第0行和第0列所以開9*9的
int city[9][9]={{0,0,0,0,0,0,0,0,0},
{0,1,0,0,0,1,0,1,1},
{0,0,1,1,1,1,0,1,1},
{0,0,1,1,0,0,1,1,1},
{0,0,1,0,1,1,1,0,1},
{0,1,1,0,1,1,1,0,0},
{0,0,0,1,1,1,1,1,0},
{0,1,1,1,0,0,1,1,0},
{0,1,1,1,1,0,0,0,1}};
int a[101];//記錄途徑城市
int b[101];//記錄途徑城市的前驅城市
int c[9];//標記哪些城市走過了避免重復走
//輸出函式out，用來逆序輸出b城市中保存的前驅城市
void out(int d)//傳進來儲存前驅城市的b陣列的下標，該下標對應著前驅城市的下標將它在a陣列里輸出即可
{
cout<<char(a[d]+64 );//a[8]=8,8+64==72 ->'H';
while(b[d]!=0)//b陣列里面記錄著每個前驅城市，第一個是A的前驅城市0，所以當b陣列中的元素為0時說明b陣列已經逆序輸出完畢
{
d = b[d]; //注意該陳述句就是該回圈的回圈變數自減，
cout<<"--"<<char(a[d]+64);
}
}
//撰寫寬搜函式
void bfs()
{
//初始化
int head=0,tail=1; //定義隊頭，隊尾
a[1]=1;//將起始城市入隊
b[1]=0;//A城沒有前驅城市所以是0
c[1]=1;//A城走過了
do
{
head++;//隊頭++搜索新的城市
for(int i=1;i<=8;i++)//按照遍歷規則能夠遍歷的方法數目：A->A,A->B,A->c,A->d,A->E,A->F,A->H; (搜索每一層,搜索每一個城市)
{
if(city[head][i]==0&&c[i]==0)//如果該城市能走(能直通且沒走過)就將它入隊，
{
tail++;//隊尾加1,將新的城市入隊
a[tail]=i;//入隊
b[tail]=head;//記錄每個城市的前驅城市（B，C，D，F的前驅城市就是A鄰接矩陣中用1表示A,所以將1入隊）
c[i]=1;//標記每一個走過的城市
if(i==8)//如果入隊的是第8個城市H，說明我們找到的目標城市，此時只需要逆序輸出儲存在b城市中的城市即可得到最短路線：H--F--A
{
out(tail);//逆序輸出b城市中保存的前驅城市
break;
}
}
}
}while(head<tail);//當遍歷完全部結點時停止搜索
}
int main()
{
bfs();
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/241929.html
標籤：其他
上一篇：Unity_關于我寫爆裂魔法那些事(氛圍渲染流彩描邊星星與其發射系統的實作)
下一篇：找到搜索二叉樹中兩個錯誤的節點