《信息学奥赛一本通》 广度优先搜索算法 【例8.1】图8-2表示的是从城市A到城市H的交通图。 书本代码详解

【例8.1】图8-2表示的是从城市A到城市H的交通图。
从图中可以看出，从城市A到城市H要经过若干个城市。
现要找出一条经过城市最少的一条路线。

#include<bits/stdc++.h>
using namespace std;
int ju[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],b[101];
bool s[9];
//初始化
int out(int d)
//输出过程
{
cout<<char(a[d]+64);
//由城市编号转为字母
while (b[d])
//==while(b[d]==0)
{
d=b[d];
//得到上个城市
cout<<"--"<<char(a[d]+64);
}
cout<<endl;
}
void doit()
{
int head,tail,i;
head=0;
//第0组探寻
tail=1;
//第一次探寻
a[1]=1;
//城市A为第一次探索城市
b[1]=0;
//记录从哪个城市到达该市可在A前放个城市0
s[1]=1;
//表示该城市已经到过
do
{
head++;
//若一组探寻无法到达H市，则开始下一组探寻
for (i=1;i<=8;i++)
//搜索可直通的城市
if ((ju[a[head]][i]==0)&&(s[i]==0))
//判断城市是否走过，若有其他城市也可到该市，
//经过城市次数一定大于等于当前情况，无需考虑
{
tail++;
//若能找到则探索次数+1
a[tail]=i;
//a[]数值即为第几次探索城市编号
b[tail]=head;
//从哪个城市来，如现在b[tail]来自城市编号为a[head]
s[i]=1;
//禁用该城
if (i==8)
//若i==8则已到H城
{
out(tail);
head=tail;
//break只退出了do循环，head=tail退出while循环，可减少运行次数
break;
//第一次搜到H城市时路线最短
}
}
}
while (head<tail);
}
int main()
//主程序
{
memset(s,false,sizeof(s));
doit();
//进行Bfs操作
return 0;
}

最后

以上就是专一路人为你收集整理的《信息学奥赛一本通》 广度优先搜索算法 【例8.1】图8-2表示的是从城市A到城市H的交通图。 书本代码详解的全部内容，希望文章能够帮你解决《信息学奥赛一本通》 广度优先搜索算法 【例8.1】图8-2表示的是从城市A到城市H的交通图。 书本代码详解所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。