Python基于鏈接表實現無向圖最短路徑搜索
前言
圖的常用存儲方式有 2 種:
- 鄰接炬陣
- 鏈接表
鄰接炬陣的優(yōu)點和缺點都很明顯。優(yōu)點是簡單、易理解,對于大部分圖結構而言,都是稀疏的,使用炬陣存儲空間浪費就較大。
鏈接表的存儲相比較鄰接炬陣,使用起來更方便,對于空間的使用是剛好夠用原則,不會產生太多空間浪費。操作起來,也是簡單。
本文將以鏈接表方式存儲圖結構,在此基礎上實現無向圖最短路徑搜索。
1. 鏈接表
鏈接表的存儲思路:
使用鏈接表實現圖的存儲時,有主表和子表概念。
- 主表: 用來存儲圖對象中的所有頂點數據。
- 子表: 每一個頂點自身會維護一個子表,用來存儲與其相鄰的所有頂點數據。
如下圖結構中有 5 個頂點,使用鏈接表保存時,會有主表 1 張,子表 5 張。鏈接表的優(yōu)點是能夠緊湊地表示稀疏圖。
在 Python 中可以使用列表嵌套實現鏈接表,這應該是最簡單的表達方式。
g = [ ['A0', [('B1', 3), ('D3', 5)]], ['B1', [('C2', 4)]], ['C2', [('D3', 6), ('E4', 1)]], ['D3', [('E4', 2)]], ['E4', [('B1', 7)]], ]
在此基礎上,可以做一些簡單的常規(guī)操作。
查詢所有頂點:
for node in g: print(node[0],end=' ')
查詢頂點及其相鄰頂點:
for node in g: print('-------------------') print(node[0], ":", end='') edges = node[1] for e in edges: v, w = e print(v, w, end=';') print()
當頂點和相鄰頂點之間的關系很復雜時,這種層層嵌套的存儲格式會讓人眼花繚亂。即使要使用這種嵌套方式,那也應該選擇 Python 中的字典類型,對于查詢會方便很多。
g = { 'A0':{'B1': 3, 'D3': 5}, 'B1': {'C2': 4}, 'C2': {'D3': 6, 'E4': 1}, 'D3': {'E4':2}, 'E4': {'B1': 7} }
如上結構,在查詢時,無論是方便性還是性能,都要強于完全的列表方案。
查詢所有頂點:
for node in g.keys(): print(node,end=" ")
查詢與某一頂點相鄰的頂點時,只需要提供頂點名稱就可以了。
print("查詢與 A0 項點有連接的其它頂點") for k, v in g.get('A0').items(): print((k, v), end=";")
以上的存儲方案,適合于演示,并不適合于開發(fā)環(huán)境,因頂點本身是具有特定的數據含義(如,可能是城市、公交車站、網址、路由器……),且以上存儲方案讓頂點和其相鄰頂點的信息過度耦合,在實際運用時,會牽一發(fā)而動全身。
也許一個微不足道的修改,會波動到整個結構的更新。
所以,有必要引于 OOP
設計理念,讓頂點和圖有各自特定數據結構,通過 2 種類類型可以更好地體現圖是頂點的集合,頂點和頂點之間的多對多關系。
項點類:
class Vertex: def __init__(self, name, v_id=0): # 頂點的編號 self.v_id = v_id # 頂點的名稱 self.v_name = name # 是否被訪問過:False 沒有 True:有 self.visited = False # 與此頂點相連接的其它頂點 self.connected_to = {}
頂點類結構說明:
visited
:用于搜索路徑算法中,檢查節(jié)點是否已經被搜索過。connected_to
:存儲與項點相鄰的頂點信息。這里使用了字典,以頂點為鍵,權重為值。
圖類:
class Graph: def __init__(self): # 一維列表,保存節(jié)點 self.vert_list = {} # 頂點個數 self.v_nums = 0 # 使用隊列模擬隊列或棧,用于路徑搜索算法 self.queue_stack = [] # 保存搜索到的路徑 self.searchPath = []
圖類結構說明:
queue_stack
:使用隊列模擬?;蜿犃?。用于路徑搜索過程中保存臨時數據。
怎么使用列表模擬隊列或棧?
列表有 append()
、pop()
2 個很價值的方法。
append()
用來向列表中添加數據,且每次都是從列表最后面添加。
pop()
默認從列表最后面刪除且彈出數據, pop(參數)
可以提供索引值用來從指定位置刪除且彈出數據。
使用 append() 和 pop() 方法就能模擬棧,從同一個地方進出數據。
使用 append() 和 pop(0) 方法就能模擬隊列,從后面添加數據,從最前面獲取數據
searchPath
:用于保存搜索到的路徑數據。
2. 最短路徑算法
從圖結構可知,從一個頂點到達另一個頂點,可不止一條可行路徑,在眾多路徑我們總是試圖選擇一條最短路徑,當然,需求不同,衡量一個路徑是不是最短路徑的標準也會不同。
如打開導航系統(tǒng)后,最短路徑可能是費用最少的那條,可能是速度最快的那條,也可能是量程數最少的或者是紅綠燈是最少的……
在無向圖中,以經過的邊數最少的路徑為最短路徑。
在有向加權圖中,會以附加在每條邊上的權重的數據含義來衡量。權重可以是時間、速度、量程數……
2.1 無向圖最短路徑算法
查找無向圖中任意兩個頂點間的最短路徑長度,可以直接使用廣度搜索算法。如下圖求解 A0 ~ F5
的最短路徑。
Tips: 無向圖中任意 2 個頂點間的最短路徑長度由邊數決定。
廣度優(yōu)先搜索算法流程:
廣度優(yōu)先搜索算法的基本原則:以某一頂點為參考點,先搜索離此頂點最近的頂點,再搜索離最近頂點最近的頂點……以此類推,一層一層向目標頂點推進。
如從頂點 A0
找到頂點 F5
。先從離 A0
最近的頂點 B1
、D3
找起,如果沒找到,再找離 B1
、D3
最近的頂點 C2
、E4
,如果還是沒有找到,再找離 C2
、E4
最近的頂點 F5
。
因為每一次搜索都是采用最近原則,最后搜索到的目標也一定是最近的路徑。
也因為采用最近原則,所以搜索過程中,在搜索過程中所經歷到的每一個頂點的路徑都是最短路徑。最近+最近,結果必然還是最近。
顯然,廣度優(yōu)先搜索的最近搜索原則是符合先進先出思想的,具體算法實施時可以借助隊列實現整個過程。
算法流程:
1.先確定起始點 A0
。
2.找到 A0
的 2 個后序頂點 B1
、D3
(或者說 B1、D3
的前序頂點是 A0
),壓入隊列中。除去起點 A0
,B1
、D3
頂點屬于第一近壓入隊列的節(jié)點。
B1
和D3
壓入隊列的順序并不影響A0
~B1
或A0
~D3
的路徑距離(都是 1)。A0
~B1
的最短路徑長度為 1A0
~D3
的最短路徑長度為 1
3.從隊列中搜索 B1
時,找到 B1
的后序頂點 C2
并壓入隊列。B1
是 C2
的前序頂點。
B1
~ C2
的最短路徑長度為 1,而又因為 A0
~B1
的最短路徑長度為 1 ,所以 A0
~ C2
的最短路徑為 2
4.B1
搜索完畢后,在隊列中搜索 B3
時,找到 B3
的后序頂點 E4
,壓入隊列。因 B1
和 D3
屬于第一近頂點,所以這 2 個頂點的后序頂點 C2
、E4
屬于第二近壓入隊列,或說 A0-B1-C2
、A0-D3-E4
的路徑距離是相同的(都為 2)。
5.當搜索到 C2
時,沒有后序頂點,此時隊列沒有壓入操作。
6.當 搜索到 E4
時,E4
有 2 個后序頂點 C2
、F5
,因 C2
已經壓入過,所以僅壓入 F5
。因 F5
是由第二近頂點壓入,所以 F5
是屬于第三近壓入頂點。
A0-D3-E4-F5
的路徑為 3。
編碼實現廣度優(yōu)先算法:
在頂點類中添加如下幾個方法:
class Vertex: def __init__(self, v_name, v_id=0): # 頂點的編號 self.v_id = v_id # 頂點的名稱 self.v_name = v_name # 是否被訪問過:False 沒有 True:有 self.visited = False # 與此頂點相連接的其它頂點 self.connected_to = {} ''' 添加鄰接頂點 nbr_ver:相鄰頂點 weight:無向無權重圖,權重默認設置為 1 ''' def add_neighbor(self, nbr_ver, weight=1): # 以相鄰頂點為鍵,權重為值 self.connected_to[nbr_ver] = weight ''' 顯示與當前頂點相鄰的頂點 ''' def __str__(self): return '與 {0} 頂點相鄰的頂點有:{1}'.format(self.v_name, str([(key.v_name, val) for key, val in self.connected_to.items()])) ''' 得到相鄰頂點的權重 ''' def get_weight(self, nbr_v): return self.connected_to[nbr_v] ''' 判斷給定的頂點是否和當前頂點相鄰 ''' def is_neighbor(self, nbr_v): return nbr_v in self.connected_to
頂點類用來構造一個新頂點,并維護與相鄰頂點的關系。
對圖類中的方法做一下詳細解釋:
初始化方法:
class Graph: def __init__(self): # 一維列表,保存節(jié)點 self.vert_list = {} # 頂點個數 self.v_nums = 0 # 使用隊列模擬隊列或棧,用于路徑搜索算法 self.queue_stack = [] # 保存搜索到的路徑 self.searchPath = []
為圖添加新頂點方法:
def add_vertex(self, vert): if vert.v_name in self.vert_list: # 已經存在 return # 頂點的編號內部生成 vert.v_id = self.v_nums # 所有頂點保存在圖所維護的字典中,以頂點名為鍵,頂點對象為值 self.vert_list[vert.v_name] = vert # 數量增一 self.v_nums += 1
頂點的編號由圖對象內部指定,便于統(tǒng)一管理。
所有頂點保存在一個字典中,以頂點名稱為鍵,頂點對象為值。也可以使用列表直接保存頂點,根據需要決定。
提供一個根據頂點名稱返回頂點的方法:
''' 根據頂點名找到頂點對象 ''' def find_vertex(self, v_name): if v_name in self.vert_list: return self.vert_list.get(v_name) # 查詢所有頂點 def find_vertexes(self): return [str(ver) for ver in self.vert_list.values()]
添加頂點與相鄰頂點的關系:此方法屬于一個封裝方法,本質是調用頂點自身的添加相鄰頂點方法。
''' 添加節(jié)點與節(jié)點之間的關系(邊), 如果是無權重圖,統(tǒng)一設定為 1 ''' def add_edge(self, from_v, to_v, weight=1): # 如果節(jié)點不存在 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.add_neighbor(to_v, weight)
圖中核心方法:用來廣度優(yōu)先搜索算法查找頂點與頂點之間的路徑
''' 廣度優(yōu)先搜索 ''' def bfs_nearest_path(self, from_v, to_v): tmp_path = [] tmp_path.append(from_v) # 起始頂點不用壓入隊列 from_v.visited = True # from_v 頂點的相鄰頂點壓入隊列 self.push_queue(from_v) while len(self.queue_stack) != 0: # 從隊列中獲取頂點 v_ = self.queue_stack.pop(0) if from_v.is_neighbor(v_): # 如果 v_ 是 from_v 的后序相鄰頂點,則連接成一條中路徑信息 tmp_path.append(v_) # 添加路徑信息 self.searchPath.append(tmp_path) tmp_path = tmp_path.copy() tmp_path.pop() else: for path_ in self.searchPath: tmp_path = path_.copy() tmp = tmp_path[len(tmp_path) - 1] if tmp.is_neighbor(v_): tmp_path.append(v_) self.searchPath.append(tmp_path) if v_.v_id == to_v.v_id: break else: self.push_queue(v_) ''' 把某一頂點的相鄰頂點壓入隊列 ''' def push_queue(self, vertex): # 獲取 vertex 頂點的相鄰頂點 for v_ in vertex.connected_to.keys(): # 檢查此頂點是否壓入過 if v_.visited: continue vertex.visited = True self.queue_stack.append(v_)
廣度優(yōu)先搜索算法有一個核心點,當搜索到某一個頂點后,需要找到與此頂點相鄰的其它頂點,并壓入隊列中。push_queue()
方法就是做些事情的。如果某一個頂點曾經進過隊列,就不要再重復壓入隊列了。
測試代碼:
''' 測試無向圖最短路徑 ''' if __name__ == '__main__': # 初始化圖 graph = Graph() # 添加節(jié)點 for v_name in ['A', 'B', 'C', 'D', 'E', 'F']: v = Vertex(v_name) graph.add_vertex(v) # 添加頂點之間關系 v_to_v = [('A', 'B'), ('A', 'D'), ('B', 'C'), ('C', 'E'), ('D', 'E'), ('E', 'F')] # 無向圖中每 2 個相鄰頂點之間互為關系 for v in v_to_v: f_v = graph.find_vertex(v[0]) t_v = graph.find_vertex(v[1]) graph.add_edge(f_v, t_v) graph.add_edge(t_v, f_v) # 輸出所有頂點 print('-----------頂點及頂點之間的關系-------------') for v in graph.find_vertexes(): print(v) # 查找路徑 print('-------------廣度優(yōu)先搜索--------------------') # 起始點 f_v = graph.find_vertex('A') # 目標點 t_v = graph.find_vertex('F') # 廣度優(yōu)先搜索 graph.bfs_nearest_path(f_v, t_v) for path in graph.searchPath: weight = 0 for idx in range(len(path)): if idx != len(path) - 1: weight += path[idx].get_weight(path[idx + 1]) print(path[idx].v_name, end='-') print("的最短路徑長度,", weight)
輸出結果:
-----------頂點及頂點之間的關系-------------
與 A 頂點相鄰的頂點有:[('B', 1), ('D', 1)]
與 B 頂點相鄰的頂點有:[('A', 1), ('C', 1)]
與 C 頂點相鄰的頂點有:[('B', 1), ('E', 1)]
與 D 頂點相鄰的頂點有:[('A', 1), ('E', 1)]
與 E 頂點相鄰的頂點有:[('C', 1), ('D', 1), ('F', 1)]
與 F 頂點相鄰的頂點有:[('E', 1)]
-------------廣度優(yōu)先搜索--------------------
A-B-的最短路徑長度, 1
A-D-的最短路徑長度, 1
A-B-C-的最短路徑長度, 2
A-D-E-的最短路徑長度, 2
A-B-C-E-的最短路徑長度, 3
A-D-E-的最短路徑長度, 2
A-B-C-E-的最短路徑長度, 3
A-D-E-F-的最短路徑長度, 3
A-B-C-E-F-的最短路徑長度, 4
A-D-E-F-的最短路徑長度, 3
A-B-C-E-F-的最短路徑長度, 4
廣度優(yōu)先搜索算法也可以使用遞歸方案:
''' 遞歸實現 ''' def bfs_nearest_path_dg(self, from_v, to_v): # 相鄰頂點 self.push_queue(from_v) tmp_v = self.queue_stack.pop(0) if not tmp_v.visited: self.searchPath.append(tmp_v) if tmp_v.v_id == to_v.v_id: return self.bfs_nearest_path_dg(tmp_v, to_v)
在無向圖中,查找起始點到目標點的最短路徑,使用廣度優(yōu)先搜索算法便可實現,但如果是有向加權圖,可能不會稱心如愿。因有向加權圖中的邊是有權重的。所以對于有向加權圖則需要另擇方案。
3. 總結
圖數據結構的實現過程中會涉及到其它數據結構的運用。學習、使用圖數據結構對其它數據結構有重新認識和鞏固作用。
以上就是Python基于鏈接表實現無向圖最短路徑搜索的詳細內容,更多關于Python無向圖最短路徑搜索的資料請關注腳本之家其它相關文章!
相關文章
python,Java,JavaScript實現indexOf
這篇文章主要介紹了python,Java,JavaScript如何實現indexOf,幫助大家更好的理解indexOf,感興趣的朋友可以了解下2020-09-09