算法系列：广度优先搜索

待我称王封你为后i 2022-09-03 06:14 238阅读 0赞

有一天，婷婷去超超的大学，想给异地已久的超超一个惊喜。但是方向感不好的婷婷很快就在大学迷路了，超超得知后便去寻找思恋已久的婷婷。此时超超的妈妈也在来学校的路上，现在超超要以最快的速度去寻找婷婷（不然可能会出现我和你妈同时迷路你先救谁的问题了????）。那么，问题来了，你可以制定一种策略帮超超尽快找到婷婷吗？

![bbf261d68a4e1c60abd2f06d4162e747.png][]

据说看完这篇文章的人都能帮助超超解决问题的同时，再顺手拿个offer！

下面将依次介绍广度优先搜索（本文简称为广搜）的定义，算法模板，俩种常见的题型，以及常见的出题点于易错点。

**一、什么是广搜**

**广搜定义**

又译作宽度优先搜索，或横向优先搜索，是一种图形搜索方法。简单的说，广度优先搜索（Breadth-First-Search，BFS）是从根节点开始，沿着树的宽度遍历树的节点。如果所有节点均被访问，则算法终止。

**广搜步骤**

以遍历下面这棵树为例

![f3f7c1158aaa5170f135f8af6c4bbfb7.png][]

*  定一个出发点：假设我们从v1出发来遍历这棵树，先将v1存到队列que中
    
      
    
    
    ![b9edcab271c729f996d4ada8d33eea48.png][]
 *  按层遍历：从队列中取出v1，然后将v1能搜索到的v2，v3存到队列que中
    
    ![81f2224e04c1e9cc473b45b5b24a69da.png][]  
    
 *  再从que中取出v2，v3，将v2能搜索到的v4和v5，v3能搜索到的v6和v7放到que中
    
    ![e3da46040c8f5ea215a2b14f5cc8520b.png][]
 *  再从que中取出v4，v5，v6，v7，均无子节点可以遍历，因此遍历结束

代码如下

1//树的节点
     2type TreeNode struct {
     3    Val   int
     4    Left  *TreeNode
     5    Right *TreeNode
     6}
     7
     8func bfs(root *TreeNode) {
     9  //初始化队列
    10    que := make([]*TreeNode, 0, 100)
    11    que = append(que, root)
    12
    13  //循环队列所有元素
    14    for len(que) != 0 {
    15        curSize := len(que)
    16
    17    //循环遍历每层节点
    18        for i := 0; i < curSize; i++ {
    19      //取出队列中节点
    20            tnode := que[0]
    21            que = que[1:]
    22
    23      //求出该节点所能到达的节点，进行入队列操作
    24            if tnode.Left != nil {
    25                que = append(que, tnode.Left)
    26            }
    27            if tnode.Right != nil {
    28                que = append(que, tnode.Right)
    29            }
    30        }
    31    }
    32}

抽象为模板

1   func bfs(root *TreeNode) int {
     2   //初始化队列
     3      que := make([]*TreeNode, 0, 100)
     4      que = append(que, root)
     5      dep := 1
     6
     7      //循环队列所有节点
     8      for len(que) != 0 {
     9         curSize := len(que)
    10
    11         //循环遍历每层节点
    12         for i := 0; i < curSize; i++ {
    13            //取出队列首节点
    14            tnode := que[0]
    15            que = que[1:]
    16
    17           for 当前节点所有方向{
    18            //对移动后的节点做坐标值变化
    19
    20            //无法到达点，是否为边界，障碍物
    21             ...
    22            //终点判断，题目所求的点
    23             ...
    24            //入队列
    25             ...
    26           }
    27         }
    28        //深度变化（层数或步数）
    29         dep++
    30      }
    31      return 0
    32   }

**易错点**

*  遍历每层节点时，先求出当前队列长度curSize而不是用len(que)作为该层队列的长度，如果用len(que)后面入队列操作，会使len(que)一直在变化
 *  边界值、结果值判断；入队列的判断顺序：入队列一定是在最后，如果放在前面会将无法到达点放入队列

**带备忘录的广搜**

在树中节点之间是有方向的，我们只能从父节点遍历到子节点，而无法从子节点遍历到父节点，但是在图的遍历中往往子节点也能遍历到父节点。例如下图中，每个节点可以有上下左右，以及左上，左下，右上，右下八个方向可以移动，从A1出发可以遍历到A2，B1，B2点，当A2出队列时，他同样可以遍历到A1，这样A1就会被重复遍历，因此需要定义一个visited切片标记当前哪些节点被遍历过。

