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)系。
1. 圖理論
借助計(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)中誰與誰最般配……
1.1 圖的概念
頂點(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。
1.2 定義圖
根據(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)}
1.3 圖的抽象數(shù)據(jù)結(jié)構(gòu)
圖的抽象數(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)之間的路徑。
2. 圖的存儲實(shí)現(xiàn)
圖的存儲實(shí)現(xiàn)主流有 2 種：鄰接矩陣和鏈接表，本文主要介紹鄰接矩陣。
2.1 鄰接矩陣
使用二維矩陣（數(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)系……
2.2 編碼實(shí)現(xià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
'''
3. 搜索路徑
在圖中經(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)先搜索
3.1 廣度優(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)
3.2 深度優(yōu)先搜索算法
先看一下深度優(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)便可。
4. 總結(jié)
圖是一種很重要的數(shù)據(jù)結(jié)構(gòu)，因這個世界中萬事萬物之間的關(guān)系并不是簡單的你和我，我和你的關(guān)系，本質(zhì)都是錯綜復(fù)雜的。
圖能準(zhǔn)確的映射現(xiàn)實(shí)世界的這種錯綜復(fù)雜關(guān)系，為計(jì)算機(jī)處理現(xiàn)實(shí)世界的問題提供了可能，也拓展了計(jì)算機(jī)在現(xiàn)實(shí)世界的應(yīng)用領(lǐng)域。
到此這篇關(guān)于Python實(shí)現(xiàn)圖的廣度和深度優(yōu)先路徑搜索算法的文章就介紹到這了,更多相關(guān)Python圖 路徑搜索內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
今天向大家介紹如何搭建Python開發(fā)環(huán)境, Python可應(yīng)用于多平臺包括 Linux 和 Mac OS X,文中有非常詳細(xì)的圖文介紹,需要的朋友可以參考下2021-05-05
python 非線性規(guī)劃方式(scipy.optimize.minimize)
今天小編就為大家分享一篇python 非線性規(guī)劃方式(scipy.optimize.minimize)，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-02-02
Python中保存文件是一項(xiàng)非?；镜娜蝿?wù),它允許我們將程序輸出保存到磁盤上,以便以后使用或與他人共享,這篇文章主要給大家介紹了關(guān)于Python中文件讀取與保存的相關(guān)資料,需要的朋友可以參考下2024-04-04
本文主要介紹了OpenCV 繪制同心圓的示例代碼，文中通過示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-08-08
這篇文章主要介紹了Python flask與fastapi性能測試方法，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)吧2022-12-12
我們在日常辦公時,經(jīng)常需要將圖片進(jìn)行修改尺寸,本文將使用python和PyQt5開發(fā)一個方便圖片修改尺寸工具,感興趣的小伙伴可以了解一下2025-03-03
本文主要介紹了離線部署Python環(huán)境的全過程,包括前置工作、部署Python、測試Python、配置環(huán)境和驗(yàn)證Python五個步驟,為讀者提供了詳細(xì)的操作指南,希望能對需要離線部署Python環(huán)境的讀者提供幫助2024-10-10
這篇文章主要介紹了vscode配置anaconda3的方法步驟，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-08-08
Python實(shí)現(xiàn)壓縮與解壓gzip大文件的方法
這篇文章主要介紹了Python實(shí)現(xiàn)壓縮與解壓gzip大文件的方法,分析了Python針對壓縮成gzip文件及解壓gzip文件的方法,并給出了相應(yīng)的封裝類,需要的朋友可以參考下2016-09-09
這篇文章主要介紹了python實(shí)用代碼片段收集貼,本文收集了如獲取一個類的所有子類、計(jì)算運(yùn)行時間、SQLAlchemy簡單使用、實(shí)現(xiàn)類似Java或C中的枚舉等實(shí)用功能代碼,需要的朋友可以參考下2015-06-06