[TOC] ## DFS(Depth-First-Search) 深度優先 ### 方式一:前序遍歷 ``` func preorderTraversal(root *TreeNode) []string { result := make([]string, 0) dfs(root, &result) return result } // V1：深度遍歷，結果指針作為參數傳入到函數內部 func dfs(root *TreeNode, result *[]string) { if root == nil { return } *result = append(*result, root.Data) dfs(root.Left, result) dfs(root.Right, result) } // 輸出 // [A B D E C F] ``` ### 方式二: 分治法 ``` // V2：通過分治法遍歷 func preorderTraversal(root *TreeNode) []string { result := divideAndConquer(root) return result } func divideAndConquer(root *TreeNode) []string { result := make([]string, 0) // 返回條件(null & leaf) if root == nil { return result } // 分治(Divide) left := divideAndConquer(root.Left) right := divideAndConquer(root.Right) // 合并結果(Conquer) result = append(result, root.Data) result = append(result, left...) result = append(result, right...) return result } // 輸出 // [A B D E C F] ``` > DFS 深度搜索（從上到下） 和分治法區別：前者一般將最終結果通過指針參數傳入，后者一般遞歸返回結果最后合并 ## 示例 ### 走格子 - 深度優先搜索的步驟分為 1.遞歸下去 2.回溯上來。 - 顧名思義，深度優先，則是以深度為準則，先一條路走到底，直到達到目標。這里稱之為遞歸下去。 - 否則既沒有達到目標又無路可走了，那么則退回到上一步的狀態，走其他路。這便是回溯上來    <details> <summary>main.go</summary> ``` package main import ( "fmt" "os" "os/exec" . "time" ) // 按照右下上左的方向順序走 // 規則: // 1. 能走右邊的走右邊 // 2. 右邊不行的下邊 // 3. 下邊不行的左右邊 // 4. 左邊不行的上(回溯) /** [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 2 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 dfsMap struct { goal_x int goal_y int // //目標的坐標，暫時設置為右下角 graph [n][m]int used [n][m]int px, py [4]int // 通過px 和 py數組來實現左下右上的移動順序 flag bool cout int // 計數 走了多久 } func newDfsMap(goal_x int, goal_y int) *dfsMap { d := dfsMap{ 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]=2 return &d } func (d *dfsMap) Dfs() { d.dfs(0,0) } func (d *dfsMap) dfs(y int ,x int){ Sleep(100* Millisecond) d.clear() fmt.Printf("%s", d) // or if x==d.goal_x && y==d.goal_y { if d.graph[y][x] == d.graph[d.goal_y][d.goal_x] { d.flag = true fmt.Printf("走了 %+v 步\n", d.cout ) return } // 遍歷四個方向 for i := 0; i < 4; i++ { new_x := x + d.px[i] new_y := y + d.py[i] if new_x >= 0 && new_x < n && new_y >= 0 && new_y < m && d.used[new_y][new_x] == 0 && !d.flag { d.used[new_y][new_x] = 1 // //將該格子設為走過 d.cout++ // 記步數 d.dfs(new_y, new_x) // //遞歸下去 d.used[new_y][new_x] = 0 // //狀態回溯，退回來，將格子設置為未走過 } } } func (d *dfsMap) clear() { cmd := exec.Command("clear") cmd.Stdout = os.Stdout cmd.Run() } func (d *dfsMap) String()string{ var res string tmp :=d.used tmp[d.goal_y][d.goal_x]=d.graph[d.goal_y][d.goal_x] for i:=0; i<n; i++ { res+=fmt.Sprintf("%v",tmp[i])+"\n" } return res } func main() { d := newDfsMap(5, 3) d.Dfs() } ``` </details> <br />