一般來(lái)講，實(shí)現(xiàn)圖的過(guò)程中需要有兩個(gè)自定義的類(lèi)進(jìn)行支撐：頂點(diǎn)(Vertex)類(lèi)，和圖(Graph)類(lèi)。按照這一架構(gòu)，Vertex類(lèi)至少需要包含名稱(chēng)(或者某個(gè)代號(hào)、數(shù)據(jù))和鄰接頂點(diǎn)兩個(gè)參數(shù)，前者作為頂點(diǎn)的標(biāo)識(shí)，后者形成頂點(diǎn)和頂點(diǎn)相連的邊，相應(yīng)地必須有訪問(wèn)獲取和設(shè)定參數(shù)的方法加以包裝。Graph類(lèi)至少需要擁有一個(gè)包含所有點(diǎn)的數(shù)據(jù)結(jié)構(gòu)(列表或者map等)，相應(yīng)地應(yīng)該有新增頂點(diǎn)、訪問(wèn)頂點(diǎn)、新增連接邊等方法。當(dāng)然，為了實(shí)現(xiàn)Dijkstra算法(一種基本的最短路徑算法)，除了可以在Graph類(lèi)里增加一個(gè)執(zhí)行Dijkstra算法的方法以外，還需要在Vertex類(lèi)里增加用于Dijkstra算法的一些參數(shù)：某一個(gè)頂點(diǎn)距離Dijkstra搜索起點(diǎn)的距離，以及一旦完成Dijkstra搜索需要回溯路徑時(shí)，前驅(qū)頂點(diǎn)的信息。

在這里記錄用python實(shí)現(xiàn)以上基本方法和Dijkstra算法的代碼，因?yàn)镻ython中的現(xiàn)成的數(shù)據(jù)結(jié)構(gòu)類(lèi)型便于使用，比如字典dict類(lèi)，很方便地能夠構(gòu)造一個(gè)類(lèi)似于map的映射，而且Python的sort方法也特別好用。首先是自定義類(lèi)頂點(diǎn)(Vertex)的代碼，如上所述，為了滿足BFS算法的執(zhí)行和回溯的需要，Vertex類(lèi)一共有四個(gè)參數(shù)：id(標(biāo)記)、connections(鄰接頂點(diǎn)字典，鍵值為鄰接頂點(diǎn)，對(duì)應(yīng)值為權(quán)重或者邊長(zhǎng))、前驅(qū)頂點(diǎn)pre和從起點(diǎn)的距離distance。這二者在Dijkstra算法的執(zhí)行過(guò)程中被賦值，在回溯時(shí)需要利用pre的信息。

Vertex類(lèi)的方法中多數(shù)為基本的訪問(wèn)參數(shù)(get)-設(shè)定參數(shù)(set)的方法對(duì)，比如訪問(wèn)/設(shè)定鄰接頂點(diǎn)信息的?add_neighbour(neighbour, weight)?和?get_connection()?，訪問(wèn)/設(shè)定前驅(qū)頂點(diǎn)信息的?get_pre()? 和?set_pre(prev)?，以及訪問(wèn)/設(shè)定從起點(diǎn)起距離的?get_distance()? 和?set_distance(dist)?。除此之外重載了字符串化方法，即__str__，這便于print函數(shù)和str函數(shù)將Vertex類(lèi)轉(zhuǎn)化為一個(gè)有意義的字符串。

1 classVertex:2 #初始化構(gòu)造函數(shù)，name為字符串，connections字典為

3 #前驅(qū)頂點(diǎn)pre，從起點(diǎn)距離distance，在Dijkstra執(zhí)行賦值后有意義

4 def __init__(self, name):5 self.id =name6 self.pre =None7 self.distance = float('inf')8 self.connections =dict()9

10 #重載字符串化函數(shù)，返回字符串

11 def __str__(self):12 return str(self.id) + "connected to:" + str([x.id for x inself.connections])13

14 #增加相鄰頂點(diǎn)，neighbour為Vertex類(lèi)，weight為浮點(diǎn)型邊權(quán)重

15 def add_neighbour(self, neighbour, weight=0):16 self.connections[neighbour] =weight17

18 #獲取頂點(diǎn)id函數(shù)

19 defget_id(self):20 returnself.id21

