广度优先搜索(Breadth-First-Search).doc

宽度优先搜索算法1.概述:宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。之所以称之为宽度优先算法，是因为算法自始至终一直通过已找到和未找到顶点之间的边界向外扩展，就是说，算法首先搜索和s距离为k的所有顶点，然后再去搜索和S距离为k+l的其他顶点。例题hdu 1242/showproblem.php?pid=1242/zhuihunmiling/article/details/8979570（DFS做法）这一此我们介绍广度优先搜索按照惯例，我们还是先说一下该题目的主要易错点1.天使可能有多个朋友，所以不能从朋友的位置开始着天使，只能是从天使找离他最近的朋友2.题目要求的是找到一个用时最少的朋友，而不是步数最少既然是广度优先，那么必然用到队列，但是队列只能是先进先出，即是步数少的先遍历到，显然是不符合题目要求的，那应该怎么办呢？c+给我们提供了标准的函数库，可以引入#include 并定义优先队列类型 priority_queue，并自动对里面的元素进行排序如果排序不符合要求，可以给出小于号 “” 的运算符重载函数，当然在结构体里面进行了，代码里面有具体的实现广度优先搜索依然是简单的 出队-判断-扫描-入队 的四部曲。结构简单，程序也容易实现，现直接给出代码实现cpp view plaincopy1 #include 2 #include 3 #include 4 #include 5 #define N 201 6 using namespace std; 7 8 /优先队列解决,广度优先 9 struct Persion 10 11 int x,y; 12 int time; 13 friend bool operator b.time; / 返回队列中较小的元素； 则返回队列中较大的元素 16 17 18 ; 19 20 int dir42=-1,0,1,0,0,-1,0,1; 21 char mapNN; 22 int visitedNN; 23 int m,n; 24 25 26 int BFS(int x,int y) 27 28 29 30 priority_queue q; 31 Persion current,next; 32 memset(visited,0,sizeof(visited); 33 34 current.x=x; 35 current.y=y; 36 current.time=0; 37 visitedcurrent.xcurrent.y=1; 38 q.push(current); 39 40 41 while(!q.empty() 42 43 44 current=q.top(); 45 q.pop(); 46 for(int i=0;i=0&next.x=0&next.ynm&(m|n) 85 86 87 for(i=0;in;i+) 88 for(j=0;jmapij; 92 if(mapij=a) 93 94 angle.x=i; 95 angle.y=j; 96 97 98 99 100 int time=BFS(angle.x,angle.y); 101 102 103 if(time=-1) 104 coutPoor ANGEL has to stay in the p