廣度優先搜索bfs的python實作
廣度優先排序(BFS)可以一層一層地將圖向外搜索, 以得到離起點最近的元素, 這個“最近”在不同情況可以有不同的意義
實作方法
將下一層所有元素先儲存在同一個串列中, 當把本層元素的內容執行完后再執行.
還是以這張圖為例:
當從s開始廣度優先搜索時
第1層:[s]
第2層:[a,d]
第3層:[b,c]
第4層:[t]
依次執行這些串列就行了~
當然,這些串列可以合為一個處理, 即[s,a,d,b,c,t].這種情況通常用佇列來處理, 但不好得到深度
通過leetcode127來實作廣度優先搜索
代碼如下
def ladderLength(self, beginWord, endWord, wordList):
#beginWord = 'hit'
#endWord = 'cog'
#wordList = ['hot','dot','dog','lot','log','cog']
#得到圖
tree = {}
for i in wordList+[beginWord]:
length = len(i)
tree[i] = []
for j in wordList:
n=0
for u in range(length):
if j[u] == i[u]:
n+=1
if n+1 == length:
tree[i].append(j)
#already = {}
q = [beginWord]
flag = 0
while len(q):
flag += 1 #記錄層數
nq = [] #記錄下一層
for i in q:
if endWord == i:
return flag
for j in tree[i]:
#if not j in already: #避免重復, 節約時間, 但不會影響答案
#nq.append(j)
#already[j] =1
nq.append(j)
print(nq)
q = nq#改執行下一層
return []
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/230727.html
標籤：python