22 #獲取頂點(diǎn)鄰接點(diǎn)的函數(shù)，返回鍵值(Vertex)列表

23 defget_connections(self):24 returnself.connections.keys()25

26 #獲取頂點(diǎn)與鄰接點(diǎn)邊權(quán)重，傳入Vertex類(lèi)對(duì)象neighbour，返回weight(fl)

27 defget_weight(self, neighbour):28 returnself.connections[neighbour]29

30 #獲取頂點(diǎn)的距離(在BFS執(zhí)行后使用)

31 defget_distance(self):32 returnself.distance33

34 #獲取前驅(qū)頂點(diǎn)(在Dijkstra執(zhí)行后使用)

35 defget_pre(self):36 returnself.pre37

38 #設(shè)定頂點(diǎn)的距離(在Dijkstra執(zhí)行過(guò)程中調(diào)用)

39 defset_distance(self, dist):40 self.distance =dist41

42 #設(shè)定前驅(qū)頂點(diǎn)(在Dijkstra執(zhí)行過(guò)程中調(diào)用)

43 defset_pre(self, prev):44 self.pre = prev

圖(Graph)類(lèi)：擁有兩個(gè)參數(shù)：頂點(diǎn)字典(頂點(diǎn)id：頂點(diǎn)Vertex類(lèi))和頂點(diǎn)數(shù)量。頂點(diǎn)數(shù)量這個(gè)參數(shù)似乎沒(méi)什么用，除非是增加一個(gè)判斷圖是否為空的?isEmpty()?方法和?getSize()?方法可能用得著。

方法中包含新增頂點(diǎn)的?add_vertex(name)?，按照id獲取頂點(diǎn)的?get_vertex(name)?。dict的數(shù)據(jù)結(jié)構(gòu)給按照id訪問(wèn)頂點(diǎn)在空間上和時(shí)間上都創(chuàng)造了極大的方便，也為此參數(shù)中為頂點(diǎn)字典而不用頂點(diǎn)列表。添加邊的方法?add_edge(vertex1, vertex2, weight)?，其中需要調(diào)用Vertex類(lèi)中設(shè)定鄰接點(diǎn)的方法。除此之外，Graph類(lèi)還有一些重載的方法，比如重載contains，這個(gè)函數(shù)在類(lèi)似于?3 in list(range(5))?這樣的語(yǔ)句中被調(diào)用，比如經(jīng)常用的，判斷某個(gè)元素是否在列表內(nèi)等。重載迭代器__iter__，類(lèi)似于?for item in list(range(10)):?這樣的語(yǔ)句中被調(diào)用，有助于圖中所有Vertex的遍歷?；诘鬟€可以重載字符串化方法__str__。

最后就是Dijkstra算法。關(guān)于這個(gè)算法的信息準(zhǔn)備記錄在另一篇隨筆中，基本思路是創(chuàng)建一個(gè)優(yōu)先隊(duì)列(即距離起始點(diǎn)路程從小到大的隊(duì)列)，每次查看列表中路程最短的點(diǎn)A，觀察在這個(gè)頂點(diǎn)A的鄰接點(diǎn)中，是否有可能因?yàn)橥ㄟ^(guò)頂點(diǎn)A而使得該鄰接點(diǎn)的路程縮減。每次這樣一輪操作結(jié)束以后就從隊(duì)列中刪去這個(gè)點(diǎn)A，然后把隊(duì)列重新排列一遍。在以前課上的學(xué)習(xí)中，優(yōu)先隊(duì)列使用的是二叉堆(Binary Heap)實(shí)現(xiàn)，在這里我直接調(diào)用了Python內(nèi)置的sort函數(shù)，雖然計(jì)算復(fù)雜度不敢保證，但是從后面用的實(shí)際例子的效率來(lái)說(shuō)也沒(méi)有任何影響。

1 classGraph:2 #無(wú)參數(shù)構(gòu)造函數(shù)，vertex_dict為映射字典

3 def __init__(self):4 self.vertex_dict =dict()5 self.vertex_num =06

7 #增加頂點(diǎn)函數(shù)，傳入新增頂點(diǎn)id

