广搜练习

72 阅读 0 评论 48 点赞

我是靠谱客的博主爱听歌缘分，最近开发中收集的这篇文章主要介绍广搜练习，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目描述：

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

【思路】：经过的城市最少然后。。广搜。。因为一层一层的找嘛，先找到的一定是经过城市最少的

【代码】

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 using namespace std;
 5 bool ccan[9][9]={{0,0,0,0,0,0,0,0,0},
 6
{0,1,0,0,0,1,0,1,1},
 7
{0,0,1,1,1,1,0,1,1},
 8
{0,0,1,1,0,0,1,1,1},
 9
{0,0,1,0,1,1,1,0,1},
10
{0,1,1,0,1,1,1,0,0},
11
{0,0,0,1,1,1,1,1,0},
12
{0,1,1,1,0,0,1,1,0},
13
{0,1,1,1,1,0,0,0,1}};//邻接矩阵 ，0表示可以走，1表示不可以走 
14 int qque[100],pre[100];//队列和前驱结点，用来输出路径 
15 bool visited[10];//是否入队列 
16 int oout(int);//输出路径 
17 void bfs();//广搜 
18 int main()
19 {
20 
dfs();
21
return 0;
22 }
23 void bfs()
24 {
25
int head=0,tail=1;//队列的指针 
26
qque[1]=1;pre[1]=0;visited[1]=1;//记录队列的 第一个元素是1（A），它的前驱是0，它已经访问了 
27
do
28 
{
29
head++;
30
for(int i=1;i<=8;i++)//寻找A,B,C,D,E,F,G,H中能够走的 
31 
{
32
if(!ccan[qque[head]][i]&&!visited[i])//能都走并且没有访问 
33 
{
34
tail++;
35
qque[tail]=i;//入队 
36
visited[i]=1;//打标记 
37
pre[i]=qque[head];//记录前驱 
38
if(i==8)//当搜到H，输出 
39 
{
40 
oout(tail);
41
head=tail;
42
break;
43 
}
44 
}
45 
}
46
}while(head<tail);
47 }
48 int oout(int x)
49 {
50
cout<<char(qque[x]+64);//首先输出H 
51
while(pre[x]!=0)
52 
{
53
x=pre[x];//不要 int x=pre[x]再重新定义是不可以的，那样形参x就不变了orz 
54
cout<<"---"<<char(x+64);
55 
}
56
cout<<endl;
57 }