闪电彬彬

2021-05-22 21:13 字节跳动_直播server_高级开发工程师

关注

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

字节员工，直播业务长期招人（北京，杭州，上海，深圳），hc巨多，社招，校招，实习都有。
欢迎关注更多精彩
关注我，学习常用算法与数据结构，一题多解，降维打击。

一、简介

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

图应用主要有1）无权图中2点最短路计算，2）图或树的层次遍历，3）图连通块相关的一些计算，比如判2点是否连通，有几个连通块。

广搜同样适用于隐式图中。隐式图概念

对于隐式图中状态可达性，以及2个状态之间转移的代价的计算也可以通过广搜来解决。

该算法原理是从初始状态出发层次遍历隐式图中所有结点，所有遍历到的结点既为可达状态结点（所处层次即为转移代价）。

比如，在二维矩阵迷宫中从某个格子到达出口的步数查找（如果可以走出来）就是隐式图广搜的一种应用。

由于广搜是遍历所有图中结点，所以该算法是一种暴力算法。BFS算法往往就会有固定的代码框架和解题套路。

广搜算法的核心是预估状态（图中的结点）的数量，以及转移条件（从某一状态到另状态的方法）。

如果状态数量太多，其实是不适用广搜的。反之，如果状态数量在一定可控范围，那么广搜暴力算法将是非常好的选择。

转移条件就是如何从一个结点到另一个结点。对普通图来说就是边的关系，对于隐式图来说就是状态转移规则（一般都是模拟操作），比如在上述的迷宫中，那么一个人的状态就是当前处在哪个点（x, y），转移就是向4个方向走。dir = [][]{{1,0},{-1,0},{0,1},{0,-1}}，转移状态就是(x+dir[i][0], y+dir[i][1])

遍历图的复杂度是O(v+e), 结点数加边的数量。

广搜在算法题中非常实用，由于是遍历所有状态，对答案的探索非常的完备（很有安全感），一旦分析出状态量是可控的，那就是直接上。是我个人在解题中优先考虑的算法之一。

二、条件及解题步骤

条件：

图或是可定义出状态的隐式图
可达状态数量在百万级别以内
有明确的状态转移方法

解题步骤

定义数据

定义状态表示
定义状态转移方法
定义边界判断方法

具体操作

step 1 初始化，将初始化结点加入到队列q中，表示第一层

step 2 判断队列是否为空，是则转 step5

step3 遍历当前层结点

1. 产生新状态，

2. 判断新状态是否合法（是否跃界，是否可达）

3. 判断新状态是否已经加入到队列中。

4. 加入到队列中

step 4 转step2

step 5 结束

三、作用

图应用

无权图中2点最短路计算
图或树的层次遍历
图连通块相关的一些计算，比如判2点是否连通，有几个连通块。

隐式图应用

问从初始状态出发，是否可到达目标状态。
问从初始状态出发，到目标状态的最小代价。

四、代码框架

BFS层次遍历算法

// 层次遍历算法
func BFS(start State) [][]State {
    vis // 表示 某状态是否被访问过, 针对有环图的情况需要判断，无环图不用
    queue.Enqueue(start)
    vis[start]<-true
    ans [][]State
    while(!queue.Empty()) { // 查看当前层有没有元素
        l <- queue.Len() // 当前队列中前面l个元素都是当前层的元素，先记录下l，然后循环取l次就可以了
        curLevel []State // 当前层遍历结果
        for i <- 0 to l-1 {
            front <-  queue.Dequeu()
            curLevel = append(curLevel, front) //当前层结果收集
            for child : front.Children() { // 产生转移状态
                if vis[child] {continue} // 已经遍历过
                if !Region(child) {continue} // 不合法
                queue.Enqueue(child)
            }
        }

        // 一层遍历完了，加入到ans
        ans = append(ans, curLevel)
    }

    return ans
}

BFS求解2点最短路算法

// BFS求解2点最短路算法
// 无法到达返回-1
func BFS(start State, target State) int {
    vis // 表示 某状态是否被访问过, 针对有环图的情况需要判断，无环图不用
    queue.Enqueue(start)
    step <- 0 // 初始是走了0步
    vis[start]<-true
    while(!queue.Empty()) { // 查看当前层有没有元素
        l <- queue.Len() // 当前队列中前面l个元素都是当前层的元素，先记录下l，然后循环取l次就可以了
        curLevel []State // 当前层遍历结果
        for i <- 0 to l-1 {
            front <-  queue.Dequeu()
            if front == target { // 当前这一步走完就到达终点了，直接返回结果
                return step
            }
            for child : front.Children() { // 产生转移状态
                if vis[child] {continue} // 已经遍历过
                if !Region(child) {continue} // 不合法
                queue.Enqueue(child)
            }
        }

        // 这一步走不到，步数要+1
        step <- step+1
    }

    return -1 //所有结果都找不到终点
}

