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

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

一、简介

广度优先搜索算法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. Problem - 1035
  3. http://acm.hdu.edu.cn/showproblem.php?pid=1043
  4. Problem - 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. Problem - 1252
  10. http://acm.hdu.edu.cn/showproblem.php?pid=1253
  11. Problem - 1312
  12. Problem - 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. Problem - 1548
  17. Problem - 1885
  18. http://acm.hdu.edu.cn/showproblem.php?pid=2128
  19. Problem - 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. Problem - 2952
  27. http://acm.hdu.edu.cn/showproblem.php?pid=2977
  28. Problem - 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 -- 迷宫问题

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

在这里插入图片描述