Python 图_系列之基于邻接矩阵实现广度、深度优先路径搜索算法
圖是一種抽象數(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)建成一個(gè)圖。
樹適合描述從上向下的一對(duì)多的數(shù)據(jù)結(jié)構(gòu)，如公司的組織結(jié)構(gòu)。
圖適合描述更復(fù)雜的多對(duì)多數(shù)據(jù)結(jié)構(gòu)，如復(fù)雜的群體社交關(guān)系。
1. 圖理論
借助計(jì)算機(jī)解決現(xiàn)實(shí)世界中的問題時(shí)，除了要存儲(chǔ)現(xiàn)實(shí)世界中的信息，還需要正確地描述信息之間的關(guān)系。
如在開發(fā)地圖程序時(shí)，需要在計(jì)算機(jī)中正確模擬出城市與城市、或城市中各道路之間的關(guān)系圖。在此基礎(chǔ)上，才有可能通過算法計(jì)算出從一個(gè)城市到另一個(gè)城市、或從指定起點(diǎn)到目標(biāo)點(diǎn)間的最佳路徑。
類似的還有航班路線圖、火車線路圖、社交交系圖。
圖結(jié)構(gòu)能很好的對(duì)現(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)都會(huì)帶有附加信息，稱作"有效載荷"。
頂點(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）之間的邊有兩個(gè)方向（雙向箭頭），稱為雙向邊。 城市與城市之間的關(guān)系為雙向邊。
權(quán)重： 邊上可以附加值信息，附加的值稱為權(quán)重。有權(quán)重的邊用來描述一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的連接強(qiáng)度。
如現(xiàn)實(shí)生活中的地鐵路線中，權(quán)重可以描述兩個(gè)車站之間時(shí)間長度、公里數(shù)、票價(jià)……
邊描述的是頂點(diǎn)之間的關(guān)系，權(quán)重描述的是連接的差異性。
路徑：
先了解現(xiàn)實(shí)世界中路徑概念
如：從一個(gè)城市開車去另一個(gè)城市，就需要先確定好路徑。也就是 從出發(fā)地到目的地要經(jīng)過那些城市？要走多少里程？
可以說路徑是由邊連接的頂點(diǎn)組成的序列。因路徑不只一條，所以，從一個(gè)項(xiàng)點(diǎn)到另一個(gè)項(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ì)形成一個(gè)環(huán)，環(huán)是一種特殊的路徑。如上 (V1, V2, V3, V1) 就是一個(gè)環(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 個(gè)元數(shù)據(jù)（起點(diǎn)，終點(diǎn)，權(quán)重）。當(dāng)然，權(quán)重是可以省略的，但一般研究圖時(shí)，都是指的加權(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 個(gè)頂點(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)建一個(gè)新圖。
-
add_vertex( vert )：向圖中添加一個(gè)新節(jié)點(diǎn)，參數(shù)應(yīng)該是一個(gè)節(jié)點(diǎn)類型的對(duì)象。
-
add_edge(fv，tv )：在 2 個(gè)項(xiàng)點(diǎn)之間建立起邊關(guān)系。
-
add_edge(fv，tv，w )：在 2 個(gè)項(xiàng)點(diǎn)之間建立起一條邊并指定連接權(quán)重。
-
find_vertex( key ) : 根據(jù)關(guān)鍵字 key 在圖中查找頂點(diǎn)。
-
find_vertexs( )：查詢所有頂點(diǎn)信息。
-
find_path( fv,tv)：查找.從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)之間的路徑。
2. 圖的存儲(chǔ)實(shí)現(xiàn)
圖的存儲(chǔ)實(shí)現(xiàn)主流有 2 種：鄰接矩陣和鏈接表，本文主要介紹鄰接矩陣。
2.1 鄰接矩陣
使用二維矩陣（數(shù)組）存儲(chǔ)頂點(diǎn)之間的關(guān)系。
如 graph[5][5] 可以存儲(chǔ) 5 個(gè)頂點(diǎn)的關(guān)系數(shù)據(jù)，行號(hào)和列號(hào)表示頂點(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)是相連的。因不是每兩兩個(gè)頂點(diǎn)之間會(huì)有連接，會(huì)導(dǎo)致大量的空間閑置，稱這種矩陣為”稀疏“的。
只有當(dāng)每一個(gè)頂點(diǎn)和其它頂點(diǎn)都有關(guān)系時(shí)，矩陣才會(huì)填滿。所以，使用這種結(jié)構(gòu)存儲(chǔ)圖數(shù)據(jù)，對(duì)于關(guān)系不是很復(fù)雜的圖結(jié)構(gòu)而言，會(huì)產(chǎn)生大量的空間浪費(fèi)。
鄰接矩陣適合表示關(guān)系復(fù)雜的圖結(jié)構(gòu)，如互聯(lián)網(wǎng)上網(wǎng)頁之間的鏈接、社交圈中人與人之間的社會(huì)關(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)的編號(hào)self.v_id = v_id# 頂點(diǎn)的名稱self.v_name = name# 是否被訪問過:False 沒有 True:有self.visited = False# 自我顯示def __str__(self):return '[編號(hào)為 {0}，名稱為 {1} ] 的頂點(diǎn)'.format(self.v_id, self.v_name)頂點(diǎn)類中 v_id 和 v_name 很好理解。為什么要添加一個(gè) visited？
這個(gè)變量用來記錄頂點(diǎn)在路徑搜索過程中是否已經(jīng)被搜索過，避免重復(fù)搜索計(jì)算。
**圖類：**圖類的方法較多，這里逐方法介紹。
初始化方法用來初始化圖中的數(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 個(gè)很價(jià)值的方法。
append() 用來向列表中添加數(shù)據(jù)，且每次都是從列表最后面添加。
pop() 默認(rèn)從列表最后面刪除且彈出數(shù)據(jù)， pop(參數(shù)) 可以提供索引值用來從指定位置刪除且彈出數(shù)據(jù)。
使用 append() 和 pop() 方法就能模擬棧，從同一個(gè)地方進(jìn)出數(shù)據(jù)。
使用 append() 和 pop(0) 方法就能模擬隊(duì)列，從后面添加數(shù)據(jù)，從最前面獲取數(shù)據(jù)
-
searchPath ： 用來保存使用廣度或深度優(yōu)先路徑搜索中的結(jié)果。
上述方法注意一點(diǎn)，節(jié)點(diǎn)的編號(hào)由圖內(nèi)部邏輯提供，便于節(jié)點(diǎn)編號(hào)順序的統(tǒng)一。
添加邊方法
此方法是鄰接矩陣表示法的核心邏輯。
添加邊信息的方法有 2 個(gè)，一個(gè)用來添加無權(quán)重邊，一個(gè)用來添加有權(quán)重的邊。
查找某節(jié)點(diǎn)
使用線性查找法從節(jié)點(diǎn)集合中查找某一個(gè)節(jié)點(diǎn)。
此方法僅為了查詢方便。
3. 搜索路徑
在圖中經(jīng)常做的操作，就是查找從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的路徑。如怎么查找到 A0 到 E4 之間的路徑長度：
從人的直觀思維角度查找一下，可以找到如下路徑：
- {A0，B1，C2，E4}路徑長度為 8。
- {A0，D3，E4} 路徑長度為 7。
- {A0，B1，C2，D3，E4} 路徑長度為 15。
人的思維是知識(shí)性、直觀性思維，在路徑查找時(shí)不存在所謂的嘗試或碰壁問題。而計(jì)算機(jī)是試探性思維，就會(huì)出現(xiàn)這條路不通，再找另一條路的現(xiàn)象。
所以路徑算法中常常會(huì)以錯(cuò)誤為代價(jià)，在查找過程中會(huì)走一些彎路。常用的路徑搜索算法有 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)，并存儲(chǔ)至隊(duì)列。
- 從隊(duì)列中每拿出一個(gè)頂點(diǎn)后，再把與此頂點(diǎn)相鄰的其它頂點(diǎn)做為候選點(diǎn)存儲(chǔ)于隊(duì)列。
- 不停重復(fù)上述過程，至到找到目標(biāo)頂點(diǎn)或隊(duì)列為空。
使用廣度搜索到的路徑與候選節(jié)點(diǎn)進(jìn)入隊(duì)列的先后順序有關(guān)系。如第 1 步確定候選節(jié)點(diǎn)時(shí) B1 和 D3 誰先進(jìn)入隊(duì)列，對(duì)于后面的查找也會(huì)有影響。
上圖使用廣度搜索可找到 A0~E4 路徑是：
- {A0，B1，D3，C2，E4}
其實(shí) {A0，B1，C2，E4} 也是一條有效路徑，有可能搜索不出來，這里因?yàn)樗阉鞯?B1 后不會(huì)馬上搜索 C2，因?yàn)?B3 先于 C2 進(jìn)入，廣度優(yōu)先搜索算法只能保證找到路徑，而不能保存找到最佳路徑。
編碼實(shí)現(xiàn)廣度優(yōu)先搜索：
廣度優(yōu)先搜索需要借助隊(duì)列臨時(shí)存儲(chǔ)選節(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)# 臨時(shí)路徑lst_path = [from_v]# 重復(fù)條件：隊(duì)列不為空while len(self.queue_stack) != 0:# 從隊(duì)列中一個(gè)節(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:returnfind_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)先搜索過程中，需要隨時(shí)獲取與當(dāng)前節(jié)點(diǎn)相鄰的節(jié)點(diǎn)，find_neighbor() 方法的作用就是用來把當(dāng)前節(jié)點(diǎn)的相鄰節(jié)點(diǎn)壓入隊(duì)列中。
測試廣度優(yōu)先搜索算法：
if __name__ == "__main__":# 初始化圖對(duì)象g = Graph(5)# 添加頂點(diǎn)for _ in range(len(g.matrix)):v_name = input("頂點(diǎn)的名稱（ q 為退出）：")if v_name == 'q':breakv = 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)先搜索算法使用棧存儲(chǔ)下一個(gè)需要查找的節(jié)點(diǎn)'''def dfs(self, from_v, to_v):# 查找與 from_v 相鄰的節(jié)點(diǎn)self.find_neighbor(from_v)# 臨時(shí)路徑lst_path = [from_v]# 重復(fù)條件：棧不為空while len(self.queue_stack) != 0:# 從棧中取一個(gè)節(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__":# 初始化圖對(duì)象g = Graph(5)# 添加頂點(diǎn)for _ in range(len(g.matrix)):v_name = input("頂點(diǎn)的名稱（ q 為退出）：")if v_name == 'q':breakv = 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)及邊aprint("-----------頂點(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)系------------------------- 深度優(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:returnfind_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)時(shí)，不需要使用全局棧，只需要獲到當(dāng)前節(jié)點(diǎn)的相鄰節(jié)點(diǎn)便可。
4. 總結(jié)
圖是一種很重要的數(shù)據(jù)結(jié)構(gòu)，因這個(gè)世界中萬事萬物之間的關(guān)系并不是簡單的你和我，我和你的關(guān)系，本質(zhì)都是錯(cuò)綜復(fù)雜的。
圖能準(zhǔn)確的映射現(xiàn)實(shí)世界的這種錯(cuò)綜復(fù)雜關(guān)系，為計(jì)算機(jī)處理現(xiàn)實(shí)世界的問題提供了可能，也拓展了計(jì)算機(jī)在現(xiàn)實(shí)世界的應(yīng)用領(lǐng)域。
總結(jié)
以上是生活随笔為你收集整理的Python 图_系列之基于邻接矩阵实现广度、深度优先路径搜索算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 认知天性个人笔记2
- 下一篇： Win10如何清除运行历史记录