[TOC] ### BFS (Breath First Search) 層次遍歷 每一層從左到右訪問每一個節點 層次遍歷較復雜，用到一種名叫**廣度遍歷**的方法，需要使用輔助的先進先出的隊列。 1. 先將樹的根節點放入隊列。 2. 從隊列里面 remove 出節點，先打印節點值，如果該節點有左子樹節點，左子樹入棧，如果有右子樹節點，右子樹入棧。 3. 重復2，直到隊列里面沒有元素。 <details> <summary>main.go</summary> ``` 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)) } ``` </details> <br/> ``` // 層次排序 A B C D E F ``` ## 示例 ### 走格子 - 廣度優先搜索旨在面臨一個路口時，把所有的岔路口都記下來，然后選擇其中一個進入，然后將它的分路情況記錄下來，然后再返回來進入另外一個岔路，并重復這樣的操作 - 在DFS中我們說關鍵點是遞歸以及回溯，在BFS中，關鍵點則是狀態的選取和標記     數字標識步數 <details> <summary>main.go</summary> ``` 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<n; i++ { res+=fmt.Sprintf("%v",tmp[i])+"\n" } return res } func main() { d := newBfsMap(5, 3) d.Bfs() } ``` </details> <br /> 輸出 ``` [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] ```