广度优先搜索
概念
广度优先搜索(Bread First Search: BFS)对源节点的子结点都进行遍历后,才会遍历子结点的子结点。BFS是很多重要的图算法的原型,比如Prim最小生成树算法和Dijkstra单源最短路径算法。
LeetCode之广度优先搜索
505.The Maze II
设定与迷宫I一致,0表示空格,1表示障碍物,四周为墙;球一旦滚动则一直到遇到墙为止。求到达终点的最短距离。
由于这道题需要计算起点到终点最短路径,Dijkstra单源最短路径算法可解。用优先队列来存储每次要遍历的结点。
1 | var PriorityQueue = require('./PriorityQueue'); |
499.The Maze III
这次迷宫中有一个洞,如果球滚到洞里就停止,其余与The Maze I一致,求到洞的最短距离中的最小(词典序)路径。
其实与The Maze II解法相同,只不过在点的类型中加入路径属性作为比较的附属
1 | var PriorityQueue = require('./PriorityQueue'); |
317.Shortest Distance from All Buildings
二维地图中,1表示建筑物,2表示障碍物,0表示空地。返回距离地图中所有建筑物最近的距离和。
Input:
1 - 0 - 2 - 0 - 1
| | | | |
0 - 0 - 0 - 0 - 0
| | | | |
0 - 0 - 1 - 0 - 0
Output: 7
对于每个建筑物,用BFS来搜索到每个点的最短距离;对每次求出的距离求和,最后对所有的总距离求最小值。
1 | //BFS: from every building and add the shortest distance |