BFS(广搜)算法与模板 bfs求最短路

时间:2022-05-31 09:52:28


BFS(广搜)日有所思,日有所得

1    bfs(广度优先搜索)

BFS(广搜)算法与模板 bfs求最短路BFS(广搜)算法与模板 bfs求最短路

  1. 含义:广度优先搜索由名字即可看出算法,即将目前结点可到达的结点先全部到达后再进行下一步,在该图中的顺序如下:A B C D E F G

  2. 前提:你得知道链表的写法,动态链表和静态链表(简单来说就是用数组实现)皆可,如不知道可点击以下网址进行学习:http://blog.csdn.net/hackbuteer1/article/details/6591486

  3. 模板:用递归实现(以bfs求最短路演示)

1.1    题目:1431: BFS找最短路

时间限制:1 Sec  内存限制:128 MB
提交:126  解决:58
[提交][状态][讨论版]

1.2   题目描述

下图表示的是从城市A到城市H的交通图。从图中可以看出,从城市A到城市H要经过若干个城市。现给给出一个城市的路线图,并给出起点与终点,请给出最短的路线。

BFS(广搜)算法与模板 bfs求最短路

1.3    输入

第一行三个数,分别是起点城市,目标城市,线路条数n

接下来n行,每行两个数字,表示这两个城市之间有线路。

注意:输入数据中1表示城市A2表示城市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出发,就样例而言,有bcdf可以到达,目前head=1

A

 

 

 

 

 

 

 

 

 

Head

因为BCDF都可以回到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()

{

  付初值headtailduilie[1];

While(队列不为空){

Head++;

For(将状态遍历一遍){

If(满足情况){

               Tail++

入队;

记录已入过队}

     If(到达终点){输出  head=tailbreak}

}

}

加油吧,与君共勉,致谢