溫馨提示×
您好，登錄后才能下訂單哦！
點(diǎn)擊 登錄注冊 即表示同意《億速云用戶服務(wù)條款》
您好，登錄后才能下訂單哦！
本篇內(nèi)容主要講解“Python怎么實(shí)現(xiàn)圖的廣度和深度優(yōu)先路徑搜索算法”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實(shí)用性強(qiáng)。下面就讓小編來帶大家學(xué)習(xí)“Python怎么實(shí)現(xiàn)圖的廣度和深度優(yōu)先路徑搜索算法”吧!
圖是一種抽象數(shù)據(jù)結(jié)構(gòu)，本質(zhì)和樹結(jié)構(gòu)是一樣的。
圖與樹相比較，圖具有封閉性，可以把樹結(jié)構(gòu)看成是圖結(jié)構(gòu)的前生。在樹結(jié)構(gòu)中，如果把兄弟節(jié)點(diǎn)之間或子節(jié)點(diǎn)之間橫向連接，便構(gòu)建成一個圖。
樹適合描述從上向下的一對多的數(shù)據(jù)結(jié)構(gòu)，如公司的組織結(jié)構(gòu)。
圖適合描述更復(fù)雜的多對多數(shù)據(jù)結(jié)構(gòu)，如復(fù)雜的群體社交關(guān)系。
借助計(jì)算機(jī)解決現(xiàn)實(shí)世界中的問題時，除了要存儲現(xiàn)實(shí)世界中的信息，還需要正確地描述信息之間的關(guān)系。
如在開發(fā)地圖程序時，需要在計(jì)算機(jī)中正確模擬出城市與城市、或城市中各道路之間的關(guān)系圖。在此基礎(chǔ)上，才有可能通過算法計(jì)算出從一個城市到另一個城市、或從指定起點(diǎn)到目標(biāo)點(diǎn)間的最佳路徑。
類似的還有航班路線圖、火車線路圖、社交交系圖。
圖結(jié)構(gòu)能很好的對現(xiàn)實(shí)世界中如上這些信息之間的復(fù)雜關(guān)系進(jìn)行映射。以此可使用算法方便的計(jì)算出如航班線路中的最短路徑、如火車線路中的最佳中轉(zhuǎn)方案，如社交圈中誰與誰關(guān)系最好、婚姻網(wǎng)中誰與誰最般配……
頂點(diǎn)：頂點(diǎn)也稱為節(jié)點(diǎn)，可認(rèn)為圖就是頂點(diǎn)組成的集合。頂點(diǎn)本身是有數(shù)據(jù)含義的，所以頂點(diǎn)都會帶有附加信息，稱作"有效載荷"。
頂點(diǎn)可以是現(xiàn)實(shí)世界中的城市、地名、站名、人……
邊： 圖中的邊用來描述頂點(diǎn)之間的關(guān)系。邊可以有方向也可以沒有方向，有方向的邊又可分為單向邊和雙向邊。
如下圖（項(xiàng)點(diǎn)1）到（頂點(diǎn)2）之間的邊只有一方向（箭頭所示為方向），稱為單向邊。類似現(xiàn)實(shí)世界中的單向道。
（頂點(diǎn)1）到（頂點(diǎn)2）之間的邊有兩個方向（雙向箭頭），稱為雙向邊。 城市與城市之間的關(guān)系為雙向邊。
權(quán)重： 邊上可以附加值信息，附加的值稱為權(quán)重。有權(quán)重的邊用來描述一個頂點(diǎn)到另一個頂點(diǎn)的連接強(qiáng)度。
如現(xiàn)實(shí)生活中的地鐵路線中，權(quán)重可以描述兩個車站之間時間長度、公里數(shù)、票價……
邊描述的是頂點(diǎn)之間的關(guān)系，權(quán)重描述的是連接的差異性。
路徑：
先了解現(xiàn)實(shí)世界中路徑概念
如：從一個城市開車去另一個城市，就需要先確定好路徑。也就是 從出發(fā)地到目的地要經(jīng)過那些城市？要走多少里程？
可以說路徑是由邊連接的頂點(diǎn)組成的序列。因路徑不只一條，所以，從一個項(xiàng)點(diǎn)到另一個項(xiàng)點(diǎn)的路徑描述也不指一種。
在圖結(jié)構(gòu)中如何計(jì)算路徑？
無權(quán)重路徑的長度是路徑上的邊數(shù)。
有權(quán)重路徑的長度是路徑上的邊的權(quán)重之和。
如上圖從（頂點(diǎn)1）到（頂點(diǎn)3）的路徑長度為 8。
環(huán)： 從起點(diǎn)出發(fā)，最后又回到起點(diǎn)（終點(diǎn)也是起點(diǎn)）就會形成一個環(huán)，環(huán)是一種特殊的路徑。如上 (V1, V2, V3, V1) 就是一個環(huán)。
圖的類型：
綜上所述，圖可以分為如下幾類：
有向圖： 邊有方向的圖稱為有向圖。
無向圖： 邊沒有方向的圖稱為無向圖。
加權(quán)圖： 邊上面有權(quán)重信息的圖稱為加權(quán)圖。
無環(huán)圖： 沒有環(huán)的圖被稱為無環(huán)圖。
有向無環(huán)圖： 沒有環(huán)的有向圖，簡稱 DAG。
根據(jù)圖的特性，圖數(shù)據(jù)結(jié)構(gòu)中至少要包含兩類信息：
所有頂點(diǎn)構(gòu)成集合信息，這里用 V 表示（如地圖程序中，所有城市構(gòu)在頂點(diǎn)集合）。
所有邊構(gòu)成集合信息，這里用 E 表示（城市與城市之間的關(guān)系描述）。
如何描述邊？
邊用來表示項(xiàng)點(diǎn)之間的關(guān)系。所以一條邊可以包括 3 個元數(shù)據(jù)（起點(diǎn)，終點(diǎn)，權(quán)重）。當(dāng)然，權(quán)重是可以省略的，但一般研究圖時，都是指的加權(quán)圖。
如果用 G 表示圖，則 G = (V, E)。每一條邊可以用二元組 (fv, ev) 也可以使用 三元組 （fv,ev,w） 描述。
fv 表示起點(diǎn)，ev 表示終點(diǎn)。且 fv，ev 數(shù)據(jù)必須引用于 V 集合。
如上的圖結(jié)構(gòu)可以描述如下：
# 5 個頂點(diǎn)
V={A0,B1,C2,D3,E4}
# 7 條邊
E={ (A0,B1,3),(B1,C2,4),(C2,D3,6),(C2,E4,1),(D3,E4,2),(A0,D3,5),(E4,B1,7)}圖的抽象數(shù)據(jù)描述中至少要有的方法：
Graph ( ) ： 用來創(chuàng)建一個新圖。
add_vertex( vert )：向圖中添加一個新節(jié)點(diǎn)，參數(shù)應(yīng)該是一個節(jié)點(diǎn)類型的對象。
add_edge(fv，tv )：在 2 個項(xiàng)點(diǎn)之間建立起邊關(guān)系。
add_edge(fv，tv，w )：在 2 個項(xiàng)點(diǎn)之間建立起一條邊并指定連接權(quán)重。
find_vertex( key ): 根據(jù)關(guān)鍵字 key 在圖中查找頂點(diǎn)。
find_vertexs( )：查詢所有頂點(diǎn)信息。
find_path( fv,tv)：查找.從一個頂點(diǎn)到另一個頂點(diǎn)之間的路徑。
圖的存儲實(shí)現(xiàn)主流有 2 種：鄰接矩陣和鏈接表，本文主要介紹鄰接矩陣。
使用二維矩陣（數(shù)組）存儲頂點(diǎn)之間的關(guān)系。
如 graph[5][5] 可以存儲 5 個頂點(diǎn)的關(guān)系數(shù)據(jù)，行號和列號表示頂點(diǎn)，第 v 行的第 w 列交叉的單元格中的值表示從頂點(diǎn) v 到頂點(diǎn) w 的邊的權(quán)重，如 grap[2][3]=6 表示 C2 頂點(diǎn)和 D3 頂點(diǎn)的有連接（相鄰），權(quán)重為 6
相鄰矩陣的優(yōu)點(diǎn)就是簡單，可以清晰表示那些頂點(diǎn)是相連的。因不是每兩兩個頂點(diǎn)之間會有連接，會導(dǎo)致大量的空間閑置，稱這種矩陣為”稀疏“的。
只有當(dāng)每一個頂點(diǎn)和其它頂點(diǎn)都有關(guān)系時，矩陣才會填滿。所以，使用這種結(jié)構(gòu)存儲圖數(shù)據(jù)，對于關(guān)系不是很復(fù)雜的圖結(jié)構(gòu)而言，會產(chǎn)生大量的空間浪費(fèi)。
鄰接矩陣適合表示關(guān)系復(fù)雜的圖結(jié)構(gòu)，如互聯(lián)網(wǎng)上網(wǎng)頁之間的鏈接、社交圈中人與人之間的社會關(guān)系……
因頂點(diǎn)本身有數(shù)據(jù)含義，需要先定義頂點(diǎn)類型。
頂點(diǎn)類：
"""
節(jié)（頂）點(diǎn)類
"""
class Vertex:
def __init__(self, name, v_id=0):
# 頂點(diǎn)的編號
self.v_id = v_id
# 頂點(diǎn)的名稱
self.v_name = name
# 是否被訪問過:False 沒有 True:有
self.visited = False
# 自我顯示
def __str__(self):
return '[編號為 {0}，名稱為 {1} ] 的頂點(diǎn)'.format(self.v_id, self.v_name)頂點(diǎn)類中 v_id 和 v_name 很好理解。為什么要添加一個 visited？
這個變量用來記錄頂點(diǎn)在路徑搜索過程中是否已經(jīng)被搜索過，避免重復(fù)搜索計(jì)算。
圖類：圖類的方法較多，這里逐方法介紹。
初始化方法
class Graph: """ nums:相鄰矩陣的大小 """ def __init__(self, nums): # 一維列表，保存節(jié)點(diǎn)，最多只能有 nums 個節(jié)點(diǎn) self.vert_list = [] # 二維列表，存儲頂點(diǎn)及頂點(diǎn)間的關(guān)系(權(quán)重) # 初始權(quán)重為 0 ，表示節(jié)點(diǎn)與節(jié)點(diǎn)之間還沒有建立起關(guān)系 self.matrix = [[0] * nums for _ in range(nums)] # 頂點(diǎn)個數(shù) self.v_nums = 0 # 使用隊(duì)列模擬隊(duì)列或棧，用于廣度、深度優(yōu)先搜索算法 self.queue_stack = [] # 保存搜索到的路徑 self.searchPath = [] # 暫省略……
初始化方法用來初始化圖中的數(shù)據(jù)類型：
一維列表 vert_list 保存所有頂點(diǎn)數(shù)據(jù)。
二維列表 matrix 保存頂點(diǎn)與頂點(diǎn)之間的關(guān)系數(shù)據(jù)。
queue_stack 使用列表模擬隊(duì)列或棧，用于后續(xù)的廣度搜索和深度搜索。
怎么使用列表模擬隊(duì)列或棧？
列表有 append()、pop() 2 個很價值的方法。
append() 用來向列表中添加數(shù)據(jù)，且每次都是從列表最后面添加。
pop() 默認(rèn)從列表最后面刪除且彈出數(shù)據(jù)， pop(參數(shù)) 可以提供索引值用來從指定位置刪除且彈出數(shù)據(jù)。
使用 append() 和 pop() 方法就能模擬棧，從同一個地方進(jìn)出數(shù)據(jù)。
使用 append() 和 pop(0) 方法就能模擬隊(duì)列，從后面添加數(shù)據(jù)，從最前面獲取數(shù)據(jù)
searchPath ： 用來保存使用廣度或深度優(yōu)先路徑搜索中的結(jié)果。
添加新節(jié)（頂）點(diǎn)方法：
""" 添加新頂點(diǎn) """ def add_vertex(self, vert): if vert in self.vert_list: # 已經(jīng)存在 return if self.v_nums >= len(self.matrix): # 超過相鄰矩陣所能存儲的節(jié)點(diǎn)上限 return # 頂點(diǎn)的編號內(nèi)部生成 vert.v_id = self.v_nums self.vert_list.append(vert) # 數(shù)量增一 self.v_nums += 1
上述方法注意一點(diǎn)，節(jié)點(diǎn)的編號由圖內(nèi)部邏輯提供，便于節(jié)點(diǎn)編號順序的統(tǒng)一。
添加邊方法
此方法是鄰接矩陣表示法的核心邏輯。
''' 添加節(jié)點(diǎn)與節(jié)點(diǎn)之間的邊， 如果是無權(quán)重圖，統(tǒng)一設(shè)定為 1 ''' def add_edge(self, from_v, to_v): # 如果節(jié)點(diǎn)不存在 if from_v not in self.vert_list: self.add_vertex(from_v) if to_v not in self.vert_list: self.add_vertex(to_v) # from_v 節(jié)點(diǎn)的編號為行號，to_v 節(jié)點(diǎn)的編號為列號 self.matrix[from_v.v_id][to_v.v_id] = 1 ''' 添加有權(quán)重的邊 ''' def add_edge(self, from_v, to_v, weight): # 如果節(jié)點(diǎn)不存在 if from_v not in self.vert_list: self.add_vertex(from_v) if to_v not in self.vert_list: self.add_vertex(to_v) # from_v 節(jié)點(diǎn)的編號為行號，to_v 節(jié)點(diǎn)的編號為列號 self.matrix[from_v.v_id][to_v.v_id] = weight
添加邊信息的方法有 2 個，一個用來添加無權(quán)重邊，一個用來添加有權(quán)重的邊。
查找某節(jié)點(diǎn)
使用線性查找法從節(jié)點(diǎn)集合中查找某一個節(jié)點(diǎn)。
''' 根據(jù)節(jié)點(diǎn)編號返回節(jié)點(diǎn) ''' def find_vertex(self, v_id): if v_id >= 0 or v_id <= self.v_nums: # 節(jié)點(diǎn)編號必須存在 return [tmp_v for tmp_v in self.vert_list if tmp_v.v_id == v_id][0]
查詢所有節(jié)點(diǎn)
''' 輸出所有頂點(diǎn)信息 ''' def find_only_vertexes(self): for tmp_v in self.vert_list: print(tmp_v)
此方法僅為了查詢方便。
查詢節(jié)點(diǎn)之間的關(guān)系
''' 迭代節(jié)點(diǎn)與節(jié)點(diǎn)之間的關(guān)系（邊） ''' def find_vertexes(self): for tmp_v in self.vert_list: edges = self.matrix[tmp_v.v_id] for col in range(len(edges)): w = edges[col] if w != 0: print(tmp_v, '和', self.vert_list[col], '的權(quán)重為：', w)
測試代碼：
if __name__ == "__main__":
# 初始化圖對象
g = Graph(5)
# 添加頂點(diǎn)
for _ in range(len(g.matrix)):
v_name = input("頂點(diǎn)的名稱（ q 為退出）：")
if v_name == 'q':
break
v = Vertex(v_name)
g.add_vertex(v)
# 節(jié)點(diǎn)之間的關(guān)系
infos = [(0, 1, 3), (0, 3, 5), (1, 2, 4), (2, 3, 6), (2, 4, 1), (3, 4, 2), (4, 1, 7)]
for i in infos:
v = g.find_vertex(i[0])
v1 = g.find_vertex(i[1])
g.add_edge(v, v1, i[2])
# 輸出頂點(diǎn)及邊a
print("-----------頂點(diǎn)與頂點(diǎn)關(guān)系--------------")
g.find_vertexes()
'''
輸出結(jié)果：
頂點(diǎn)的名稱（ q 為退出）：A
頂點(diǎn)的名稱（ q 為退出）：B
頂點(diǎn)的名稱（ q 為退出）：C
頂點(diǎn)的名稱（ q 為退出）：D
頂點(diǎn)的名稱（ q 為退出）：E
[編號為 0，名稱為 A ] 的頂點(diǎn) 和 [編號為 1，名稱為 B ] 的頂點(diǎn) 的權(quán)重為： 3
[編號為 0，名稱為 A ] 的頂點(diǎn) 和 [編號為 3，名稱為 D ] 的頂點(diǎn) 的權(quán)重為： 5
[編號為 1，名稱為 B ] 的頂點(diǎn) 和 [編號為 2，名稱為 C ] 的頂點(diǎn) 的權(quán)重為： 4
[編號為 2，名稱為 C ] 的頂點(diǎn) 和 [編號為 3，名稱為 D ] 的頂點(diǎn) 的權(quán)重為： 6
[編號為 2，名稱為 C ] 的頂點(diǎn) 和 [編號為 4，名稱為 E ] 的頂點(diǎn) 的權(quán)重為： 1
[編號為 3，名稱為 D ] 的頂點(diǎn) 和 [編號為 4，名稱為 E ] 的頂點(diǎn) 的權(quán)重為： 2
[編號為 4，名稱為 E ] 的頂點(diǎn) 和 [編號為 1，名稱為 B ] 的頂點(diǎn) 的權(quán)重為： 7
'''在圖中經(jīng)常做的操作，就是查找從一個頂點(diǎn)到另一個頂點(diǎn)的路徑。如怎么查找到 A0 到 E4 之間的路徑長度：
從人的直觀思維角度查找一下，可以找到如下路徑：
{A0，B1，C2，E4}路徑長度為 8。
{A0，D3，E4} 路徑長度為 7。
{A0，B1，C2，D3，E4} 路徑長度為 15。
人的思維是知識性、直觀性思維，在路徑查找時不存在所謂的嘗試或碰壁問題。而計(jì)算機(jī)是試探性思維，就會出現(xiàn)這條路不通，再找另一條路的現(xiàn)象。
所以路徑算法中常常會以錯誤為代價，在查找過程中會走一些彎路。常用的路徑搜索算法有 2 種：
廣度優(yōu)先搜索
深度優(yōu)先搜索
先看一下廣度優(yōu)先搜索的示意圖：
廣度優(yōu)先搜索的基本思路：
確定出發(fā)點(diǎn)，本案例是 A0 頂點(diǎn)。
以出發(fā)點(diǎn)相鄰的頂點(diǎn)為候選點(diǎn)，并存儲至隊(duì)列。
從隊(duì)列中每拿出一個頂點(diǎn)后，再把與此頂點(diǎn)相鄰的其它頂點(diǎn)做為候選點(diǎn)存儲于隊(duì)列。
不停重復(fù)上述過程，至到找到目標(biāo)頂點(diǎn)或隊(duì)列為空。
使用廣度搜索到的路徑與候選節(jié)點(diǎn)進(jìn)入隊(duì)列的先后順序有關(guān)系。如第 1 步確定候選節(jié)點(diǎn)時 B1 和 D3 誰先進(jìn)入隊(duì)列，對于后面的查找也會有影響。
上圖使用廣度搜索可找到 A0~E4 路徑是：
{A0，B1，D3，C2，E4}
其實(shí) {A0，B1，C2，E4} 也是一條有效路徑，有可能搜索不出來，這里因?yàn)樗阉鞯?nbsp;B1 后不會馬上搜索 C2，因?yàn)?nbsp;B3 先于 C2 進(jìn)入，廣度優(yōu)先搜索算法只能保證找到路徑，而不能保存找到最佳路徑。
編碼實(shí)現(xiàn)廣度優(yōu)先搜索：
廣度優(yōu)先搜索需要借助隊(duì)列臨時存儲選節(jié)點(diǎn)，本文使用列表模擬隊(duì)列。
在圖類中實(shí)現(xiàn)廣度優(yōu)先搜索算法的方法：
class Graph():
# 省略其它代碼
'''
廣度優(yōu)先搜索算法
'''
def bfs(self, from_v, to_v):
# 查找與 fv 相鄰的節(jié)點(diǎn)
self.find_neighbor(from_v)
# 臨時路徑
lst_path = [from_v]
# 重復(fù)條件：隊(duì)列不為空
while len(self.queue_stack) != 0:
# 從隊(duì)列中一個節(jié)點(diǎn)（模擬隊(duì)列）
tmp_v = self.queue_stack.pop(0)
# 添加到列表中
lst_path.append(tmp_v)
# 是不是目標(biāo)節(jié)點(diǎn)
if tmp_v.v_id == to_v.v_id:
self.searchPath.append(lst_path)
print('找到一條路徑', [v_.v_id for v_ in lst_path])
lst_path.pop()
else:
self.find_neighbor(tmp_v)
'''
查找某一節(jié)點(diǎn)的相鄰節(jié)點(diǎn)，并添加到隊(duì)列（棧）中
'''
def find_neighbor(self, find_v):
if find_v.visited:
return
find_v.visited = True
# 找到保存 find_v 節(jié)點(diǎn)相鄰節(jié)點(diǎn)的列表
lst = self.matrix[find_v.v_id]
for idx in range(len(lst)):
if lst[idx] != 0:
# 權(quán)重不為 0 ，可判斷相鄰
self.queue_stack.append(self.vert_list[idx])廣度優(yōu)先搜索過程中，需要隨時獲取與當(dāng)前節(jié)點(diǎn)相鄰的節(jié)點(diǎn)，find_neighbor() 方法的作用就是用來把當(dāng)前節(jié)點(diǎn)的相鄰節(jié)點(diǎn)壓入隊(duì)列中。
測試廣度優(yōu)先搜索算法：
if __name__ == "__main__":
# 初始化圖對象
g = Graph(5)
# 添加頂點(diǎn)
for _ in range(len(g.matrix)):
v_name = input("頂點(diǎn)的名稱（ q 為退出）：")
if v_name == 'q':
break
v = Vertex(v_name)
g.add_vertex(v)
# 節(jié)點(diǎn)之間的關(guān)系
infos = [(0, 1, 3), (0, 3, 5), (1, 2, 4), (2, 3, 6), (2, 4, 1), (3, 4, 2), (4, 1, 7)]
for i in infos:
v = g.find_vertex(i[0])
v1 = g.find_vertex(i[1])
g.add_edge(v, v1, i[2])
print("----------- 廣度優(yōu)先路徑搜索--------------")
f_v = g.find_vertex(0)
t_v = g.find_vertex(4)
g.bfs(f_v,t_v)
'''
輸出結(jié)果
頂點(diǎn)的名稱（ q 為退出）：A
頂點(diǎn)的名稱（ q 為退出）：B
頂點(diǎn)的名稱（ q 為退出）：C
頂點(diǎn)的名稱（ q 為退出）：D
頂點(diǎn)的名稱（ q 為退出）：E
----------- 廣度優(yōu)先路徑搜索--------------
找到一條路徑 [0, 1, 3, 2, 4]
找到一條路徑 [0, 1, 3, 2, 3, 4]
'''使用遞歸實(shí)現(xiàn)廣度優(yōu)先搜索算法：
''' 遞歸方式實(shí)現(xiàn)廣度搜索 ''' def bfs_dg(self, from_v, to_v): self.searchPath.append(from_v) if from_v.v_id != to_v.v_id: self.find_neighbor(from_v) if len(self.queue_stack) != 0: self.bfs_dg(self.queue_stack.pop(0), to_v)
先看一下深度優(yōu)先算法的示意圖。
深度優(yōu)先搜索算法與廣度優(yōu)先搜索算法不同之處：候選節(jié)點(diǎn)是放在棧中的。因棧是先進(jìn)后出，所以，搜索到的節(jié)點(diǎn)順序不一樣。
使用循環(huán)實(shí)現(xiàn)深度優(yōu)先搜索算法：
深度優(yōu)先搜索算法需要用到棧，本文使用列表模擬。
'''
深度優(yōu)先搜索算法
使用棧存儲下一個需要查找的節(jié)點(diǎn)
'''
def dfs(self, from_v, to_v):
# 查找與 from_v 相鄰的節(jié)點(diǎn)
self.find_neighbor(from_v)
# 臨時路徑
lst_path = [from_v]
# 重復(fù)條件：棧不為空
while len(self.queue_stack) != 0:
# 從棧中取一個節(jié)點(diǎn)（模擬棧）
tmp_v = self.queue_stack.pop()
# 添加到列表中
lst_path.append(tmp_v)
# 是不是目標(biāo)節(jié)點(diǎn)
if tmp_v.v_id == to_v.v_id:
self.searchPath.append(lst_path)
print('找到一條路徑:', [v_.v_id for v_ in lst_path])
lst_path.pop()
else:
self.find_neighbor(tmp_v)測試：
if __name__ == "__main__":
# 初始化圖對象
g = Graph(5)
# 添加頂點(diǎn)
for _ in range(len(g.matrix)):
v_name = input("頂點(diǎn)的名稱（ q 為退出）：")
if v_name == 'q':
break
v = Vertex(v_name)
g.add_vertex(v)
# 節(jié)點(diǎn)之間的關(guān)系
infos = [(0, 1, 3), (0, 3, 5), (1, 2, 4), (2, 3, 6), (2, 4, 1), (3, 4, 2), (4, 1, 7)]
for i in infos:
v = g.find_vertex(i[0])
v1 = g.find_vertex(i[1])
g.add_edge(v, v1, i[2])
# 輸出頂點(diǎn)及邊a
print("-----------頂點(diǎn)與頂點(diǎn)關(guān)系--------------")
g.find_vertexes()
print("----------- 深度優(yōu)先路徑搜索--------------")
f_v = g.find_vertex(0)
t_v = g.find_vertex(4)
g.dfs(f_v, t_v)
'''
輸出結(jié)果
頂點(diǎn)的名稱（ q 為退出）：A
頂點(diǎn)的名稱（ q 為退出）：B
頂點(diǎn)的名稱（ q 為退出）：C
頂點(diǎn)的名稱（ q 為退出）：D
頂點(diǎn)的名稱（ q 為退出）：E
-----------頂點(diǎn)與頂點(diǎn)關(guān)系--------------
[編號為 0，名稱為 A ] 的頂點(diǎn) 和 [編號為 1，名稱為 B ] 的頂點(diǎn) 的權(quán)重為： 3
[編號為 0，名稱為 A ] 的頂點(diǎn) 和 [編號為 3，名稱為 D ] 的頂點(diǎn) 的權(quán)重為： 5
[編號為 1，名稱為 B ] 的頂點(diǎn) 和 [編號為 2，名稱為 C ] 的頂點(diǎn) 的權(quán)重為： 4
[編號為 2，名稱為 C ] 的頂點(diǎn) 和 [編號為 3，名稱為 D ] 的頂點(diǎn) 的權(quán)重為： 6
[編號為 2，名稱為 C ] 的頂點(diǎn) 和 [編號為 4，名稱為 E ] 的頂點(diǎn) 的權(quán)重為： 1
[編號為 3，名稱為 D ] 的頂點(diǎn) 和 [編號為 4，名稱為 E ] 的頂點(diǎn) 的權(quán)重為： 2
[編號為 4，名稱為 E ] 的頂點(diǎn) 和 [編號為 1，名稱為 B ] 的頂點(diǎn) 的權(quán)重為： 7
----------- 深度優(yōu)先路徑搜索--------------
找到一條路徑: [0, 3, 4]
找到一條路徑: [0, 3, 1, 2, 4]
'''使用遞歸實(shí)現(xiàn)深度優(yōu)先搜索算法：
''' 遞歸實(shí)現(xiàn)深度搜索算法 ''' def def_dg(self, from_v, to_v): self.searchPath.append(from_v) if from_v.v_id != to_v.v_id: # 查找與 from_v 節(jié)點(diǎn)相連的子節(jié)點(diǎn) lst = self.find_neighbor_(from_v) if lst is not None: for tmp_v in lst[::-1]: self.def_dg(tmp_v, to_v) """ 查找某一節(jié)點(diǎn)的相鄰節(jié)點(diǎn)，以列表方式返回 """ def find_neighbor_(self, find_v): if find_v.visited: return find_v.visited = True # 查找與 find_v 節(jié)點(diǎn)相鄰的節(jié)點(diǎn) lst = self.matrix[find_v.v_id] return [self.vert_list[idx] for idx in range(len(lst)) if lst[idx] != 0]
遞歸實(shí)現(xiàn)時，不需要使用全局棧，只需要獲到當(dāng)前節(jié)點(diǎn)的相鄰節(jié)點(diǎn)便可。
到此，相信大家對“Python怎么實(shí)現(xiàn)圖的廣度和深度優(yōu)先路徑搜索算法”有了更深的了解，不妨來實(shí)際操作一番吧！這里是億速云網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！
免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點(diǎn)不代表本網(wǎng)站立場，如果涉及侵權(quán)請聯(lián)系站長郵箱：is@yisu.com進(jìn)行舉報(bào)，并提供相關(guān)證據(jù)，一經(jīng)查實(shí)，將立刻刪除涉嫌侵權(quán)內(nèi)容。
億速云公眾號
手機(jī)網(wǎng)站二維碼