BFS(广搜)日有所思，日有所得
1 bfs（广度优先搜索）
含义：广度优先搜索由名字即可看出算法，即将目前结点可到达的结点先全部到达后再进行下一步，在该图中的顺序如下：A B C D E F G。
前提：你得知道链表的写法，动态链表和静态链表（简单来说就是用数组实现）皆可，如不知道可点击以下网址进行学习：http://blog.csdn.net/hackbuteer1/article/details/6591486
模板：用递归实现（以bfs求最短路演示）
1.1 题目：1431: BFS找最短路
时间限制:1 Sec 内存限制:128 MB
提交:126 解决:58
[提交][状态][讨论版]
1.2 题目描述
下图表示的是从城市A到城市H的交通图。从图中可以看出，从城市A到城市H要经过若干个城市。现给给出一个城市的路线图，并给出起点与终点，请给出最短的路线。
1.3 输入
第一行三个数，分别是起点城市，目标城市，线路条数n。
接下来n行，每行两个数字，表示这两个城市之间有线路。
注意：输入数据中1表示城市A，2表示城市B……（你应该知道数据范围了吧？）
1.4 输出
输出路线一行，用->表示箭头，具体格式见样例。
1.5 样例输入
1 8 12
1 2
1 3
1 4
1 6
2 6
3 4
3 5
4 7
5 7
5 8
6 8
7 8
1.6 样例输出
A->F->H
①题解：
首先，题目输入的是数字，输出的却是字母，那么就要学会数字与字母的转换i->A;
方法：i=i+‘A’-1;//将数字i转换成对应的字母。
接着分析，从起点a出发，就样例而言，有b、c、d、f可以到达，目前head=1；
|
A |
|
|
|
|
|
|
|
|
|
Head
因为B、C、D、F都可以回到A并且并不知道哪条路最短，所以我们需要用一个链表来记录可以到达的地方，A出队
|
B |
C |
D |
F |
|
|
|
|
|
|
Head
那么，A出队可以用head++来体现
此时头结点就变成了B,再对B进行同样操作，但是，就会出现以下问题：有两个重复字母
|
B |
C |
D |
F |
F |
|
|
|
|
|
Head
由于F已入队中，不能再入，所以我们需要有一个东西来进行记录：bool rudui[101];
如果已入队，就变成1，其他情况为零，就可以避免上图情况
|
B |
C |
D |
F |
E |
|
|
|
|
|
Head
这样，一直到我们要的终点入队，就可以结束了，从终点倒回去就是我们要的最短路了（自己想想，或者上网查查为什么）
广搜部分代码实现如下：
//jingguo[i]为队列 ,如果a[i][j]为1表示第i个城市和第j个城市之间有路 ,qianqu[i]=j表示第j个城市是从第i个城市过去的
voidbfs()
{
inthead=0,tail=1;//详情参照前面队列
qianqu[1]=0;
jingguo[1]=1;
kexing[1]=0;
while(head<tail)/防止队列为空现象
{
head++; //头结点广搜完毕处理
for(i=qidian;i<=mubiao;i++)//情况罗列
if(kexing[i]==1&&a[jingguo[head]][i]==1)
{
tail++;//入队准备
kexing[i]=0;
jingguo[tail]=i;
qianqu[i]=jingguo[head];//记录前驱，方便输出
if(i==mubiao){
print();//需要写一个输出函数
head=tail;
break; //到终点了！输出最短路
}
}
}
}
希望各位不要复制粘贴
那么，广搜的模板来了：
Void bfs（）
{
付初值head，tail，duilie[1];
While（队列不为空）{
Head++;
For（将状态遍历一遍）{
If（满足情况）{
Tail++；
入队；
记录已入过队}
If（到达终点）{输出 head=tail；break；}
}
}
加油吧，与君共勉，致谢