深度優(yōu)先搜索

1、簡介
DFS（Depth-First-Search）：深度優(yōu)先搜索。從一個(gè)初始結(jié)點(diǎn)開始，沿著一條路一直走到底，如果不是目標(biāo)解，就返回到上一個(gè)結(jié)點(diǎn)，從另一條路開始走到底，使用了回溯的思想。

2、應(yīng)用
（1）二叉樹的層序遍歷
下面是 Go 語言版的完整代碼，可運(yùn)行：

package main

import (
"fmt"
"container/list"
)

type TreeNode struct {
    Val int
    Left *TreeNode
    Right *TreeNode
}

func dfs(node *TreeNode, result *[][]int, level int) {
    if len(*result) < level + 1 {
        *result = append(*result, []int{} )
    }
    (*result)[level] = append( (*result)[level], node.Val )

    if nil != node.Left{
        dfs(node.Left, result, level+1)
    }
    if nil != node.Right{
        dfs(node.Right, result, level+1)
    }
}

func levelOrderDFS(root *TreeNode) [][]int {
    if nil == root{
        return [][]int{}
    }
    result := [][]int{}
    dfs(root, &result, 0)
    return result
}

func createBST( v []int ) *TreeNode {
    n := len(v)
    if n == 0{
        return nil
    }else if n == 1{
        return & TreeNode{ v[0], nil, nil}
    }

    m := n/2
    root := & TreeNode{ v[m], nil, nil}
    root.Left = createBST( v[0:m] )
    root.Right = createBST( v[m+1:] )
    return root
}

func main() {
    tree := createBST( []int {1,2,3,4,5,6,7} )
    fmt.Println(levelOrderDFS(tree))
}

（2）二叉樹的最大深度
某個(gè)結(jié)點(diǎn)的最大深度，可以先求出左子樹的最大深度和右子樹的最大深度中較大的那一個(gè)，再加上 1 即可。遞歸的結(jié)束條件是遇到空結(jié)點(diǎn)，返回 0 。

func maxDepthDFS(root *TreeNode) int {
    if root == nil{
        return 0
    }
    max := maxDepthDFS(root.Left)
    right := maxDepthDFS(root.Right)
    if right > max{
        max = right
    }
    return 1 + max
}

（3）二叉樹的最小深度：

func minDepthDFS(root *TreeNode) int {
    if root == nil{
        return 0
    }
    min := minDepthDFS(root.Left)
    right := minDepthDFS(root.Right)
    if right < min{
        min = right
    }
    return 1 + min
}

（4）解數(shù)獨(dú)
(A) 判斷數(shù)獨(dú)是否有效，暴力破解
一個(gè)簡單的解決方案是 遍歷該 9 x 9 數(shù)獨(dú)，以確保：
行中沒有重復(fù)的數(shù)字，
列中沒有重復(fù)的數(shù)字，
3 x 3 子數(shù)獨(dú)內(nèi)沒有重復(fù)的數(shù)字。
完整代碼如下，外圍 2 層循環(huán)，加上 isLegal 函數(shù)內(nèi)的 1 層循環(huán)，時(shí)間復(fù)雜度是 O(n3)

package main
import "fmt"

func isValid(board *[][]byte, row int, col int) bool {
    for i:=0 ; i < 9; i++ {
        if (*board)[i][col] == (*board)[row][col] && i != row {
            return false
        }
        if (*board)[row][i] == (*board)[row][col] && i != col {
            return false
        }
        r := row / 3 * 3 + i / 3
        c := col / 3 * 3 + i % 3
        if (*board)[r][c] == (*board)[row][col] && r != row && c != row {
            return false
        }
    }
    return true
}

func isValidSudoku(board [][]byte) bool {
    for i:=0 ; i < 9; i++ {
        for j:=0 ; j < 9; j++ {
            if board[i][j] == '.' || isValid(&board, i , j) {
                continue
            }
            return false
        }
    }
    return true
}

func main() {
    input := [][]byte{
        {'5','3','.','.','7','.','.','.','.'},
        {'6','.','.','1','9','5','.','.','.'},
        {'.','9','8','.','.','.','.','6','.'},
        {'8','.','.','.','6','.','.','.','3'},
        {'4','.','.','8','.','3','.','.','1'},
        {'7','.','.','.','2','.','.','.','6'},
        {'.','6','.','.','.','.','2','8','.'},
        {'.','.','.','4','1','9','.','.','5'},
        {'.','.','.','.','8','.','.','7','9'} }
    fmt.Println(isValidSudoku(input))
}

