用Python實現(xiàn)廣度優(yōu)先搜索
發(fā)布日期：2022/9/18 17:40:39 瀏覽量：
圖是一種善于處理關(guān)系型數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)，使用它可以很輕松地表示數(shù)據(jù)之間是如何關(guān)聯(lián)的
圖的實現(xiàn)形式有很多，最簡單的方法之一就是用散列表
背景
圖有兩種經(jīng)典的遍歷方式：廣度優(yōu)先搜索和深度優(yōu)先搜索。兩者是相似的。
實現(xiàn)
1廣度優(yōu)先搜索算法需要用隊列來記錄后續(xù)要處理哪些頂點。
2該隊列最初只含有起步的頂點
3處理頂點。我們將其移出隊列，標為“已訪問”，并記為當前頂點
|
1
2
3
4
5
6
7
8
9
|
class Bfs:
def __init__(self,from_v,json):
# 最初的頂點
self.from_v = from_v
# 已訪問
self.visitList = [self.from_v]
# 需要一個隊列來記錄后續(xù)需要處理哪些頂點
self.vertexQ = queue.Queue()
self.json = json
|
核心步驟
(1) 找出當前頂點的所有鄰接點。如果有哪個是沒訪問過的，就把它標為“已訪問”，并且將它入隊。（盡管該頂點并未作為“當前頂點”被訪問過。）
(2) 如果當前頂點沒有未訪問的鄰接點，且隊列不為空，那就再從隊列中移出一個頂點作為當前頂點。
(3) 如果當前頂點沒有未訪問的鄰接點，且隊列里也沒有其他頂點，那么算法完成。
圖解
1首先A會作為頂點，A被訪問
2再去尋找A領(lǐng)接點B、D，依次加入隊列
3A所有領(lǐng)接點都訪問完成，開始訪問B的領(lǐng)接點
4知道隊列為空，算法結(jié)束
代碼展示
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
class Bfs:
def __init__(self,from_v,json):
# 最初的頂點
self.from_v = from_v
# 已訪問
self.visitList = [self.from_v]
# 需要一個隊列來記錄后續(xù)需要處理哪些頂點
self.vertexQ = queue.Queue()
self.json = json
def find_neighbor(self,currentVertex):
#尋找領(lǐng)接點
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）是否已經(jīng)在當前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)
|
此外我們額外寫了一個向上反向找尋路徑的工具類（主要代碼寫好，不想動原來的結(jié)構(gòu)了）
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
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):
#根據(jù)值找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)}
|
運行結(jié)果
|
1
2
3
|
json = {"A":["B","D"],"B":["C"],"C":["E","D"],"D":["E"],"E":["B"]}<br>#從A出發(fā)找B
b=Bfs("A",json)
b.searchV("B")
|
作者： yetangjian
出處： https://www.cnblogs.com/yetangjian/p/16653129.html
業(yè)務(wù)實施流程 馬上咨詢： 如果您有業(yè)務(wù)方面的問題或者需求，歡迎您咨詢！我們帶來的不僅僅是技術(shù)，還有行業(yè)經(jīng)驗積累。
QQ: 39764417/308460098 Phone: 13 9800 1 9844 / 135 6887 9550 聯(lián)系人：石先生/雷先生