go实现树层次遍历模板

go语言中队列可以通过slice特性来实现。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func levelOrder(root *TreeNode) [][]int {
    ans := [][]int{}
    if root==nil {
        return ans
    }
    queue := []*TreeNode{root}
    for len(queue)>0 { // 判断当前队列中是否有元素
        curLevel := []int{}
        for i, l:=0, len(queue);i<l;i++ { //取前面l个元素为当前层元素
            front := queue[0] // 获取头
            queue = queue[1:] // 将头从队列中删除
            curLevel = append(curLevel, front.Val) // 添加到当前层

            // 查看孩子状态
            if front.Left!=nil {
                queue = append(queue, front.Left)
            }
            if front.Right!=nil {
                queue = append(queue, front.Right)
            }
        }

        ans  = append(ans, curLevel)
    }

    return ans
}

五、牛刀小试

练习1 层次遍历应用二叉树的层序遍历

题目链接 https://leetcode-cn.com/problems/binary-tree-level-order-traversal/

题目大意

给你一个二叉树，请你返回其按层序遍历得到的节点值。（即逐层地，从左到右访问所有节点）。

示例：
二叉树：[3,9,20,null,null,15,7],

3
/
9 20
/
15 7
返回其层序遍历结果：

[
[3],
[9,20],
[15,7]
]

题目解析

利用层次遍历，对每层进行收集，在一层结束后把当前层结果放入到整体结果中。

AC代码

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func levelOrder(root *TreeNode) [][]int {
    ans := [][]int{}
    if root==nil {
        return ans
    }
    queue := []*TreeNode{root}
    for len(queue)>0 {
        curLevel := []int{}
        for i, l:=0, len(queue);i<l;i++ {
            front := queue[0] // 获取头
            queue = queue[1:] // 将头从队列中删除
            curLevel = append(curLevel, front.Val) // 添加到当前层

            // 查看孩子状态
            if front.Left!=nil {
                queue = append(queue, front.Left)
            }
            if front.Right!=nil {
                queue = append(queue, front.Right)
            }
        }

        ans  = append(ans, curLevel)
    }

    return ans
}

练习2 连通块应用岛屿数量

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

题目大意

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1：

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

输入：grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
输出：3

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] 的值为 '0' 或 '1'

题目解析

把矩阵看成一个图，题目要求多少个岛屿，就是求图中有多少个连通块。可以利用广搜求连通块。

具体做法如下：从每一个点出发（如果已经搜索则略过，说明和前面的点连通），没有搜索过就是一个新的岛屿（岛屿数+1），搜索出所有相通的点。

AC代码

func getInd(state []int) int {
    return state[0]*1000+state[1]
}

func numIslands(grid [][]byte) int {
    n, m := len(grid), len(grid[0])
    vis := map[int]bool{} // 标记是否搜索过
    sum := 0 // 总岛屿数
    dir := [][]int{{0,1},{0,-1},{-1,0},{1,0}} // 上下左右4个方向
    var bfs = func(start []int) int {// 搜索由start组成的所有陆地，返回1 如果有陆地，否则返回0
        if grid[start[0]][start[1]]=='0' {return 0} // 非陆地
        if vis[getInd(start)] {return 0} //已经搜索过了
        queue := [][]int{start}

        for len(queue)>0 {
            // 这里不需要知道某一层的具体情况，只要队列里有东西就取出来，然后把转移状态加入到队列中
            front := queue[0]
            queue = queue[1:]

            // 状态转移
            for _, d:=range dir {
                nx, ny := front[0]+d[0], front[1]+d[1] // 新状态

                // 开始判断合法性
                if nx<0 || nx>=n || ny<0 || ny>=m { // 越界了
                    continue
                }

                if grid[nx][ny]=='0' { //非陆地
                    continue
                }

                //查看是否已经遍历过
                newState := []int{nx, ny}
                if vis[getInd(newState)]  {continue}
                vis[getInd(newState)] = true// 标记遍历过了
                queue = append(queue, newState)
            }
        }

        return 1
    }

    for i, row := range grid {
        for j:=range row {
            sum += bfs([]int{i,j})
        }
    }

    return sum
}
/*
[["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]]
[["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]
[["0"]]
*/

练习3 最短路应用单词接龙

题目链接：https://leetcode-cn.com/problems/word-ladder/

题目大意

字典 wordList 中从单词 beginWord 和 endWord 的转换序列是一个按下述规格形成的序列：

序列中第一个单词是 beginWord 。
序列中最后一个单词是 endWord 。
每次转换只能改变一个字母。
转换过程中的中间单词必须是字典 wordList 中的单词。
给你两个单词 beginWord 和 endWord 和一个字典 wordList ，找到从 beginWord 到 endWord 的最短转换序列中的单词数目。如果不存在这样的转换序列，返回 0。

示例 1：

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
输出：5
解释：一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的长度 5。
示例 2：

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
输出：0
解释：endWord "cog" 不在字典中，所以无法进行转换。