![ff8c2f78eba9bfedd0f4479ae7e0eba2.png][]

**二、常见题型**

图中最短路径

下面来看看广搜怎么解决超超的问题，用0表示空地，1表示障碍物，假设超超在地图左上角，婷婷在地图的右下角，超超每一步可以沿着八个方向移动。那么地图可以抽象为下图所示，超超希望的就是用最少的移动步数从左上角移动到右下角。

![bbb67980a58d19ae533166ada643c43a.png][]

分析：超超的问题是标准的图中求俩点间最短路径问题，显然可以利用广搜从左上角出发，一层层的遍历下去直到遍历到右下角，为了快速帮超超解决问题，下面直接上模板

1func bfs(root *TreeNode) int {
     2   //初始化队列
     3   que := make([]*TreeNode, 0, 100)
     4   que = append(que, root)
     5   dep := 1
     6
     7   //循环队列所有节点
     8   for len(que) != 0 {
     9      curSize := len(que)
    10
    11      //循环遍历每层节点
    12      for i := 0; i < curSize; i++ {
    13
    14         //取出队列节点
    15         tnode := que[0]
    16         que = que[1:]
    17
    18        for 当前节点所有方向{
    19          //对移动后的节点做坐标值变化
    20
    21         //特殊值，是否为边界，障碍物
    22          ...
    23         //结果值判断，是否到达题目要求的目标点
    24          ...
    25         //入队列
    26          ...
    27        }
    28      }
    29     //深度变化（步数）
    30      dep++
    31   }
    32   return 0
    33}

*  是否需要visited标识：在搜索时每个节点都会向八个方向搜索，A向右移动到B节点入队列后，向后遍历下一层时B还会向左搜索到A，因此需要用visited进行标识该节点是否被遍历过
 *  确定移动方向：超超一共有八个移动方向，可以用数组next := \[\]\[\]int\{ \{1, 0\}, \{-1, 0\}, \{0, 1\}, \{0, -1\}, \{1, 1\}, \{1, -1\}, \{-1, 1\}, \{-1, -1\}\}表示移动方向，俩个维度分别表示坐标x和y的变化

![fa84acae9618d28e3edf1e85d7fced68.png][]

*  遍历的特殊值判断：这题有边界值墙，障碍物，以及终点

完整代码如下

1func shortestPathBinaryMatrix(grid [][]int) int {
     2    width := len(grid)
     3  //若起点和终点是障碍物则地图有问题
     4    if grid[0][0] == 1 || grid[width-1][width-1] == 1 {
     5        return -1
     6    }
     7  //地图中起点和终点是一个点
     8    if width == 1 {
     9        return 1
    10    }
    11
    12  //初始化队列和visited
    13    que := make([]*Node, 0, width*width)
    14    visited := make([][]bool, width)
    15    for i := 0; i < len(visited); i++ {
    16        visited[i] = make([]bool, width)
    17    }
    18    dep := 1
    19  //每个节点所能走的八个方向
    20    next := [][]int{
        {1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}}
    21    que = append(que, &Node{0, 0})
    22    visited[0][0] = true
    23
    24  //开始搜索
    25    for len(que) != 0 {
    26        current := len(que)
    27    //按层遍历
    28        for i := 0; i < current; i++ {
    29            top := que[0]
    30            que = que[1:]
    31      //对队列中的节点做八个方向的坐标变化
    32            for i := 0; i < 8; i++ {
    33                var temp *Node = new(Node)
    34                temp.x = top.x + next[i][0]
    35                temp.y = top.y + next[i][1]
    36        //移动后坐标越界
    37                if temp.x >= width || temp.x < 0 || temp.y >= width || temp.y < 0 {
    38                    continue
    39                }
    40        //找到终点（右下角）
    41                if temp.x == width-1 && temp.y == width-1 {
    42                    return dep + 1
    43                }
    44        //不是障碍物并且没有被遍历过入队列
    45                if grid[temp.x][temp.y] != 1 && !visited[temp.x][temp.y] {
    46                    que = append(que, temp)
    47                    visited[temp.x][temp.y] = true
    48                }
    49            }
    50        }
    51    //层数加1
    52        dep++
    53    }
    54    return -1
    55}

##### 字符串最短变化次数 #####

![3bd15ac9c25b62f2085c7399d6a1b18e.png][]

帮助完超超之后，也要为我们的offer好好准备下了，面试算法很少会直接出一个图的bfs题型，比较常见的是这种题型。这题看似和bfs没有关系，但是我们稍作抽象就可以联系在一起了，起点hit能匹配的字符串为\*it，h \* t，hi\*，**与worldList中可以匹配的节点就是从hit出发能到达的节点了**，这样依次连接下去是不是就可以连成图了！这题也就变成了求hit到cog的最短距离。

