用Python實現廣度優先搜索
圖是一種善於處理關係型數據的數據結構，使用它可以很輕鬆地表示數據之間是如何關聯的
圖的實現形式有很多，最簡單的方法之一就是用散列表
背景
圖有兩種經典的遍歷方式：廣度優先搜索和深度優先搜索。兩者是相似的。
實現
1廣度優先搜索演算法需要用隊列來記錄後續要處理哪些頂點。
2該隊列最初只含有起步的頂點
3處理頂點。我們將其移出隊列，標為「已訪問」，並記為當前頂點
class Bfs:
def __init__(self,from_v,json):
# 最初的頂點
self.from_v = from_v
# 已訪問
self.visitList = [self.from_v]
# 需要一個隊列來記錄後續需要處理哪些頂點
self.vertexQ = queue.Queue()
self.json = json
核心步驟
(1) 找出當前頂點的所有鄰接點。如果有哪個是沒訪問過的，就把它標為「已訪問」，並且將它入隊。（儘管該頂點並未作為「當前頂點」被訪問過。）
(2) 如果當前頂點沒有未訪問的鄰接點，且隊列不為空，那就再從隊列中移出一個頂點作為當前頂點。
(3) 如果當前頂點沒有未訪問的鄰接點，且隊列里也沒有其他頂點，那麼演算法完成。
圖解
1首先A會作為頂點，A被訪問
2再去尋找A領接點B、D，依次加入隊列
3A所有領接點都訪問完成，開始訪問B的領接點
4知道隊列為空，演算法結束
程式碼展示
class Bfs:
def __init__(self,from_v,json):
# 最初的頂點
self.from_v = from_v
# 已訪問
self.visitList = [self.from_v]
# 需要一個隊列來記錄後續需要處理哪些頂點
self.vertexQ = queue.Queue()
self.json = json
def find_neighbor(self,currentVertex):
#尋找領接點
for neighbor in self.json[currentVertex]:
if neighbor not in self.visitList:
self.visitList.append(neighbor)
self.vertexQ.put(neighbor)
def checkTOV(self,currentVertex,to_v):
#檢測要尋找的值（to_v）是否已經在當前currentVertex中
return to_v in self.json[currentVertex]
def searchV(self,to_v):
reverseList = [self.from_v]
self.find_neighbor(self.from_v)
while not self.vertexQ.empty():
currentVertex = self.vertexQ.get()
reverseList.append(currentVertex)
tmp_path = Reverse(currentVertex,self.json).reverseOrder(reverseList,currentVertex)
if currentVertex == to_v:
print(tmp_path)
else:
self.find_neighbor(currentVertex)
if self.checkTOV(currentVertex,to_v):
tmp_path.append(to_v)
print(tmp_path)
此外我們額外寫了一個向上反向找尋路徑的工具類（主要程式碼寫好，不想動原來的結構了）
class Reverse:
def __init__(self,from_v,json):
self.from_v = from_v
self.json = json
def reverseOrder(self,reverseList:list,current_v):
indexReverseList = self.indexReverseList(reverseList)
res = [self.from_v]
tmp = current_v
while len(reverseList) > 0 :
# for _key in self.value2Key(current_v):
_key = self.value2Key(reverseList,tmp)
res.append(_key)
reverseList = reverseList[:indexReverseList[_key]]
tmp = _key
return res[::-1]
def value2Key(self,reverseList:list,current_v):
#根據值找json中的key
#這裡我們每次都只取離我們最近的一個key
indexReverseList = self.indexReverseList(reverseList)
tmp = -1
for _key, _value in self.json.items():
if current_v in _value and _key in reverseList and (index := indexReverseList[_key]) > tmp:
tmp = index
return reverseList[tmp]
def indexReverseList(self,reverseList:list):
return {value: index for index, value in enumerate(reverseList)}
運行結果
json = {"A":["B","D"],"B":["C"],"C":["E","D"],"D":["E"],"E":["B"]}
#從A出發找B
b=Bfs("A",json)
b.searchV("B")
