欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Python使用鄰接矩陣實現(xiàn)圖及Dijkstra算法問題

 更新時間:2022年12月16日 10:24:55   作者:科恩兄弟  
這篇文章主要介紹了Python使用鄰接矩陣實現(xiàn)圖及Dijkstra算法問題,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教

使用鄰接矩陣實現(xiàn)圖及Dijkstra算法

# 鄰接矩陣實現(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é)點的訪問情況

    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é)點
        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é)點與子節(jié)點的距離
                    print("vertex:{}".format(self.vertexes[j]), end=" ")
                    self.visited[j] = True
                    q.append(j)

    # 最短路徑算法-Dijkstra 輸入點v0,找到所有點到v0的最短距離
    def Dijkstra(self, v0):
        # 初始化操作
        D = [inf]*self.vertexn  # 用于存放從頂點v0到v的最短路徑長度
        path = [None]*self.vertexn  # 用于存放從頂點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點,則路徑直接改為i
        D[v0] = 0
        final[v0] = True
        ###
        for i in range(1, self.vertexn):
            min = inf  # 找到離v0最近的頂點
            for k in range(self.vertexn):
                if(not final[k]) and (D[k] < min):
                    v = k
                    min = D[k]
            final[v] = True  # 最近的點找到,加入到已得最短路徑集合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搜索點到圖中各點的最短路徑:")
    D, path = g.Dijkstra(0)
    print(D)
    print(path)

將鄰接矩陣輸出成圖

利用networkx,numpy,matplotlib,將鄰接矩陣輸出為圖形。

1,自身確定一個鄰接矩陣,然后通過循環(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é)點完全圖

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é)點圖

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)化的問題是一個值得學習的地方。

總結(jié)

以上為個人經(jīng)驗,希望能給大家一個參考,也希望大家多多支持腳本之家。

相關文章

  • Python基礎入門之魔法方法與異常處理

    Python基礎入門之魔法方法與異常處理

    在python中,所有以“__"雙下劃線包起來的方法,都統(tǒng)稱為魔法方法,下面這篇文章主要給大家介紹了關于Python基礎入門之魔法方法與異常處理的相關資料,需要的朋友可以參考下
    2021-11-11
  • Anaconda中Python虛擬環(huán)境的創(chuàng)建使用與刪除方法詳解

    Anaconda中Python虛擬環(huán)境的創(chuàng)建使用與刪除方法詳解

    這篇文章主要為大家介紹了在Anaconda環(huán)境下,創(chuàng)建、使用與刪除Python虛擬環(huán)境的方法,具有一定的借鑒價值,需要的小伙伴可以跟隨小編一起了解一下
    2023-08-08
  • python中List添加與刪除元素的幾種方法實例

    python中List添加與刪除元素的幾種方法實例

    列表基本上是?Python?中最常用的數(shù)據(jù)結(jié)構之一了,并且刪除操作也是經(jīng)常使用的,下面這篇文章主要給大家介紹了關于python中List添加與刪除元素的相關資料,需要的朋友可以參考下
    2022-09-09
  • Python使用urlretrieve實現(xiàn)直接遠程下載圖片的示例代碼

    Python使用urlretrieve實現(xiàn)直接遠程下載圖片的示例代碼

    這篇文章主要介紹了Python使用urlretrieve實現(xiàn)直接遠程下載圖片的示例代碼,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧
    2020-08-08
  • Python實現(xiàn)字符串格式化輸出的方法詳解

    Python實現(xiàn)字符串格式化輸出的方法詳解

    這篇文章主要介紹了Python實現(xiàn)字符串格式化輸出的方法,結(jié)合具體實例形式總結(jié)分析了Python字符串格式化輸出的各種常用操作技巧,需要的朋友可以參考下
    2017-09-09
  • 詳解python ThreadPoolExecutor異常捕獲

    詳解python ThreadPoolExecutor異常捕獲

    本文主要介紹了詳解python ThreadPoolExecutor異常捕獲,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧
    2023-01-01
  • Python迭代器和生成器定義與用法示例

    Python迭代器和生成器定義與用法示例

    這篇文章主要介紹了Python迭代器和生成器定義與用法,結(jié)合實例形式詳細分析了Python迭代器和生成器的概念、原理、定義、使用方法及相關操作注意事項,需要的朋友可以參考下
    2018-02-02
  • python繪制帶有誤差棒條形圖的實現(xiàn)

    python繪制帶有誤差棒條形圖的實現(xiàn)

    本文主要介紹了python繪制帶有誤差棒條形圖的實現(xiàn),文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧
    2023-07-07
  • python-Web-flask-視圖內(nèi)容和模板知識點西寧街

    python-Web-flask-視圖內(nèi)容和模板知識點西寧街

    在本篇文章里小編給大家分享了關于python-Web-flask-視圖內(nèi)容和模板的相關知識點內(nèi)容,有需要的朋友們參考學習下。
    2019-08-08
  • Django如何使用jwt獲取用戶信息

    Django如何使用jwt獲取用戶信息

    這篇文章主要介紹了Django如何使用jwt獲取用戶信息,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下
    2020-04-04

最新評論