闪电彬彬

编辑于 2021-06-05 18:42

+ 关注

AK F.*ing leetcode 流浪计划之DFS

字节员工，直播业务长期招人（北京，杭州，上海，深圳），hc巨多，社招，校招，实习都有。

欢迎关注更多精彩
关注我，学习常用算法与数据结构，一题多解，降维打击。

一、简介

广度优先搜索算法BFS（广搜）是图的一种遍历方式，类似于树的层次遍历。

深度优先搜索算法DFS(深搜)是图的一种遍历方式。其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。

由DFS衍生出来的相关应用算法比较多，主要可以分为图应用、回溯法（遍历所有解）、带剪枝的回溯法（求解最优解或判断是否有解）、记忆化搜索（动态规划递归版本实现）。

DFS和BFS也是一种暴力搜索的算法，通常情况下也很完备，对于整体状态的数量要事先估计。对于带剪枝的回溯算法要充分分析剪枝条件的正确性，以免剪掉一些可行解，导致答案不完备。

由于DFS是基于递归的一个过程，学习DFS算法对于理解递归过程非常有帮助，通过练习掌握递归的常规应用。

二、作用

图（树）应用

深度优先遍历结点
判断图中2点是否连通
查找图的连通块

回溯法应用，该算法大多是用于模拟求解。先把问题拆解成某一个基础操作，在每一层做一个基础操作，直到确定唯一解，然后再逐步回溯。

比如：

全排列生成，一开始有n个数字，从第1个位置到n位置，每个位置选择一个数字，直到数字选完产生一个排列，再继续回溯。
走迷宫，每次都选择一个方向走，直到走不动或离开迷宫，就是生成了一条路线，然后再回溯。
对一堆数字生成子集。对每个数字，进集合或者不进集合，当用完所有数字就形成一个子集，再回溯。
八皇后问题，每行选择一个可以放的位置，直到放完所有行，再回溯。

带剪枝的回溯法，该算法一般用于求解某个问题是否有解或问题的最优解。他与回溯法的区别就是递归的终止条件会更多（普通回溯法的终止条件就是元素都操作完了），使得递归次数大大减少。

比如

求解数组（都是非负数）中的某几个数字之和是否等于目标值，基本思想可以生成所有子集，然后判断子集之和是否等于目标值，可以增加终止条件：如果剩下的数字都加上也无法达到目标值就返回。

记忆化搜索求解动态规划问题

动态规划有2种实现方式，递推和递归求解。递推是自底向上，关键要找到这个底在哪里，有些动态规划问题不容易找到底，所以用递归求解更容易实现。递归求解会存在重复求解，需要引入一个map标记是否已求解过，故名记忆化搜索。

三、解题步骤

图遍历应用

解题步骤

定义数据

定义结点数据和孩子数据

具体操作

step 1 选择一个没有遍历过的点

step 2 判断该结点是否已经遍历，是则转6

Step 4 标记当前结点已遍历

step 5 遍历子结点

        1. 判断子结点是否合法
        2. 转step2

step 6 查看是否还有未遍历结点，有则转1，没有转7

step 7 结束

回溯法（剪枝）应用

适用条件：

整体递归层数不能太多，10多个可以接受。
总体状态数量要控制在百万级别，剪枝的话要看情况，可以扩大到千万甚至更高。

解题步骤

定义数据

定义每一层的状态
定义状态转移操作
定义基础结束条件
定义剪枝条件

具体操作

step 1 选择起状态

step 2 判断该状态是否结束，是则返回

Step 3 判断该状态是否剪枝，是则返回（非剪枝可以不要）

step 4 生成和遍历子状态

           1. 判断子状态是否合法
           2. 转step2

step 5 结束

记忆化搜索动态规划应用

适用条件：

所有动态规划问题

解题步骤

定义数据

定义状态
定义结束条件
定义转移方程

具体操作

step 1 选择起状态

step 2 判断该状态是否结束，是则返回结束值

Step 3 判断该状态是否计算过，是则返回

step 4 根据转移方程计算子状态

转到2
标记本状态计算完成，并保存计算结果

step 5 结束

四、代码框架

图遍历框架

// 图遍历框架
vis // 表示 某状态是否被访问过, 针对有环图的情况需要判断，无环图不用
func DFS(start State)  {
    if vis[start] {return}
    vis[start]&lt;-true
    // 对start 进行一些操作
    visit(start)

    // 遍历子结点
    for child &lt;- start.Children {
        DFS(child)
    }
}

回溯法（剪枝）框架

// 回溯法（剪枝）框架
func DFS(dep int, start State) {
     // 判断当前状态的基本条件
     if isEnd(start) {
             // 得到一个结果进行存储
      do sth ...
             return
     }

     // 剪枝条件判断(非剪枝这步可以不要)
     if isCut(start) {return}


     // 进行下一层选择
     for child&lt;-start.Children {
             DFS(dep+1, child)
     }
}

