定義

·廣度優(yōu)先搜索指出是否有從A到B的路徑。

·如果有，廣度優(yōu)先搜索將找出最短路徑。

·面臨類(lèi)似于尋找最短路徑的問(wèn)題時(shí)，可嘗試使用圖來(lái)建立模型，再使用廣度優(yōu)先搜索來(lái)解決問(wèn)題。

·有向圖中的邊為箭頭，箭頭的方向指定了關(guān)系的方向，例如，rama→adit表示rama欠adit錢(qián)。

·無(wú)向圖中的邊不帶箭頭，其中的關(guān)系是雙向的，例如，ross-rachel表示"ross與rachel約會(huì)，而rache也與ross約會(huì)"。

·隊(duì)列是先進(jìn)先出（FIFO）的。

·棧是后進(jìn)先出（LIFO）的。

·你需要按加入順序檢查搜索列表中的人，否則找到的就不是最短路徑，因此搜索列表必須是隊(duì)列。

·對(duì)于檢查過(guò)的人，務(wù)必不要再去檢查，否則可能導(dǎo)致無(wú)限循環(huán)。

#廣度優(yōu)先算法

graph={

"A":["B","C"],

"B":["A","C","D"],

"C":["A","B","D","E"],

"D":["B","C","E","F"],

"E":["C","D"],

"F":["D"]

}

def BFS(graph,s):

? ? #創(chuàng)建隊(duì)列queue

? ? queue=[]

? ? #加入變量起點(diǎn)根s

? ? queue.append(s)

? ? # 鄰居節(jié)點(diǎn)，判斷是否重復(fù)遍歷

? ? seen=set()#創(chuàng)建一個(gè)集合

? ? seen.add(s)#加入

? ? relpace=0#記錄所走步長(zhǎng)

? ? while queue:

? ? ? ? # 添加一個(gè)節(jié)點(diǎn)，比如"A"為vertex

? ? ? ? vertex=queue.pop(0)

? ? ? ? # 隊(duì)列先進(jìn)先出，所以是pop（0）先出

? ? ? ? # nodes為"A"的臨近節(jié)點(diǎn)

? ? ? ? nodes=graph[vertex]

? ? ? ? #w為遍歷nodes的集合

? ? ? ?

? ? ? ? for w in nodes:

? ? ? ? ? ? ?

? ? ? ? ? ? if w not in seen:

? ? ? ? ? ? ? ? # 如果w不在seen中，w則加入集合和字典

? ? ? ? ? ? ? ? queue.append(w)

? ? ? ? ? ? ? ? seen. add(w)

? ? ? ? ? ? ? ? ? ? ?

? ? ? ? # 當(dāng)遍歷到F ? ? ? ?

? ? ? ? if vertex=="F":

? ? ? ? ? ? break ?

? ? ? ? print(vertex) ? ?

? ? ? ? relpace +=1

? ? print(relpace)

BFS(graph,"A")