NarcissusBlog广度优先搜索
目录
BFS的核心思想就是把一些问题抽象成图，从一个点开始，向四周开始扩散。一般来说，写BFS算法都用队列这种数据结构，每次将一个节点周围所有节点加入队列。
1、算法框架
BFS常见场景问题的本质就是在一幅图中找起点start到终点target的最近距离。
cur.adj()泛指cur相邻的节点；visited主要作用是防止走回头路，大部分的时候是必须的，但像一般的二叉树结构，没有子节点到父节点的指针，不会走回头路就不需要visited。
2、二叉树最小高度
一个简单的BFS题目，如下：
首先明确起点start和终点target是什么，怎么判断到了终点：显然起点就是root根节点，终点就是最靠近根节点的那个叶子节点。
代码如下：
func minDepth(root *TreeNode) int {
// BFS
if root == nil {
return 0
}
var queue []*TreeNode
// 先将起点加入队列并记录扩散步数
queue = append(queue, root)
step := 1
for len(queue) != 0 {
size := len(queue)
// 将当前队列中的所有节点向四周扩散
for i := 0; i < size; i++ {
cur := queue[i]
// 判断是否到达终点
if cur.Left == nil && cur.Right == nil {
return step
}
// 将cur相邻节点加入队列中
if cur.Left != nil {
queue = append(queue, cur.Left)
}
if cur.Right != nil {
queue = append(queue, cur.Right)
}
}
queue = queue[size:]
// 更新步数
step++
}
return 0
}
3、解开密码锁的最少次数
密码锁总共有4个位置，每个位置可以向上转，也可以向下转，就有8种可能。这就可以抽象成一幅图，每个节点有8个相邻的节点，求最短路径。代码如下：
func openLock(deadends []string, target string) int {
// 广度优先搜索
var queue []string
queue = append(queue, "0000")
// 记录已经穷举过的密码，防止走回头路
visited := map[string]struct{}{}
// 将deadends中的元素也加入到visited中
for _, val := range deadends {
// 特殊情况，死亡集合中有初始密码
if val == "0000" {
return -1
}
visited[val] = struct{}{}
}
step := 0
for len(queue) != 0 {
q_size := len(queue)
// 将当前队列中所有节点向周围扩散
for i := 0; i < q_size; i++ {
cur := queue[i]
// 判断是否到达终点
if cur == target {
return step
}
// 将一个节点的相邻节点加入到队列
for j := 0; j < 4; j++{
up := plusOne([]byte(cur), j)
if _, ok := visited[up]; !ok {
queue = append(queue, up)
visited[up] = struct{}{}
}
down := minusOne([]byte(cur), j)
if _, ok := visited[down]; !ok {
queue = append(queue, down)
visited[down] = struct{}{}
}
}
}
// 增加步数
step++
queue = queue[q_size:]
}
return -1
}
// 将s[j]向上拨动一次
func plusOne(s []byte, j int) string {
if s[j] == '9' {
s[j] = '0'
} else {
s[j] += 1
}
return string(s)
}
// 将s[j]向下拨动一次
func minusOne(s []byte, j int) string {
if s[j] == '0' {
s[j] = '9'
} else {
s[j] -= 1
}
return string(s)
}
4、双向BFS优化
BFS还有一种稍微高级一点的优化思路：双向BFS，可以进一步提高算法效率。
传统BFS框架就是从起点开始向四周扩散，遇到终点时停止；而双向BFS则是从起点和终点同时开始扩散，当两边有交集的时候停止。双向BFS只需要遍历半棵树就会找到最短路径，但是必须知道终点在哪里。
代码如下：
func openLock(deadends []string, target string) int {
// 双向BFS
// 使用哈希表作为队列，方便判断两个集合是否相交
q1, q2 := map[string]struct{}{}, map[string]struct{}{}
q1["0000"] = struct{}{}
q2[target] = struct{}{}
// 记录已经穷举过的密码，防止走回头路
visited := map[string]struct{}{}
// 将deadends中的元素也加入到visited中
for _, val := range deadends {
// 特殊情况，死亡集合中有初始密码
if val == "0000" {
return -1
}
visited[val] = struct{}{}
}
step := 0
for len(q1) != 0 && len(q2) != 0 {
// 哈希集合在遍历的过程中不能修改，用 temp 存储扩散结果
temp := map[string]struct{}{}
// 扩散元素少的队列
if len(q1) > len(q2) {
q1, q2 = q2, q1
}
// 将q1中所有节点向周围扩散
for cur, _ := range q1 {
// 判断是否到达终点
if _, ok := q2[cur]; ok {
return step
}
visited[cur] = struct{}{}
// 将一个节点的相邻节点加入到队列
for j := 0; j < 4; j++{
up := plusOne([]byte(cur), j)
if _, ok := visited[up]; !ok {
temp[up] = struct{}{}
}
down := minusOne([]byte(cur), j)
if _, ok := visited[down]; !ok {
temp[down] = struct{}{}
}
}
}
// 增加步数
step++
// 交换q1, q2,下一轮相当于扩散q2
q1, q2 = q2, temp
}
return -1
}
// 将s[j]向上拨动一次
func plusOne(s []byte, j int) string {
if s[j] == '9' {
s[j] = '0'
} else {
s[j] += 1
}
return string(s)
}
// 将s[j]向下拨动一次
func minusOne(s []byte, j int) string {
if s[j] == '0' {
s[j] = '9'
} else {
s[j] -= 1
}
return string(s)
}
- 双向BFS队列用哈希表代替， 方便快速判断两个集合是否相交。后续扩散的时候，由于遍历过程中哈希表不能修改(因为哈希表无须性)，所以需要临时的哈细胞存放扩散后的节点。
- while 循环的最后交换
q1和q2的内容，所以只要默认扩散q1就相当于轮流扩散q1和q2。 - while开始的时候交换
q1和q2的内容，目的是每次都选择一个较小的集合进行扩散，那么占用的空间增长速度就会慢一些，效率就会高一些。
5、滑动拼图问题
比如输入一个二维数组board = [[4,1,2],[5,0,3]]，算法会返回5：
BFS算法并不只是一个寻路算法，而是一种暴力搜索算法，只要涉及暴力穷举问题，都可以考虑BFS。
代码如下：
func slidingPuzzle(board [][]int) int {
// BFS
// 将每一种情况的二维数组转换为字符串方式
var queue []string
target := "123450"
var st []byte
// 将初始二维数组转换为字符串
for i := 0; i < 2; i++ {
for j := 0; j < 3; j++ {
st = append(st, byte(board[i][j]) + '0')
}
}
start := string(st)
queue = append(queue, start)
visited := map[string]struct{}{}
visited[start] = struct{}{}
step := 0
// 二维到一维映射表
table := [][]int{
{1, 3},
{0, 2, 4},
{1, 5},
{0, 4},
{1, 3, 5},
{2, 4},
}
for len(queue) != 0 {
size := len(queue)
for i := 0; i < size; i++ {
t := queue[i]
// 判断是否到达终点
if t == target {
return step
}
cur := []byte(t)
index := getZeroIndex(cur)
for i := 0; i < len(table[index]); i++ {
temp := make([]byte, 6)
copy(temp, cur)
temp[index], temp[table[index][i]] = temp[table[index][i]], temp[index]
temp2 := string(temp)
if _, ok := visited[temp2]; !ok {
queue = append(queue, temp2)
visited[temp2] = struct{}{}
}
}
}
queue = queue[size:]
step++
}
return -1
}
func getZeroIndex(s []byte) int {
for i := 0; i < len(s); i++ {
if s[i] == '0' {
return i
}
}
return -1
}
- 第一个技巧就是将每一种二维数组情况转换为字符串形式，方便BFS操作。
- 二维映射到一维，没有上下左右概念，建立了一个映射表：
含义就是在在一维字符串中，索引i在二维数组中的相邻索引为table[i]：
注意：因为知道target,所以可以使用双向BFS进行优化。