![e5c29ca469011fdb7ec487fc3533ba63.png][]

分析：

*  是否需要visited标识：这题的visited有俩个含义，一个是判断当前map中是否有匹配的word，二是做备忘录，当从hit出发将hot加入队列后，防止hot遍历其可到达的点时又将hit加入队列中
 *  确定移动方向：以hit为例，只要满足\*it，h \* t，hi\*，都为可移动方向，也就是循环hit中每一个字符，从'a'到'z'遍历，根据visited判断字典中是否有该字符串
 *  遍历的特殊值判断：终点，是否被遍历过

代码

1func ladderLength(beginWord string, endWord string, wordList []string) int {
     2    //定义并初始化visited
     3    visited := map[string]bool{}
     4    for _, w := range wordList {
     5        visited[w] = false
     6    }
     7    que := []string{beginWord}
     8    dep := 1
     9  //遍历所有元素
    10    for len(que) != 0 {
    11        curSize := len(que)
    12        for i := 0; i < curSize; i++ {
    13            top := que[0]
    14            que = que[1:]
    15            if top == endWord {
    16                return dep
    17            }
    18      //判断能连接的字符串
    19            for c := 0; c < len(top); c++ {
    20                for j := 'a'; j <= 'z'; j++ {
    21                    newWord := top[:c] + string(j) + top[c+1:]
    22                    if visited[newWord] == false {
    23                        que = append(que, newWord)
    24                        visited[newWord] = true
    25                    }
    26                }
    27            }
    28        }
    29        dep++
    30    }
    31    return 0
    32}

**三、总结**

**出题点****：**BFS的普适题型一共是三种：树的层次遍历，图的最短路径，字符串匹配最少次数。找准关键字“最短路径”，“层次遍历”。

**模板记忆****：**水纹波动有规律，层次遍历层层清（cursize，visited），找准特殊位置点（墙，终点，是否遍历过），判断条件有先后（特殊点判断先后顺序）。

![955d31d60728c5bba1e5939bab3b5b48.png][]

**思路****：**拿到题目，我们首先可以捕捉关键词，一旦看到有“最短路径”、“层次遍历”这种词语，那么我们应该想到BFS。但是有时候题目会隐藏这种暴露语句，例如单词接龙一样，这时我们需要抽象它的本质，能否将每一个字符串看作一个节点进行连接。需要注意的是，在遍历时或许会有重复路径的可能，这时不要忘了设visted的备忘录。同时，我们需要注意障碍物，边界值，终点位置的先后判断。

**易错点****：**循环队列中节点用curSize记录当前队列长度，而不是用len(que)。

感谢你的**点赞**和**在看**哦~

![41440760e1e99b44a56e3f2b17391fde.gif][]

[bbf261d68a4e1c60abd2f06d4162e747.png]: /images/20220829/c2e2e023bc6249e8af8fe209af46e008.png
[f3f7c1158aaa5170f135f8af6c4bbfb7.png]: /images/20220829/1e1198f0508c4e63a76b8b5715f50472.png
[b9edcab271c729f996d4ada8d33eea48.png]: /images/20220829/09ef4d39505e4eed828bfa677b6fa552.png
[81f2224e04c1e9cc473b45b5b24a69da.png]: /images/20220829/ae8e24887b5d496c99108fe0d68008a4.png
[e3da46040c8f5ea215a2b14f5cc8520b.png]: /images/20220829/ddb982c5527145b9a8a90d130f180366.png
[ff8c2f78eba9bfedd0f4479ae7e0eba2.png]: /images/20220829/436190e34a784959bf12a68e31b0daf1.png
[bbb67980a58d19ae533166ada643c43a.png]: /images/20220829/275a4817b54d4b55b8496cbc267502c8.png
[fa84acae9618d28e3edf1e85d7fced68.png]: /images/20220829/62bc82d56f59488a93374473535053a8.png
[3bd15ac9c25b62f2085c7399d6a1b18e.png]: /images/20220829/f922f401333b4f8caeca7def79972523.png
[e5c29ca469011fdb7ec487fc3533ba63.png]: /images/20220829/06b260ab0aff468f88d18eab3bcd29e8.png
[955d31d60728c5bba1e5939bab3b5b48.png]: /images/20220829/9203176423e54e0e8742dc8a127ff74c.png
[41440760e1e99b44a56e3f2b17391fde.gif]: /images/20220829/ae3adee1994c49b3afc86b74733687c3.png