记忆化搜索框架

// 记忆化搜索框架
vis // 存储是否计算过
val // 计算结果值
func dp(start State)  {
     // 判断当前是否结束条件
     if isEnd(start) {return 结果 }

     // 判断是否计算过
     if vis[start] {val[start]}
     vis[start]=true

     // 进行子状态转移
     for child&lt;-start.Children {
         val = dp(child)
         // 对val进行一些操作
     }

     return val[start]
}

Dfs 应用很广，具体每种应该只能大致分成几个部分，没有固定的写法。具体需要做题来感受。

五、牛刀小试

练习1 图深度优先遍历应用省份数量

题目链接 https://leetcode-cn.com/problems/number-of-provinces/

题目大意

有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。

省份是一组直接或间接相连的城市，组内不含其他没有相连的城市。

给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。

返回矩阵中省份的数量。

示例 1：

输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]
输出：2
示例 2：

输入：isConnected = [[1,0,0],[0,1,0],[0,0,1]]
输出：3

提示：

1 <= n <= 200
n == isConnected.length
n == isConnected[i].length
isConnected[i][j] 为 1 或 0
isConnected[i][i] == 1
isConnected[i][j] == isConnected[j

题目解析

题目中给出图是矩阵表示法，先把图转化成链表表示法。

按照题意，一个省就是图中的一个连通块。

可以通过DFS算法去查询一个连通块。

AC代码

func getLinks(isConnected [][]int) [][]int {
    links := make([][]int, len(isConnected))
    for i, row := range isConnected {
        for j, v := range row {
            if i == j { // 排除自己
                continue
            }

            if v == 0 {
                continue
            }
            links[i] = append(links[i], j)
        }
    }
    return links
}

func findCircleNum(isConnected [][]int) int {
    links := getLinks(isConnected)

    sum := 0
    vis := make(map[int]bool)

    var dfs func (int) 
    dfs = func (i int)  {
        if vis[i] { // 已经访问过了，直接返回
            return 
        }
        vis[i]=true

        for _, child :=range links[i] {
            dfs(child)
        }
    }

    for i:=0;i<len(isconnected) ;i++ { if vis[i] 访问过了 continue } 没访问过 sum++ dfs(i) 把与i在同一省的城市都遍历 return sum="=target:" * [[1,1,0],[1,1,0],[0,0,1]] [[1,0,0],[0,1,0],[0,0,1]] [[1]] ~~~ ## 练习2 回溯法应用[全排列](https: leetcode-cn.com problems permutations ) 题目链接：https: ### 题目大意 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。 示例 1： 输入：nums="[1]" 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] 2： 输出：[[0,1],[1,0]] 3： 输出：[[1]] 提示： 1 <="10" -10 中的所有整数 互不相同 题目解析 可以通过回溯法解决。 按照朴素数学做法，以[1,2,3]为例 先选择第1位，1 再从剩下中选择第二位，形成[1，2]， [1，3] 再从剩下中选择第三位，形成[1, 2, 3], [1, 3, 2] 同理第1位选择2，最终产生出 [2，1，3]，[2，3，1] 第1位选择3省略。 根据以上模拟可以发现， 每次操作都是在某一位上选择一个没被用过的数字。 定义： 1. 定义每一层的状态，当前第几位数字待选 2. 定义状态转移操作，待选数字序号加1 3. 定义基础结束条件，所有集合数字已经用完 ac代码 ~~~go func permute(nums []int) [][]int res : vis 标记是否已经被选择 var dfs="func(i" func(int, int, arr []int){ i="=len(nums)" 选完所有数字产生一组排列 temp len(nums)) copy(temp, arr) 尝试第i位填一个数字 for _, v:="range" vis[v]="false" 数字已经被选走了忽略 标记已经被选走 dfs(i+1, append(arr, v)) 释放标记，归还到集合中 dfs(0, nil) 练习3 回溯法+剪枝应用 [组合总和 ii](https: combination-sum-ii 给定一个数组 candidates="[2,5,2,1,2]," 和一个目标数 target="5," ，找出 中所有可以使数字和为 的组合。 中的每个数字在每个组合中只能使用一次。 说明： 所有数字（包括目标数）都是正整数。 解集不能包含重复的组合。 1: 输入: 所求解集为: [ 7], 5], [2, 6], 1, 6] ] 2: [1,2,2], [5] - 对于一个数字来讲就是选取或者不选取，穷举出所有可能依次判断即可 这里要解决的一个问题是相同的数字有可能被多选，举例[1, 1], 子集中会有2个[1] 这种情况是要去重。 注意剪枝 定义每一层的状态，当前层待选择的数字是否要选择 定义基础结束条件，所有选择的数字加="target" 或 所有数字都已经选择完。 4. 剪枝条件：1）所选择数字加和已经大于target, 2) 所选择数字加和加上后面未选择的数字加和小于target 子集去重思路与优化 基本思路 subset(dep, sum, selected, left) res.push(selected) dep>= len(candidates): return // 所有数字选择完
    if sum &gt; target: return // 剪枝条件1
    if sum+left<target: return 剪枝条件2 不选取当前数字 subset(dep+1, sum, selected, left-candidates[dep]) 选取当前数字 selected.push(candidates[dep]) sum+candidates[dep], selected.pop() 优化去重逻辑： 假设 [a,b,c]="[1,1,2]" 选取过程如下： [a], [a，b], [a，b，c], [a,c], [b], [b,c](这里已经重复了), [c] 从上面过程中可以看出，选b的时候前面有一个和b相同的元素还没有被选择过说明这个时候还轮不到b来选。 优化后 先对candidates排序 subuniqueset(dep, left) : if sum="=target:" res.push(selected) dep>= len(candidates): return // 所有数字选择完
    if sum &gt; target: return // 剪枝条件1
    if sum+left<target: return 剪枝条件2 不选取当前数字 subuniqueset(dep+1, sum, selected, left-candidates[dep]) 选取当前数字 判断是否前面有相同数字没有被选择 if dep>0 &amp;&amp; candidates[dep-1]==candidates[dep]: return
    curnum = candidates[dep]
    selected.push(curnum)
    candidates[dep]=-1 //标记被选中了
    subUniqueSet(dep+1, sum+curnum, selected, left-curnum)
    candidates[dep]=curnum //恢复值
    selected.pop()

    return

AC代码

先对candidates排序

func combinationSum2(candidates []int, target int) [][]int {
    sort.Ints(candidates) // 要先排序。
    res := [][]int{}
    left :=0
    for _, v:= range candidates {
        left += v
    }
    // 优化后 先对candidates排序
    var subUniqueSet func(int, int,  int,[]int)
    subUniqueSet = func(dep, sum, left int, selected []int) {
        if sum==target {
            temp := make([]int , len(selected))
            copy(temp, selected)
            res = append(res, temp)
            return // 后面加正数，肯定要大于target 直接返回
        }

        if dep &gt;= len(candidates){ return} // 所有数字选择完
        if sum &gt; target { return}    // 剪枝条件1
        if sum+left<target{ return } 剪枝条件2 不选取当前数字 subuniqueset(dep+1, sum,left-candidates[dep], selected) 选取当前数字 判断是否前面有相同数字没有被选择 if dep>0 &amp;&amp; candidates[dep-1]==candidates[dep] { return }
        curnum := candidates[dep]
        candidates[dep] = -1 //标记被选中了
        subUniqueSet(dep+1, sum+curnum, left-curnum, append(selected, curnum))
        candidates[dep]= curnum //恢复值
    }
    subUniqueSet(0, 0, left, nil)

    return res
}

练习4 记忆化搜索应用矩阵中的最长递增路径

题目链接：https://leetcode-cn.com/problems/longest-increasing-path-in-a-matrix/

题目大意

给定一个 m x n 整数矩阵 matrix ，找出其中最长递增路径的长度。

对于每个单元格，你可以往上，下，左，右四个方向移动。你不能在对角线方向上移动或移动到边界外（即不允许环绕）。

示例 1：

输入：matrix = [[9,9,4],[6,6,8],[2,1,1]]
输出：4
解释：最长递增路径为 [1, 2, 6, 9]。
示例 2：

输入：matrix = [[3,4,5],[3,2,6],[2,2,1]]
输出：4
解释：最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。
示例 3：

输入：matrix = [[1]]
输出：1

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 200
0 <= matrix[i][j] <= 2^31 - 1

题目解析

此题类似于最长上升子序列。使用动态规划解决。

定义：

定义状态，dp[i][j] 表示是以matrix[i][j] 结尾的最长上升路径的长度。
终止条件：matrix[i][j] 四周没有比自己小的数字, 或i, j 越界了 (肯定有数字的四周是大于等自己的，所以最终肯定会停止)
转移方程：dp[i][j] = 1+ max(dp[i-1][j], dp[i+1][j], dp[i][j-1], dp[i][j+1]) (matrix[i][j] >matrix[i-1][j],matrix[i+1][j], matrix[i][j-1], matrix[i][j+1])

AC代码

func max(a, b int) int {
    if a &gt; b {
        return a
    }
    return b
}

var dir = [][]int{
    {0, -1}, {0, 1}, {1, 0}, {-1, 0},
}

func longestIncreasingPath(matrix [][]int) int {
    vis := make(map[int]bool)
    dp := make(map[int]int)
    n, m := len(matrix), len(matrix[0])

    var dfs func(int, int) int
    dfs = func(i, j int) int {
        if i &lt; 0 || i &gt;= n || j &lt; 0 || j &gt;= m { // 越界了，默认0
            return 0
        }
        ind := i*1000 + j // 对矩阵一维化编码
        if vis[ind] {
            return dp[ind]
        } // 已经计算过了，直接返回
        vis[ind] = true //标记已经计算
        dp[ind] = 0
        // 检查4个方法取最大值
        //dp[i][j] = 1+ max(dp[i-1][j], dp[i+1][j], dp[i][j-1], dp[i][j+1])
        for _, d := range dir {
            newX, newY := i+d[0], j+d[1]
            if newX &lt; 0 || newX &gt;= n || newY &lt; 0 || newY &gt;= m { // 越界了
                continue
            }
            if matrix[i][j] &lt;= matrix[newX][newY] { // 不能接在自己后面
                continue
            }
            dp[ind] = max(dp[ind], dfs(newX, newY)) //更新最优值
        }

        // 加上自己
        dp[ind] = dp[ind] + 1

        return dp[ind]
    }

    best := 0
    // 检查 每个dp(i,j) 取最大值
    for i, row := range matrix {
        for j := range row {
            //fmt.Printf("%d, ", dfs(i, j))
            best = max(best, dfs(i, j))
        }
        //fmt.Println()
    }

    return best
}

六、总结

主要内容：

深搜算法是一种暴力算法，适用于状态全集规模较小搜索问题。
作用：图应用主要有1）深度优先遍历结点，2）图连通块相关的一些计算，比如判2点是否连通，有几个连通块。

回溯法（剪枝），记忆化搜索也是深搜算法的应用。
解题的基本框架比较固定，关键在于状态的定义，以及状态转移方法的构造。

笔者水平有限，有写得不对或者解释不清楚的地方还望大家指出，我会尽自己最大努力去完善。

下面我精心准备了几个流行网站上的题目（首先AK F.*ing leetcode），给大家准备了一些题目，供大家练习参考。干他F.*ing (Fighting?)。

七、实战训练

代码基础训练题

光说不练假把式，学完了怎么也要实操一下吧，快快动用把刚才那例题A了。

图深度优先遍历应用题目链接 https://leetcode-cn.com/problems/number-of-provinces/
回溯法应用题目链接 https://leetcode-cn.com/problems/permutations/
回溯法+剪枝应用题目链接 https://leetcode-cn.com/problems/combination-sum-ii/
记忆化搜索应用题目链接 https://leetcode-cn.com/problems/longest-increasing-path-in-a-matrix/

AK leetcode

leetcode相关题目都在下面了，拿起武器挨个点名呗。

https://leetcode-cn.com/tag/depth-first-search/problemset/ 深度优先遍历

https://leetcode-cn.com/tag/backtracking/problemset/ 回溯（剪枝）算法

https://leetcode-cn.com/tag/memoization/problemset/ 记忆化搜索

以上题目太多，大家适当选择就行，下面还有进阶题目。

大神进阶

hdu

poj

本人码农，希望通过自己的分享，让大家更容易学懂计算机知识。
</target{></len(isconnected)>

2025最新求职资料大礼包领取

大家都在关注

校招日程表笔试日历 ai模拟面试面试宝典剑指offer 知识点专项练习

已采纳

采纳

精彩回帖

精彩

全部评论

(0) 回帖

加载中...

话题同步到我的动态回帖

AK F.*ing leetcode 流浪计划之DFS

一、简介

二、作用

三、解题步骤

图遍历应用

回溯法（剪枝）应用

记忆化搜索动态规划应用

四、代码框架

图遍历框架

回溯法（剪枝）框架

记忆化搜索框架

五、牛刀小试

练习1 图深度优先遍历应用省份数量

题目大意

题目解析

AC代码

AC代码

练习4 记忆化搜索应用矩阵中的最长递增路径

题目大意

题目解析

AC代码

六、总结

七、实战训练

代码基础训练题

AK leetcode

大神进阶

已采纳

精彩回帖

全部评论

近期热帖

近期精华帖

热门推荐

AK F.*ing leetcode 流浪计划之DFS

一、简介

二、作用

三、解题步骤

图遍历应用

回溯法（剪枝）应用

记忆化搜索动态规划应用

四、代码框架

图遍历框架

回溯法（剪枝）框架

记忆化搜索框架

五、牛刀小试

练习1 图深度优先遍历应用 省份数量

题目大意

题目解析

AC代码

AC代码

练习4 记忆化搜索应用 矩阵中的最长递增路径

题目大意

题目解析

AC代码

六、总结

七、实战训练

代码基础训练题

AK leetcode

大神进阶

已采纳

精彩回帖

全部评论

相关热帖

近期热帖

近期精华帖

热门推荐

练习1 图深度优先遍历应用省份数量

练习4 记忆化搜索应用矩阵中的最长递增路径