目录
- 介绍
- 四大特性
- 应用场景
- 实例-迷宫算法
介绍
广度优先搜索算法（英语：Breadth-First-Search，缩写为BFS），又译作宽度优先搜索，或横向优先搜索，是一种图形搜索算法（要求能用图表示出问题的关联性）。简单的说，BFS是从根节点开始，沿着树的宽度遍历树的节点。如果所有节点均被访问，则算法中止。广度优先搜索的实现一般采用open-closed表。BFS是最简便的图的搜索算法之一，这一算法也是很多重要的图的搜索算法的原型。
BFS并不使用经验法则算法，而是类似地毯式搜索，以距离为层数逐层搜索，直到找到答案或确认无解。从算法的观点，所有因为展开节点而得到的子节点都会被加进一个先进先出的队列中。一般的实验里，其邻居节点尚未被检验过的节点会被放置在一个被称为 open 的容器中（例如队列或是链表），而被检验过的节点则被放置在被称为 closed 的容器中。
四大特性
空间复杂度：由于对空间的大量需求，因此BFS并不适合解非常大的问题，对于类似的问题，应用IDDFS(迭代加深算法）已达节省空间的效果。
时间复杂度：最差情形下，BFS必须查找所有到可能节点的所有路径。
完全性：广度优先搜索算法具有完全性。这意指无论图形的种类如何，只要目标存在，则BFS一定会找到。然而，若目标不存在，且图为无限大，则BFS将不收敛（不会结束）。
最佳解：若所有边的长度相等，广度优先搜索算法是最佳解——亦即它找到的第一个解，距离根节点的边数目一定最少；但对一般的图来说，BFS并不一定回传最佳解。这是因为当图形为加权图（亦即各边长度不同）时，BFS仍然回传从根节点开始，经过边数目最少的解；而这个解距离根节点的距离不一定最短。这个问题可以使用考虑各边权值，BFS的改良算法成本一致搜索法来解决。然而，若非加权图形，则所有边的长度相等，BFS就能找到最近的最佳解。
应用场景
- 1.最短路（边权有一定规律的可用BFS，其他就是BFS+松弛，即SPFA）
- 2.次短路（割边+BFS或SPFA）
但这里注意一下，k短路不属于BFS的应用。这类题多用IDDFS或A* - 3.双向BFS
- 4.FloodFill
实例：广度优先 迷宫算法
- box.txt
6 6
0 1 0 0 0 0
0 0 0 1 0 0
0 1 0 1 0 1
1 1 1 0 0 1
0 1 0 0 1 0
0 1 0 0 0 1
注意:
- txt文件，每行结尾需要一个空格，否则读迷宫的代码需要修改**
- 文本第一行是行列数值的说明：6行，6列；第二行起为迷宫地图
- 实现
package main
import (
"fmt"
"os"
)
/**
将数据放到数组里
*/
func readMaze() [][]int {
file, err := os.Open("./box/box.txt")
//Go语言万能错误处理语句
if err !=nil {
panic(err)
}
defer file.Close()
//定义变量 记录 行列
var row,col int
//给定扫描文本 按照指定格式 读出变量 赋值给变量
//第一行代表行数与列数
fmt.Fscanf(file,"%d %d",&row,&col)
//声明 row大小的 []int类型 切片数组
maze := make([][]int,row)
//按索引遍历 切片
for i := range maze{
//声明 col 大小的 int类型 切片数组
maze[i] = make([]int,col)
for j := range maze[i]{
//扫描数组 按照 %d 格式 去数组内容 赋值给 maze切片
fmt.Fscanf(file,"%d",&maze[i][j])
}
}
return maze
}
//定义 用来记录x坐标 和 y 坐标的2个整数
type point struct {
x int
y int
}
//0，0在左上角
//定义了 上下左右操作 的数组
var dirs =[4]point{
//向右走一步
{1,0},
//向下走一步
{0,1},
//向左走一步
{-1,0},
//向上走一步
{0,-1},
}
//节点移动
func (p point) add(r point) point {
return point{p.x + r.x,p.y + r.y}
}
/**
判断节点位置
*/
func (p point) at(grid [][]int) (int,bool) {
//如果判断x坐标已经超出 上边界 或者下边界 则 返回false
if p.x <0 || p.x >= len(grid) {
return 0,false
}
//如果判断y坐标已经超出 上边界 或者下边界 则 返回false
if p.y <0 || p.y >= len(grid[p.x]) {
return 0,false
}
//如果在地图里就返回坐标对应的值,并返回true
return grid[p.x][p.y],true
}
//开始走
func walk(maze [][]int,start,end point) [][]int {
//走过的路点标识-地图
steps := make([][]int,len(maze))
//复制跟迷宫列数一样大小的列数
for i:= range steps{
steps[i] =make([]int,len(maze[i]))
}
//初始化队列 数组 加入起始坐标
Queue := []point{start}
for len(Queue)>0{
//总是从 数组的头取 实现先进先出的队列
cur := Queue[0]
if cur == end {
break
}
//去除取出过的坐标点
Queue = Queue[1:]
//上下左右走 如果走通把那个点加入到队列
for _,dir := range dirs{
next := cur.add(dir)
//计算走后的坐标点
val, ok := next.at(maze)
//判断是否超界 判断是否 是 1 1的话是墙 不能走
if !ok || val ==1 {
continue
}
//如果这个点,已经走过了也去除(steps存在）
val,ok = next.at(steps)
if !ok || val !=0 {
continue
}
if next == start{
continue
}
//出发点的坐标值
curSteps ,_:=cur.at(steps)
//在你的地图上 跟新这个找到的点 索引为上一个点+1
steps[next.x][next.y] = curSteps + 1
//将这个点加入队列
Queue = append(Queue,next)
}
}
return steps
}
func main() {
maze := readMaze()
for _,row := range maze{
for _,val := range row{
fmt.Printf("%d ",val)
}
fmt.Printf("\n")
}
fmt.Printf("\n")
fmt.Printf("\n")
fmt.Printf("\n")
steps := walk(maze,point{0,0},point{len(maze)-1,len(maze[0])-1})
for _,row := range steps{
for _,val := range row{
fmt.Printf("%d ",val)
}
fmt.Printf("\n")
}
}
