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

[LightningBilly]

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

一、简介

广度优先搜索算法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), 结点数加边的数量。

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

二、条件及解题步骤

条件：

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

解题步骤

• 定义数据

1. 定义状态表示
2. 定义状态转移方法
3. 定义边界判断方法

• 具体操作

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

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

step3 遍历当前层结点

​ 1. 产生新状态，

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

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

​ 4. 加入到队列中

step 4 转step2

step 5 结束

三、作用

图应用

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

隐式图应用

1. 问从初始状态出发，是否可到达目标状态。
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 层次遍历应用 二叉树的层序遍历

题目链接 力扣

题目大意

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

示例：
二叉树：[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 连通块应用 岛屿数量

题目链接：力扣

题目大意

给你一个由 ‘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 最短路应用 单词接龙

题目链接：力扣

题目大意

字典 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. 作用：图应用主要有1）无权图中2点最短路计算，2）图或树的层次遍历，3）图连通块相关的一些计算，比如判2点是否连通，有几个连通块。

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

3. 解题的基本框架比较固定，关键在于状态的定义，以及状态转移方法的构造。

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

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

七、实战训练

代码基础训练题

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

1. 层次遍历应用 题目链接 力扣
2. 连通块应用 题目链接 力扣
3. 最短路应用 题目链接 力扣

AK leetcode

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

力扣 二分查找题目列表

---

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

大神进阶

hdu

1. http://acm.hdu.edu.cn/showproblem.php?pid=1026
2. http://acm.hdu.edu.cn/showproblem.php?pid=1035
3. http://acm.hdu.edu.cn/showproblem.php?pid=1043
4. http://acm.hdu.edu.cn/showproblem.php?pid=1072
5. http://acm.hdu.edu.cn/showproblem.php?pid=1195
6. http://acm.hdu.edu.cn/showproblem.php?pid=1226
7. http://acm.hdu.edu.cn/showproblem.php?pid=1241
8. http://acm.hdu.edu.cn/showproblem.php?pid=1242
9. http://acm.hdu.edu.cn/showproblem.php?pid=1252
10. http://acm.hdu.edu.cn/showproblem.php?pid=1253
11. http://acm.hdu.edu.cn/showproblem.php?pid=1312
12. http://acm.hdu.edu.cn/showproblem.php?pid=1372
13. http://acm.hdu.edu.cn/showproblem.php?pid=1426
14. http://acm.hdu.edu.cn/showproblem.php?pid=1495
15. http://acm.hdu.edu.cn/showproblem.php?pid=1547
16. http://acm.hdu.edu.cn/showproblem.php?pid=1548
17. http://acm.hdu.edu.cn/showproblem.php?pid=1885
18. http://acm.hdu.edu.cn/showproblem.php?pid=2128
19. http://acm.hdu.edu.cn/showproblem.php?pid=2416
20. http://acm.hdu.edu.cn/showproblem.php?pid=2605
21. http://acm.hdu.edu.cn/showproblem.php?pid=2612
22. http://acm.hdu.edu.cn/showproblem.php?pid=2614
23. http://acm.hdu.edu.cn/showproblem.php?pid=2616
24. http://acm.hdu.edu.cn/showproblem.php?pid=2717
25. http://acm.hdu.edu.cn/showproblem.php?pid=2821
26. http://acm.hdu.edu.cn/showproblem.php?pid=2952
27. http://acm.hdu.edu.cn/showproblem.php?pid=2977
28. http://acm.hdu.edu.cn/showproblem.php?pid=4394

poj

1. 1475 -- Pushing Boxes
2. 1915 -- Knight Moves
3. 1979 -- Red and Black
4. 2046 -- Gap
5. 2110 -- Mountain Walking
6. 3126 -- Prime Path
7. 3271 -- Lilypad Pond
8. 3278 -- Catch That Cow
9. 3669 -- Meteor Shower
10. 3984 -- 迷宫问题

---

本人码农，希望通过自己的分享，让大家更容易学懂计算机知识。