(B) 判斷數(shù)獨(dú)是否有效--空間換時(shí)間
先用數(shù)組或哈希表把狀態(tài)保存起來，這樣在判重的時(shí)候時(shí)間復(fù)雜度是 O(1)，總的時(shí)間復(fù)雜度是 O(n2) ：

func isValidSudoku(board [][]byte) bool {
    x := [9][9]bool{}
    y := [9][9]bool{}
    box := [3][3][9]bool{}
    
    for i:=0 ; i < 9; i++ {
        for j:=0 ; j < 9; j++ {
            if board[i][j] == '.' {
                continue
            }
            bx := i/3
            by := j/3
            n := board[i][j] - '1'

            if true == x[i][n] || true == y[j][n] || true == box[bx][by][n] {
                return false
            }
            x[i][n] = true
            y[j][n] = true
            box[bx][by][n] = true
        }
    }
    return true
}

(C) 解數(shù)獨(dú)
先用數(shù)組或哈希表把狀態(tài)保存起來，遍歷每個(gè)空格，for 循環(huán)遍歷 9 個(gè)數(shù)字，調(diào)用 couldPlace() 方法來判斷，如果某個(gè)格子可以放該數(shù)字，就調(diào)用 placeNumber() 方法來更新狀態(tài) ，調(diào)用 placeNextNumbers() 方法繼續(xù)下一個(gè)格子，如果這條路走不通，就再調(diào)用 removeNumber() 方法清除剛才的狀態(tài)。直到找出解。

package main
import "fmt"

const (
    n = 3
    N = n*n
)

type Sudoku struct {
    rows [N][N]bool
    columns [N][N]bool
    boxes [N][N]bool
    success bool
    pBoard *[][]byte
}

func (this *Sudoku) couldPlace(d int, row int, col int) bool {
    idx := (row / n ) * n + col / n;
    return !( this.rows[row][d] || this.columns[col][d] || this.boxes[idx][d] )
}

func (this *Sudoku) placeNumber(d int, row int, col int) {
    idx := (row / n ) * n + col / n
    this.rows[row][d] = true
    this.columns[col][d] = true
    this.boxes[idx][d] = true
    (*this.pBoard)[row][col] = byte(d + '1')
}

func (this *Sudoku) removeNumber(d int, row int, col int) {
    idx := (row / n ) * n + col / n
    this.rows[row][d] = false
    this.columns[col][d] = false
    this.boxes[idx][d] = false
    (*this.pBoard)[row][col] = '.'
}

func (this *Sudoku) placeNextNumbers(row int, col int) {
    if col == N-1 && row == N-1 {
        this.success = true
    } else {
        if col == N-1 {
            this.dfs(row + 1, 0)
        } else {
            this.dfs(row , col + 1)
        }
    }
}

func (this *Sudoku) dfs(row int, col int) {
    if (*this.pBoard)[row][col] == '.' {
        for i := 0; i < N; i++ {
            if true == this.couldPlace(i, row, col) {
                this.placeNumber(i, row, col)
                this.placeNextNumbers(row, col)

                if false == this.success {
                    this.removeNumber(i, row, col)
                }     
            }
        }
    } else {
        this.placeNextNumbers(row, col)
    }
}

func (this *Sudoku) init_array() {
    for i := 0; i < N; i++ {
        for j := 0; j < N; j++ {
            num := (*this.pBoard)[i][j]
            if num != '.' {
                d := num - '1'
                this.placeNumber( int(d), i, j)
            }
        }
    }
}

func solveSudoku(board [][]byte) {
    p := Sudoku{pBoard: &board}
    p.init_array()
    p.dfs(0, 0)
}

func printSudoku(board [][]byte) {
    fmt.Println()
    for i := 0; i < N; i++ {
        for j := 0; j < N; j++ {
            fmt.Printf( "%c  ", board[i][j])
        }
        fmt.Println()
    }
    fmt.Println()
}

func main() {
    input := [][]byte{
        {'5','3','.','.','7','.','.','.','.'},
        {'6','.','.','1','9','5','.','.','.'},
        {'.','9','8','.','.','.','.','6','.'},
        {'8','.','.','.','6','.','.','.','3'},
        {'4','.','.','8','.','3','.','.','1'},
        {'7','.','.','.','2','.','.','.','6'},
        {'.','6','.','.','.','.','2','8','.'},
        {'.','.','.','4','1','9','.','.','5'},
        {'.','.','.','.','8','.','.','7','9'} }
    printSudoku(input)
    solveSudoku(input)
    printSudoku(input)
}
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

友情鏈接更多精彩內(nèi)容