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?)。
七、实战训练
代码基础训练题
光说不练假把式,学完了怎么也要实操一下吧,快快动用把刚才那例题A了。
- 层次遍历应用 题目链接 https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
- 连通块应用 题目链接 https://leetcode-cn.com/problems/number-of-islands/
- 最短路应用 题目链接 https://leetcode-cn.com/problems/word-ladder/
AK leetcode
leetcode相关题目都在下面了,拿起武器挨个点名呗。
https://leetcode-cn.com/tag/breadth-first-search/problemset/ 二分查找题目列表
以上题目太多,大家适当选择就行,下面还有进阶题目。
大神进阶
hdu
- http://acm.hdu.edu.cn/showproblem.php?pid=1026
- http://acm.hdu.edu.cn/showproblem.php?pid=1035
- http://acm.hdu.edu.cn/showproblem.php?pid=1043
- http://acm.hdu.edu.cn/showproblem.php?pid=1072
- http://acm.hdu.edu.cn/showproblem.php?pid=1195
- http://acm.hdu.edu.cn/showproblem.php?pid=1226
- http://acm.hdu.edu.cn/showproblem.php?pid=1241
- http://acm.hdu.edu.cn/showproblem.php?pid=1242
- http://acm.hdu.edu.cn/showproblem.php?pid=1252
- http://acm.hdu.edu.cn/showproblem.php?pid=1253
- http://acm.hdu.edu.cn/showproblem.php?pid=1312
- http://acm.hdu.edu.cn/showproblem.php?pid=1372
- http://acm.hdu.edu.cn/showproblem.php?pid=1426
- http://acm.hdu.edu.cn/showproblem.php?pid=1495
- http://acm.hdu.edu.cn/showproblem.php?pid=1547
- http://acm.hdu.edu.cn/showproblem.php?pid=1548
- http://acm.hdu.edu.cn/showproblem.php?pid=1885
- http://acm.hdu.edu.cn/showproblem.php?pid=2128
- http://acm.hdu.edu.cn/showproblem.php?pid=2416
- http://acm.hdu.edu.cn/showproblem.php?pid=2605
- http://acm.hdu.edu.cn/showproblem.php?pid=2612
- http://acm.hdu.edu.cn/showproblem.php?pid=2614
- http://acm.hdu.edu.cn/showproblem.php?pid=2616
- http://acm.hdu.edu.cn/showproblem.php?pid=2717
- http://acm.hdu.edu.cn/showproblem.php?pid=2821
- http://acm.hdu.edu.cn/showproblem.php?pid=2952
- http://acm.hdu.edu.cn/showproblem.php?pid=2977
- http://acm.hdu.edu.cn/showproblem.php?pid=4394
poj
- http://poj.org/problem?id=1475
- http://poj.org/problem?id=1915
- http://poj.org/problem?id=1979
- http://poj.org/problem?id=2046
- http://poj.org/problem?id=2110
- http://poj.org/problem?id=3126
- http://poj.org/problem?id=3271
- http://poj.org/problem?id=3278
- http://poj.org/problem?id=3669
- http://poj.org/problem?id=3984