提示：

1 <= beginWord.length <= 10
endWord.length == beginWord.length
1 <= wordList.length <= 5000
wordList[i].length == beginWord.length
beginWord、endWord 和 wordList[i] 由小写英文字母组成
beginWord != endWord
wordList 中的所有字符串互不相同

题目解析

这是一个典型的隐式图搜索题目。

Step 为当前层次，初始为1。

beginWord就是起始状态，endWord是目标状态，状态转移方法就是每次改变单词中的一个字母，问最少通过多少次状态转移到达目标状态，无解输出0。

简单证明，为什么在某一层遍历到目标状态，答案就是当前step.

反证，假设endWord在x层找到，说明答案不可能<x，如果有的话，那么在x层之前就可以遍历到endWord。

思路与优化

/*
根据最短路模板给出以下搜索模板
*/
func bfs(beginWord string, endWord string) int {
    vis := map[string]bool{}
    queue := []string{beginWord}
    vis[beginWord]=true
    step :=1 // 根据题意，初始包括自己是1
    for len(queue)>0 {
        for i,l:=0, len(queue);i<l;i++ {
            front := queue[0]
            queue=queue[1:]
            if front == endWord{ //找到目标了。
                return step
            }

            for _, child := range getChild(front) {
                if vis[child]{continue}
                vis[child]=true
                queue=append(queue, child)
            }
        }
        step++
    }

    return 0
}

/*
上述代码中getChild(word)作用是获取 word通过改变一个字母可以得到的出现在wordList所有字符串，显然对于固定的word,getChild(word)结果是固定的，所以可以一开始就先计算出来，存储在map links[word]。
*/

func getLinksV1(wordList []string) map[string][]string{
    links := map[string][]string{}
    for _, s1 := range wordList {
        for _, s2 := range wordList {
            // 判断是s1到s2是否可以通过改1个字母
            // links[s1] = append(links[s1], s2)
        }
    }
    return links
}
/*
上述代码的复杂度是 10*O(n^2), n = 5000 总体复杂度是25*10^7 复杂度太大。
优化如下。
*/

func getLinksV2(wordList []string) map[string][]string{
    var  wordMap map[string]bool // 存储某个单词是否在wordList中
    links := map[string][]string{}
    for _, s1 := range wordList {
    for i:=0;i<len(s1);i++ { //对每一位，用a-z去替换
      for c:='a';c<='z';c++ {
        // 查看新单词newStr是否在wordMap中
        // links[s1] = append(links[s1], newStr)
      }
    }
    }
    return links
}
/*
上述代码复杂度是 O(n) * 10 * 26 大约是 10^6， 可以接受。
*/

AC代码

起始单词有可能不在wordList，也要生成child

func getLinksV2(wordList []string) map[string][]string {
    wordMap := map[string]bool{} // 存储某个单词是否在wordList中
    for _, s := range wordList {
        wordMap[s] = true
    }

    links := map[string][]string{}
    for _, s := range wordList {
        for i := 0; i < len(s); i++ { //对每一位，用a-z去替换
            bs := []byte(s)
            for c := 'a'; c <= 'z'; c++ {
                bs[i] = byte(c)
                if string(bs) == s {
                    continue
                }
                // 查看新单词newStr是否在wordMap中
                if wordMap[string(bs)] {
                    links[s] = append(links[s], string(bs))
                }
            }
        }
    }
    return links
}

/*
上述代码复杂度是 O(n) * 10 * 26 大约是 10^6， 可以接受。
*/
func ladderLength(beginWord string, endWord string, wordList []string) int {
    links := getLinksV2(append(wordList, beginWord)) // 起始单词有可能不在wordList，也要生成child
    // fmt.Println(links)
    var bfs = func(beginWord string, endWord string) int {
        vis := map[string]bool{}
        queue := []string{beginWord}
        vis[beginWord] = true
        step := 1 // 根据题意，初始包括自己是1
        for len(queue) > 0 {
            for i, l := 0, len(queue); i < l; i++ {
                front := queue[0]
                queue = queue[1:]
                if front == endWord { //找到目标了。
                    return step
                }

                for _, child := range links[front] {
                    if vis[child] {
                        continue
                    }
                    vis[child] = true
                    queue = append(queue, child)
                }
            }
            step++
        }

        return 0
    }

    return bfs(beginWord, endWord)
}

六、总结

主要内容：

广搜算法是一种暴力算法，适用于状态全集规模较小的图搜索问题。
作用：图应用主要有1）无权图中2点最短路计算，2）图或树的层次遍历，3）图连通块相关的一些计算，比如判2点是否连通，有几个连通块。

对于隐式图中状态可达性，以及2个状态之间转移的代价的计算也可以通过广搜来解决。
解题的基本框架比较固定，关键在于状态的定义，以及状态转移方法的构造。

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

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