概念
BFS(廣度優(yōu)先搜索)是最簡(jiǎn)便的圖的搜索算法之一馏颂，這一算法也是很多重要的圖的算法的原型蹬跃。
BFS算法的核心思想就是把一些問(wèn)題抽象成圖.
BFS相對(duì)DFS最主要的區(qū)別是: BFS找到的路徑一定是最短的,但代價(jià)是空間復(fù)雜度比DFS大很多.
BFS常出現(xiàn)的場(chǎng)景: 問(wèn)題的本質(zhì)就是讓你在一幅圖中找到從起點(diǎn) start 到終點(diǎn) target的最近距離,BFS算法其實(shí)就是在干這事.
一般來(lái)說(shuō)在找最短路徑的時(shí)候用BFS,其他時(shí)候還是用DFS多一些.
傳統(tǒng)的BFS框架是從起點(diǎn)開(kāi)始向四周擴(kuò)散,遇到終點(diǎn)時(shí)停止;而雙向BFS則是從起點(diǎn)和終點(diǎn)同時(shí)開(kāi)始擴(kuò)散,當(dāng)兩邊有交集的時(shí)候停止.
使用雙向BFS的前提是,必須提前知道終點(diǎn)在哪里.
無(wú)論傳統(tǒng)BFS還是雙向BFS,無(wú)論做不做優(yōu)化,從Big O 的衡量標(biāo)準(zhǔn)看,空間復(fù)雜度都是一樣的.
例題: 打開(kāi)密碼鎖
有一個(gè)帶四個(gè)圓形撥輪的轉(zhuǎn)盤(pán)鎖,每個(gè)撥輪都有0-9共10個(gè)數(shù)字,
每個(gè)撥輪可以上下旋轉(zhuǎn): 例如把9變成0, 0變成9,每次旋轉(zhuǎn)只能將一個(gè)撥輪旋轉(zhuǎn) 一下
代碼(python)
import copy
from rich.console import Console
from rich import print
console = Console()
res = []
#~ 解開(kāi)密碼鎖的最少次數(shù)
# 將密碼向上撥動(dòng)一次
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
# 將密碼向下?lián)軇?dòng)一次
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
# 傳統(tǒng)BFS,從起點(diǎn)出發(fā)擴(kuò)散
def openLock(deadends,target):
#記錄需要跳過(guò)的密碼
deads = []
for i in deadends:
deads.append(i)
#記錄已經(jīng)窮舉過(guò)的密碼,防止走回頭路
visited = []
q = []
#從起點(diǎn)開(kāi)始啟動(dòng)廣度優(yōu)先搜索
step = 0
q.append("0000")
visited.append("0000")
while(q != None):
sz = len(q)
#將當(dāng)前隊(duì)列中的所有節(jié)點(diǎn)向周?chē)鷶U(kuò)散
for i in range(sz):
cur = q.pop(0)
print(cur)
#判斷密碼是否合法,是否到達(dá)終點(diǎn)
if cur in deads:
continue
if cur == target:
return step
# 將一個(gè)節(jié)點(diǎn)的未遍歷相鄰節(jié)點(diǎn)加入隊(duì)列
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):
#記錄需要跳過(guò)的密碼
deads = []
for i in deadends:
deads.append(i)
#記錄已經(jīng)窮舉過(guò)的密碼,防止走回頭路
visited = []
q1 = []
q2 = []
#初始化起點(diǎn)和終點(diǎn)
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)
