共计 1938 个字符,预计需要花费 5 分钟才能阅读完成。
概念
BFS(广度优先搜寻)是最简便的图的搜索算法之一,这一算法也是很多重要的图的算法的原型。
BFS 算法的核心思想就是把一些问题形象成图.
BFS 绝对 DFS 最次要的区别是: BFS 找到的门路肯定是最短的, 但代价是空间复杂度比 DFS 大很多.
BFS 常呈现的场景: 问题的实质就是让你在 一幅图
中找到从终点 start
到起点 target
的最近间隔,BFS 算法其实就是在干这事.
一般来说在找最短门路的时候用 BFS, 其余时候还是用 DFS 多一些.
传统的 BFS 框架是从终点开始向周围扩散, 遇到起点时进行; 而双向 BFS 则是从终点和起点同时开始扩散, 当两边有交加的时候进行.
应用双向 BFS 的前提是, 必须提前晓得起点在哪里.
无论传统 BFS 还是双向 BFS, 无论做不做优化, 从 Big O 的衡量标准看, 空间复杂度都是一样的.
例题: 关上密码锁
有一个带四个圆形拨轮的转盘锁, 每个拨轮都有 0 - 9 共 10 个数字,
每个拨轮能够高低旋转: 例如把 9 变成 0, 0 变成 9, 每次旋转只能将一个拨轮旋转 一下
代码(python)
import copy
from rich.console import Console
from rich import print
console = Console()
res = []
#~ 解开密码锁的起码次数
# 将明码向上拨动一次
def plusOne(s,j):
ch = []
for i in s:
ch.append(i)
if ch[j] == '9':
ch[j] = str(0)
else:
ch[j] = str(int(ch[j]) + 1 )
# print(ch)
res = ''
for i in ch:
res += i
return res
# 将明码向下拨动一次
def minusOne(s,j):
ch = []
for i in s:
ch.append(i)
if ch[j] == '0':
ch[j] = str(9)
else:
ch[j] = str(int(ch[j]) - 1 )
res = ''
for i in ch:
res += i
return res
# 传统 BFS, 从终点登程扩散
def openLock(deadends,target):
#记录须要跳过的明码
deads = []
for i in deadends:
deads.append(i)
#记录曾经穷举过的明码, 避免走回头路
visited = []
q = []
#从终点开始启动广度优先搜寻
step = 0
q.append("0000")
visited.append("0000")
while(q != None):
sz = len(q)
#将以后队列中的所有节点向四周扩散
for i in range(sz):
cur = q.pop(0)
print(cur)
#判断明码是否非法, 是否达到起点
if cur in deads:
continue
if cur == target:
return step
# 将一个节点的未遍历相邻节点退出队列
for j in range(4):
up = plusOne(cur,j)
if up not in visited:
q.append(up)
visited.append(up)
down = minusOne(cur,j)
if down not in visited:
q.append(down)
visited.append(down)
step += 1
return -1
# 双向 BFS
def both_openLock(deadends,target):
#记录须要跳过的明码
deads = []
for i in deadends:
deads.append(i)
#记录曾经穷举过的明码, 避免走回头路
visited = []
q1 = []
q2 = []
#初始化终点和起点
q1.append("0000")
q2.append(target)
step = 0
while(q1 != None and q2 != None):
print('q1 is' + str(q1))
print('q2 is' + str(q2))
temp = []
for cur in q1:
if cur in deads:
continue
if cur in q2:
return step
visited.append(cur)
for j in range(4):
up = plusOne(cur,j)
if up not in visited:
temp.append(up)
down = minusOne(cur,j)
if down not in visited:
temp.append(down)
step += 1
print('temp is'+ str(temp))
q1 = q2
q2 = temp
return -1
deadends = ["0007","5678"]
target = "2222"
res = both_openLock(deadends,target)
print(res)
Flutter 写的 app, 须要源码能够私信~~
- 简繁火星字体转换
- 哄女友神器
- 号码测吉凶
- 电视节目直播表
最好的笔记软件
正文完