Python使用鄰接矩陣實(shí)現(xiàn)圖及Dijkstra算法問題
使用鄰接矩陣實(shí)現(xiàn)圖及Dijkstra算法
# 鄰接矩陣實(shí)現(xiàn)無向圖 Dijkstra算法 inf = float("inf") class Graph(): def __init__(self, n): self.vertexn = n self.gType = 0 self.vertexes = [inf]*n self.arcs = [self.vertexes*n] # 鄰接矩陣 self.visited = [False]*n # 用于深度遍歷記錄結(jié)點(diǎn)的訪問情況 def addvertex(self, v, i): self.vertexes[i] = v def addarcs(self, row, column, weight): self.arcs[row][column] = weight # 深度優(yōu)先遍歷 def DFS(self, i): j = 0 print("vertex:{}".format(self.vertexes[i]), end=" ") # 先打印訪問到的節(jié)點(diǎn) self.visited[i] = True while j < self.vertexn: if (self.arcs[i][j] != inf) and (not self.visited[j]): print(self.arcs[i][j], end=" ") self.DFS(j) j += 1 # 廣度優(yōu)先遍歷 def BFS(self, k): self.visited = [False]*self.vertexn # 訪問性重置 q = [] print("vertex:{}".format(self.vertexes[k]), end=" ") self.visited[k] = True q.append(k) while q != []: i = q.pop(0) for j in range(self.vertexn): if(self.arcs[i][j] != inf) and (not self.visited[j]): print(self.arcs[i][j], end=" ") # 父節(jié)點(diǎn)與子節(jié)點(diǎn)的距離 print("vertex:{}".format(self.vertexes[j]), end=" ") self.visited[j] = True q.append(j) # 最短路徑算法-Dijkstra 輸入點(diǎn)v0,找到所有點(diǎn)到v0的最短距離 def Dijkstra(self, v0): # 初始化操作 D = [inf]*self.vertexn # 用于存放從頂點(diǎn)v0到v的最短路徑長度 path = [None]*self.vertexn # 用于存放從頂點(diǎn)v0到v的路徑 final = [None]*self.vertexn # 表示從v0到v的最短路徑是否找到最短路徑 for i in range(self.vertexn): final[i] = False D[i] = self.arcs[v0][i] path[i] = "" # 路徑先置空 if D[i] < inf: path[i] = self.vertexes[i] # 如果v0直接連到第i點(diǎn),則路徑直接改為i D[v0] = 0 final[v0] = True ### for i in range(1, self.vertexn): min = inf # 找到離v0最近的頂點(diǎn) for k in range(self.vertexn): if(not final[k]) and (D[k] < min): v = k min = D[k] final[v] = True # 最近的點(diǎn)找到,加入到已得最短路徑集合S中 此后的min將在處S以外的vertex中產(chǎn)生 for k in range(self.vertexn): if(not final[k]) and (min+self.arcs[v][k] < D[k]): # 如果最短的距離(v0-v)加上v到k的距離小于現(xiàn)存v0到k的距離 D[k] = min+self.arcs[v][k] path[k] = path[v]+","+self.vertexes[k] return D, path if __name__ == "__main__": g = Graph(5) g.vertexes = ["A", "B", "C", "D", "E"] g.arcs = [[inf, 60, 80, 30, inf], [60, inf, 40, 75, inf], [ 80, 40, inf, inf, 35], [30, 75, inf, inf, 45], [inf, inf, 35, 45, inf]] print("深度優(yōu)先遍歷:") g.DFS(0) print("\n廣度優(yōu)先遍歷:") g.BFS(0) print() print("Dijkstra搜索點(diǎn)到圖中各點(diǎn)的最短路徑:") D, path = g.Dijkstra(0) print(D) print(path)
將鄰接矩陣輸出成圖
利用networkx,numpy,matplotlib,將鄰接矩陣輸出為圖形。
1,自身確定一個(gè)鄰接矩陣,然后通過循環(huán)的方式添加變,然后輸出圖像
import networkx as nx import matplotlib.pyplot as plt import numpy as np G = nx.Graph() Matrix = np.array( [ [0, 1, 1, 1, 1, 1, 0, 0], # a [0, 0, 1, 0, 1, 0, 0, 0], # b [0, 0, 0, 1, 0, 0, 0, 0], # c [0, 0, 0, 0, 1, 0, 0, 0], # d [0, 0, 0, 0, 0, 1, 0, 0], # e [0, 0, 1, 0, 0, 0, 1, 1], # f [0, 0, 0, 0, 0, 1, 0, 1], # g [0, 0, 0, 0, 0, 1, 1, 0] # h ] ) for i in range(len(Matrix)): for j in range(len(Matrix)): G.add_edge(i, j) nx.draw(G) plt.show()
2,有向圖
G = nx.DiGraph() G.add_node(1) G.add_node(2) G.add_nodes_from([3, 4, 5, 6]) G.add_cycle([1, 2, 3, 4]) G.add_edge(1, 3) G.add_edges_from([(3, 5), (3, 6), (6, 7)]) nx.draw(G) # plt.savefig("youxiangtu.png") plt.show()
3,5節(jié)點(diǎn)完全圖
G = nx.complete_graph(5) nx.draw(G) plt.savefig("8nodes.png") plt.show()
4,無向圖
G = nx.Graph() G.add_node(1) G.add_node(2) G.add_nodes_from([3, 4, 5, 6]) G.add_cycle([1, 2, 3, 4]) G.add_edge(1, 3) G.add_edges_from([(3, 5), (3, 6), (6, 7)]) nx.draw(G) # plt.savefig("wuxiangtu.png") plt.show()
5,顏色節(jié)點(diǎn)圖
G = nx.Graph() G.add_edges_from([(1, 2), (1, 3), (1, 4), (1, 5), (4, 5), (4, 6), (5, 6)]) pos = nx.spring_layout(G) colors = [1, 2, 3, 4, 5, 6] nx.draw_networkx_nodes(G, pos, node_color=colors) nx.draw_networkx_edges(G, pos) plt.axis('off') # plt.savefig("color_nodes.png") plt.show()
將圖轉(zhuǎn)化為鄰接矩陣,再將鄰接矩陣轉(zhuǎn)化為圖,還有圖的集合表示,鄰接矩陣表示,圖形表示,這三種表現(xiàn)形式互相轉(zhuǎn)化的問題是一個(gè)值得學(xué)習(xí)的地方。
總結(jié)
以上為個(gè)人經(jīng)驗(yàn),希望能給大家一個(gè)參考,也希望大家多多支持腳本之家。
相關(guān)文章
Anaconda中Python虛擬環(huán)境的創(chuàng)建使用與刪除方法詳解
這篇文章主要為大家介紹了在Anaconda環(huán)境下,創(chuàng)建、使用與刪除Python虛擬環(huán)境的方法,具有一定的借鑒價(jià)值,需要的小伙伴可以跟隨小編一起了解一下2023-08-08python中List添加與刪除元素的幾種方法實(shí)例
列表基本上是?Python?中最常用的數(shù)據(jù)結(jié)構(gòu)之一了,并且刪除操作也是經(jīng)常使用的,下面這篇文章主要給大家介紹了關(guān)于python中List添加與刪除元素的相關(guān)資料,需要的朋友可以參考下2022-09-09Python使用urlretrieve實(shí)現(xiàn)直接遠(yuǎn)程下載圖片的示例代碼
這篇文章主要介紹了Python使用urlretrieve實(shí)現(xiàn)直接遠(yuǎn)程下載圖片的示例代碼,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-08-08Python實(shí)現(xiàn)字符串格式化輸出的方法詳解
這篇文章主要介紹了Python實(shí)現(xiàn)字符串格式化輸出的方法,結(jié)合具體實(shí)例形式總結(jié)分析了Python字符串格式化輸出的各種常用操作技巧,需要的朋友可以參考下2017-09-09詳解python ThreadPoolExecutor異常捕獲
本文主要介紹了詳解python ThreadPoolExecutor異常捕獲,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-01-01python繪制帶有誤差棒條形圖的實(shí)現(xiàn)
本文主要介紹了python繪制帶有誤差棒條形圖的實(shí)現(xiàn),文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-07-07python-Web-flask-視圖內(nèi)容和模板知識(shí)點(diǎn)西寧街
在本篇文章里小編給大家分享了關(guān)于python-Web-flask-視圖內(nèi)容和模板的相關(guān)知識(shí)點(diǎn)內(nèi)容,有需要的朋友們參考學(xué)習(xí)下。2019-08-08