8 defadd_vertex(self, name):9 if name not inself.vertex_dict.keys():10 new_vertex =Vertex(name)11 self.vertex_dict[name] =new_vertex12 self.vertex_num = self.vertex_num + 1

13

14 #增加邊函數(shù)， 傳入頂點(diǎn)1名稱(chēng)、頂點(diǎn)2名稱(chēng)、權(quán)重

15 defadd_edge(self, vertex1, vertex2, weight):16 if vertex1 not inself.vertex_dict:17 self.add_vertex(vertex1)18 if vertex2 not inself.vertex_dict:19 self.add_vertex(vertex2)20 self.vertex_dict[vertex1].add_neighbour(self.vertex_dict[vertex2], weight)21 self.vertex_dict[vertex2].add_neighbour(self.vertex_dict[vertex1], weight)22

23 #按照id檢索頂點(diǎn)函數(shù)，傳入id，返回Vertex類(lèi)

24 defget_vertex(self, name):25 if name inself.vertex_dict.keys():26 returnself.vertex_dict[name]27 else:28 returnNone29

30 #重載contains方法，傳入id，返回bool值

31 def __contains__(self, item):32 return item inself.vertex_dict33

34 #重載迭代器，返回對(duì)應(yīng)迭代器

35 def __iter__(self):36 returniter(self.vertex_dict.values())37

38 #重載字符串化方法，返回字符串

39 def __str__(self):40 o_str =str()41 for item inself:42 o_str = o_str + str(item) + '\n'

43 returno_str44

45 #Dijkstra算法，傳入起點(diǎn)

46 defdijkstra_search(self, start):47 #優(yōu)先隊(duì)列priority

48 priority =list(self.vertex_dict.values())49 #起點(diǎn)距離置零

50 start.set_distance(0)51 #優(yōu)先隊(duì)列重排

52 priority.sort(key=lambda x: x.get_distance(), reverse=True)53 whilepriority:54 #重排標(biāo)記changed，若存在頂點(diǎn)發(fā)生distance變化則標(biāo)記為T(mén)rue

55 changed =False56 #彈出最高優(yōu)先頂點(diǎn)current

57 current =priority.pop()58 #遍歷current鄰接頂點(diǎn)

59 for vertex_tmp incurrent.get_connections():60 dist_tmp = current.get_distance() +current.get_weight(vertex_tmp)61 #若發(fā)現(xiàn)優(yōu)勢(shì)路徑則更改鄰接頂點(diǎn)的distance和前驅(qū)頂點(diǎn)pre

62 if dist_tmp

67 ifchanged:68 priority.sort(key=lambda x: x.get_distance(), reverse=True)

最后，和Dijkstra算法配合還需要一個(gè)路徑回溯的方法。本來(lái)把回溯作為圖類(lèi)的一個(gè)方法也可以，但是由于通過(guò)訪問(wèn)頂點(diǎn)的pre參數(shù)已經(jīng)可以回溯到上一個(gè)Vertex類(lèi)，中間不涉及到圖的操作，因此可以安全地把它寫(xiě)成一個(gè)靜態(tài)方法的形式，即不放在Graph類(lèi)中：

1 #回溯路徑函數(shù)，傳入?yún)?shù)終點(diǎn)destination，返回路徑列表list(Vertex)

2 defreverse_trace(destination):3 current =destination4 trace =[destination]5 whilecurrent.get_pre():6 current =current.get_pre()7 trace.append(current)8 trace.reverse()9 return trace

這個(gè)函數(shù)返回的是一個(gè)路徑中順序出現(xiàn)的頂點(diǎn)Vertex類(lèi)列表。

作為圖的一個(gè)練習(xí)和測(cè)試，我拿了北京市的地鐵信息。首先我在某一個(gè)文件夾里新建了編號(hào)為line1到line10的10個(gè).txt文件，錄入了10條地鐵線的信息。后來(lái)又新增了13號(hào)線和15號(hào)線的信息。這些txt里的信息是這樣儲(chǔ)存的：a)一行一個(gè)站名，表示起點(diǎn)站；b)一行一個(gè)站名+一個(gè)數(shù)字，表示一個(gè)站和前一站的距離；c)一行兩個(gè)站名+一個(gè)數(shù)字，表示兩個(gè)站之間的距離。然后可以寫(xiě)一個(gè)讀入的函數(shù)，把這些信息讀進(jìn)來(lái)，每個(gè)站名就是一個(gè)id，形成一張圖，選定一個(gè)起點(diǎn)S以后執(zhí)行Dijkstra算法，然后選定一個(gè)終點(diǎn)D回溯，就得到了從S到D的最短路徑。

