概念
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 copyfrom rich.console import Consolefrom rich import printconsole = 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, 须要源码能够私信~~
- 简繁火星字体转换
- 哄女友神器
- 号码测吉凶
- 电视节目直播表