BFS 广度优先

[TOC] ### BFS (Breath First Search) 层次遍历 每一层从左到右访问每一个节点 层次遍历较复杂，用到一种名叫**广度遍历**的方法，需要使用辅助的先进先出的队列。 1. 先将树的根节点放入队列。 2. 从队列里面 remove 出节点，先打印节点值，如果该节点有左子树节点，左子树入栈，如果有右子树节点，右子树入栈。 3. 重复2，直到队列里面没有元素。

main.go

``` package main import "fmt" // 二叉树 type TreeNode struct { Data string // 节点用来存放数据 Left *TreeNode // 左子树 Right *TreeNode // 右字树 } func levelOrder(root *TreeNode) [][]string { var ret [][]string if root == nil { return nil } q := []*TreeNode{root} // 层数 var level int for len(q) > 0 { // 设置下一层的值 ret = append(ret, []string{}) //缓存下一层节点 var p []*TreeNode // 获取这一层个数 for _, node := range q { ret[level] = append(ret[level], node.Data) if node.Left != nil { p = append(p, node.Left) } if node.Right != nil { p = append(p, node.Right) } } level++ q = p } return ret } func main() { t := &TreeNode{Data: "A"} t.Left = &TreeNode{Data: "B"} t.Right = &TreeNode{Data: "C"} t.Left.Left = &TreeNode{Data: "D"} t.Left.Right = &TreeNode{Data: "E"} t.Right.Left = &TreeNode{Data: "F"} fmt.Printf("%+v\n", levelOrder(t)) } ```

``` // 层次排序 A B C D E F ``` ## 示例 ### 走格子 - 广度优先搜索旨在面临一个路口时，把所有的岔路口都记下来，然后选择其中一个进入，然后将它的分路情况记录下来，然后再返回来进入另外一个岔路，并重复这样的操作 - 在DFS中我们说关键点是递归以及回溯，在BFS中，关键点则是状态的选取和标记     数字标识步数

main.go

``` package main import ( "fmt" "os" "os/exec" "time" ) // 按照右下上左的方向顺序走 // 规则: // 1. 能走右边的走右边 // 2. 右边不行的下边 // 3. 下边不行的左右边 // 4. 左边不行的上(回溯) /** [0 1 2 3 0 0 0 0 0 0] [1 2 3 0 0 0 0 0 0 0] [2 3 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0] [0 0 0 -1 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0] */ const ( n = 10 // 长=y m = 10 // 宽=x ) type point struct { x int y int } type bfsMap struct { goal_x int goal_y int // //目标的坐标，暂时设置为右下角 graph [n][m]int used [n][m]int px, py [4]int // 通过px 和 py数组来实现左下右上的移动顺序 } func newBfsMap(goal_x int, goal_y int) *bfsMap { d := bfsMap{ goal_x: goal_x, goal_y: goal_y, // 右下上左 // px+py 可指定四个方向 // x 加方向为右 // y 加方向为下 px: [4]int{1, 0, 0, -1}, py: [4]int{0, 1, -1, 0}, // 下上右下 //px: [4]int{0, 0, 1, -1}, //py: [4]int{1, -1, 0, 0}, } d.graph[goal_y][goal_x]=-1 return &d } func (b *bfsMap) Bfs(){ queue :=make([]point,0) queue = append(queue, point{0,0}) b.used[0][0]=1 for len(queue)!=0 { l :=len(queue) next_point :=queue[0] if l >= 1 { queue=queue[1:] }else{ queue=queue[:0] } for i:=0; i<4; i++ { new_x := next_point.x + b.px[i] new_y := next_point.y + b.py[i] if new_x >= 0 && new_x < n && new_y >= 0 && new_y < m && b.used[new_y][new_x] == 0 { b.used[new_y][new_x] = new_y+new_x+1 //将该格子设为走过 queue = append(queue, point{new_x,new_y}) time.Sleep(100* time.Millisecond) b.clear() fmt.Printf("%s", b) } } } } func (b *bfsMap) clear() { cmd := exec.Command("clear") cmd.Stdout = os.Stdout cmd.Run() } func (b *bfsMap) String()string{ var res string tmp := b.used tmp[b.goal_y][b.goal_x]= b.graph[b.goal_y][b.goal_x] for i:=0; i
输出 ``` [1 2 3 4 5 6 7 8 0 0] [2 3 4 5 6 7 8 0 0 0] [3 4 5 6 7 0 0 0 0 0] [4 5 6 7 0 -1 0 0 0 0] [5 6 7 0 0 0 0 0 0 0] [6 7 0 0 0 0 0 0 0 0] [7 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0] ```