如果只是想得到站與站之間的最短距離，這個(gè)方法當(dāng)然是合適的；不過(guò)，如果考慮到換乘因素，就會(huì)發(fā)現(xiàn)這個(gè)算法沒(méi)有考慮到換乘的時(shí)間代價(jià)，這會(huì)使得搜索出一些需要換乘很多次的結(jié)果，而這在現(xiàn)實(shí)生活中并不是最快的。一個(gè)改進(jìn)成本很小的方案是，把每個(gè)站所屬的線路號(hào)碼加在站名后面作為id的一部分，比如用“王府井1”作為一個(gè)id。同時(shí)，利用存儲(chǔ)形式c來(lái)規(guī)定換乘站的間距，比如規(guī)定“海淀黃莊4”和“海淀黃莊10”的距離。這樣一來(lái)就可以考慮換乘代價(jià)了。在這個(gè)思路下，Graph類(lèi)相應(yīng)的讀入函數(shù)：

1 classGraph:2 #讀取頂點(diǎn)文件(適用于地鐵路線例子的方法)，傳入文件路徑path和線路編號(hào)subway

3 defread_in(self, path, subway):4 with open(path, 'r') as file:5 #按行讀取文件

6 line =file.readline()7 station =None8 whileline:9 info_list =line.split()10 #當(dāng)行中僅含有1個(gè)元素時(shí)，僅創(chuàng)建

11 if len(info_list) == 1:12 station =info_list[0]13 station = station +str(subway)14 self.add_vertex(station)15 #當(dāng)行中含有2個(gè)元素時(shí)，第1個(gè)元素為車(chē)站名稱(chēng)，第2個(gè)元素為距上個(gè)車(chē)站距離

16 elif len(info_list) == 2:17 pre_station =station18 [station, distance] =info_list19 distance =int(distance)20 station = station +str(subway)21 self.add_vertex(station)22 self.add_edge(pre_station, station, distance)23 #否則當(dāng)行中含有3個(gè)元素，前2個(gè)元素為車(chē)站，第3個(gè)元素為前二者間距

24 else:25 [station1, station2, distance] =info_list26 distance =int(distance)27 self.add_edge(station1, station2, distance)28 line = file.readline()

最后是初始化函數(shù)和個(gè)人偏愛(ài)的交互式菜單代碼，僅供參考：

1 #初始化函數(shù)(適用于地鐵路線例子的方法)

2 #讀入在file_path所示文件夾下的北京地鐵線數(shù)據(jù)，返回生成的圖

3 definitialize():4 graph =Graph()5 file_path = 'D:\Personal Documents\Project\BeijingSubway\line'

6 for i in range(1, 11):7 path = file_path + str(i) + '.txt'

8 graph.read_in(path, i)9 path = file_path + '13.txt'

10 graph.read_in(path, 13)11 path = file_path + '15.txt'

12 graph.read_in(path, 15)13 returngraph14

15

16 #交互式菜單函數(shù)(適用于地鐵路線例子的方法)，傳入圖

17 defroute_find_menu(graph):18 print('>> 尋找乘地鐵最短路線，輸入0退出')19 start = input('>> 輸入起始站名+地鐵線(如“王府井1”)：')20 while start != '0':21 graph.breadth_first_search(graph.get_vertex(start))22 destination = input('>> 輸入終點(diǎn)站名+地鐵線(如“王府井1”)：')23 if destination == '0':24 break

25 trace_list =reverse_trace(graph.get_vertex(destination))26 print([x.get_id() for x intrace_list])27 start = input('>> 輸入起始站名：')

最后只要分別調(diào)用?graph1 = initialize()?創(chuàng)建實(shí)例，并且用?route_find_menu(graph1)?進(jìn)入菜單即可。

總結(jié)

以上是生活随笔為你收集整理的python无向加权图_图：无向图(Graph)基本方法及Dijkstra算法的实现 [Python]的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。