Python 圖_系列之基于鄰接矩陣實作廣度、深度優先路徑搜尋算法

圖是一種抽象資料結構，本質和樹結構是一樣的。

圖與樹相比較，圖具有封閉性，可以把樹結構看成是圖結構的前生。在樹結構中，如果把兄弟節點之間或子節點之間橫向連接配接，便建構成一個圖。

樹适合描述從上向下的一對多的資料結構，如公司的組織結構。

圖适合描述更複雜的多對多資料結構，如複雜的群體社交關系。

1. 圖理論

借助計算機解決現實世界中的問題時，除了要存儲現實世界中的資訊，還需要正确地描述資訊之間的關系。

如在開發地圖程式時，需要在計算機中正确模拟出城市與城市、或城市中各道路之間的關系圖。在此基礎上，才有可能通過算法計算出從一個城市到另一個城市、或從指定起點到目标點間的最佳路徑。

類似的還有航班路線圖、火車線路圖、社交交系圖。

圖結構能很好的對現實世界中如上這些資訊之間的複雜關系進行映射。以此可使用算法友善的計算出如航班線路中的最短路徑、如火車線路中的最佳中轉方案，如社交圈中誰與誰關系最好、婚姻網中誰與誰最般配……

1.1 圖的概念

**頂點：**頂點也稱為節點，可認為圖就是頂點組成的集合。頂點本身是有資料含義的，是以頂點都會帶有附加資訊，稱作"有效載荷"。

頂點可以是現實世界中的城市、地名、站名、人……

邊：圖中的邊用來描述頂點之間的關系。邊可以有方向也可以沒有方向，有方向的邊又可分為單向邊和雙向邊。

如下圖（項點1）到（頂點2）之間的邊隻有一方向（箭頭所示為方向），稱為單向邊。類似現實世界中的單向道。

（頂點1）到（頂點2）之間的邊有兩個方向（雙向箭頭），稱為雙向邊。城市與城市之間的關系為雙向邊。

權重：邊上可以附加值資訊，附加的值稱為權重。有權重的邊用來描述一個頂點到另一個頂點的連接配接強度。

如現實生活中的地鐵路線中，權重可以描述兩個車站之間時間長度、公裡數、票價……

邊描述的是頂點之間的關系，權重描述的是連接配接的差異性。

路徑：

先了解現實世界中路徑概念

如：從一個城市開車去另一個城市，就需要先确定好路徑。也就是從出發地到目的地要經過那些城市？要走多少裡程？

可以說路徑是由邊連接配接的頂點組成的序列。因路徑不隻一條，是以，從一個項點到另一個項點的路徑描述也不指一種。

在圖結構中如何計算路徑？

無權重路徑的長度是路徑上的邊數。

有權重路徑的長度是路徑上的邊的權重之和。

如上圖從（頂點1）到（頂點3）的路徑長度為 8。

環：從起點出發，最後又回到起點（終點也是起點）就會形成一個環，環是一種特殊的路徑。如上

(V1, V2, V3, V1)

就是一個環。

圖的類型：

綜上所述，圖可以分為如下幾類：

有向圖：邊有方向的圖稱為有向圖。
無向圖：邊沒有方向的圖稱為無向圖。
權重圖：邊上面有權重資訊的圖稱為權重圖。
無環圖：沒有環的圖被稱為無環圖。
有向無環圖：沒有環的有向圖，簡稱 DAG。

1.2 定義圖

根據圖的特性，圖資料結構中至少要包含兩類資訊：

所有頂點構成集合資訊，這裡用 V 表示（如地圖程式中，所有城市構在頂點集合）。
所有邊構成集合資訊，這裡用 E 表示（城市與城市之間的關系描述）。

如何描述邊？

邊用來表示項點之間的關系。是以一條邊可以包括 3 個中繼資料（起點，終點，權重）。當然，權重是可以省略的，但一般研究圖時，都是指的權重圖。

如果用

表示圖，則

G = (V, E)

。每一條邊可以用二進制組

(fv, ev)

也可以使用三元組

（fv,ev,w）

描述。

fv 表示起點， ev 表示終點。且 fv ， ev 資料必須引用于 V 集合。

如上的圖結構可以描述如下：

# 5 個頂點
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 圖的抽象資料結構

圖的抽象資料描述中至少要有的方法：

Graph ( ) ：用來建立一個新圖。
add_vertex( vert ) ：向圖中添加一個新節點，參數應該是一個節點類型的對象。
add_edge(fv，tv ) ：在 2 個項點之間建立起邊關系。
add_edge(fv，tv，w ) ：在 2 個項點之間建立起一條邊并指定連接配接權重。
find_vertex( key ) : 根據關鍵字 key 在圖中查找頂點。
find_vertexs( ) ：查詢所有頂點資訊。
find_path( fv,tv) ：查找.從一個頂點到另一個頂點之間的路徑。

2. 圖的存儲實作

圖的存儲實作主流有 2 種：鄰接矩陣和連結表，本文主要介紹鄰接矩陣。

2.1 鄰接矩陣

使用二維矩陣（數組）存儲頂點之間的關系。

如

graph[5][5]

可以存儲 5 個頂點的關系資料，行号和列号表示頂點，第 v 行的第 w 列交叉的單元格中的值表示從頂點 v 到頂點 w 的邊的權重，如

grap[2][3]=6

表示 C2 頂點和 D3 頂點的有連接配接（相鄰），權重為 6。

相鄰矩陣的優點就是簡單，可以清晰表示那些頂點是相連的。因不是每兩兩個頂點之間會有連接配接，會導緻大量的空間閑置，稱這種矩陣為”稀疏“的。

隻有當每一個頂點和其它頂點都有關系時，矩陣才會填滿。是以，使用這種結構存儲圖資料，對于關系不是很複雜的圖結構而言，會産生大量的空間浪費。

鄰接矩陣适合表示關系複雜的圖結構，如網際網路上網頁之間的連結、社交圈中人與人之間的社會關系……

2.2 編碼實作鄰接矩陣

因頂點本身有資料含義，需要先定義頂點類型。

頂點類：

"""
節（頂）點類
"""
class Vertex:
    def __init__(self, name, v_id=0):
        # 頂點的編号
        self.v_id = v_id
        # 頂點的名稱
        self.v_name = name
        # 是否被通路過:False 沒有 True:有
        self.visited = False

    # 自我顯示
    def __str__(self):
        return '[編号為 {0}，名稱為 {1} ] 的頂點'.format(self.v_id, self.v_name)

頂點類中

v_id

和

v_name

很好了解。為什麼要添加一個

visited

？

這個變量用來記錄頂點在路徑搜尋過程中是否已經被搜尋過，避免重複搜尋計算。

**圖類：**圖類的方法較多，這裡逐方法介紹。

初始化方法

class Graph:
    """
    nums:相鄰矩陣的大小
    """

    def __init__(self, nums):
        # 一維清單，儲存節點，最多隻能有 nums 個節點
        self.vert_list = []
        # 二維清單，存儲頂點及頂點間的關系(權重)
        # 初始權重為 0 ，表示節點與節點之間還沒有建立起關系
        self.matrix = [[0] * nums for _ in range(nums)]
        # 頂點個數
        self.v_nums = 0
        # 使用隊列模拟隊列或棧，用于廣度、深度優先搜尋算法
        self.queue_stack = []
        # 儲存搜尋到的路徑
        self.searchPath = []
        
    # 暫省略……

初始化方法用來初始化圖中的資料類型：

一維清單 vert_list 儲存所有頂點資料。
二維清單 matrix 儲存頂點與頂點之間的關系資料。
queue_stack 使用清單模拟隊列或棧，用于後續的廣度搜尋和深度搜尋。

怎麼使用清單模拟隊列或棧？

清單有
append() 、 pop() 2 個很價值的方法。 append() 用來向清單中添加資料，且每次都是從清單最後面添加。 pop() 預設從清單最後面删除且彈出資料， pop(參數)
可以提供索引值用來從指定位置删除且彈出資料。

使用
append() 和 pop()
方法就能模拟棧，從同一個地方進出資料。

使用
append() 和 pop(0) 方法就能模拟隊列，從後面添加資料，從最前面擷取資料
searchPath ：用來儲存使用廣度或深度優先路徑搜尋中的結果。

添加新節（頂）點方法：

"""
    添加新頂點
    """
    def add_vertex(self, vert):
        if vert in self.vert_list:
            # 已經存在
            return
        if self.v_nums >= len(self.matrix):
            # 超過相鄰矩陣所能存儲的節點上限
            return
        # 頂點的編号内部生成
        vert.v_id = self.v_nums
        self.vert_list.append(vert)
        # 數量增一
        self.v_nums += 1

上述方法注意一點，節點的編号由圖内部邏輯提供，便于節點編号順序的統一。

添加邊方法

此方法是鄰接矩陣表示法的核心邏輯。

'''
    添加節點與節點之間的邊，
    如果是無權重圖，統一設定為 1 
    '''
    def add_edge(self, from_v, to_v):
        # 如果節點不存在
        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 節點的編号為行号，to_v 節點的編号為列号
        self.matrix[from_v.v_id][to_v.v_id] = 1

    '''
    添加有權重的邊
    '''
    def add_edge(self, from_v, to_v, weight):
        # 如果節點不存在
        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 節點的編号為行号，to_v 節點的編号為列号
        self.matrix[from_v.v_id][to_v.v_id] = weight

添加邊資訊的方法有 2 個，一個用來添加無權重邊，一個用來添加有權重的邊。

查找某節點

使用線性查找法從節點集合中查找某一個節點。

'''
    根據節點編号傳回節點
    '''
    def find_vertex(self, v_id):
        if v_id >= 0 or v_id <= self.v_nums:
            # 節點編号必須存在
            return [tmp_v for tmp_v in self.vert_list if tmp_v.v_id == v_id][0]

查詢所有節點

'''
    輸出所有頂點資訊
    '''
    def find_only_vertexes(self):
        for tmp_v in self.vert_list:
            print(tmp_v)

此方法僅為了查詢友善。

查詢節點之間的關系

'''
    疊代節點與節點之間的關系（邊）
    '''
    def find_vertexes(self):
        for tmp_v in self.vert_list:
            edges = self.matrix[tmp_v.v_id]
            for col in range(len(edges)):
                w = edges[col]
                if w != 0:
                    print(tmp_v, '和', self.vert_list[col], '的權重為：', w)

測試代碼：

if __name__ == "__main__":
    # 初始化圖對象
    g = Graph(5)
    # 添加頂點
    for _ in range(len(g.matrix)):
        v_name = input("頂點的名稱（ q 為退出）：")
        if v_name == 'q':
            break
        v = Vertex(v_name)
        g.add_vertex(v)

    # 節點之間的關系
    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])
    # 輸出頂點及邊a
    print("-----------頂點與頂點關系--------------")
    g.find_vertexes()
    '''
    輸出結果：
    頂點的名稱（ q 為退出）：A
    頂點的名稱（ q 為退出）：B
    頂點的名稱（ q 為退出）：C
    頂點的名稱（ q 為退出）：D
    頂點的名稱（ q 為退出）：E
    -----------頂點與頂點關系--------------
    [編号為 0，名稱為 A ] 的頂點 和 [編号為 1，名稱為 B ] 的頂點 的權重為： 3
    [編号為 0，名稱為 A ] 的頂點 和 [編号為 3，名稱為 D ] 的頂點 的權重為： 5
    [編号為 1，名稱為 B ] 的頂點 和 [編号為 2，名稱為 C ] 的頂點 的權重為： 4
    [編号為 2，名稱為 C ] 的頂點 和 [編号為 3，名稱為 D ] 的頂點 的權重為： 6
    [編号為 2，名稱為 C ] 的頂點 和 [編号為 4，名稱為 E ] 的頂點 的權重為： 1
    [編号為 3，名稱為 D ] 的頂點 和 [編号為 4，名稱為 E ] 的頂點 的權重為： 2
    [編号為 4，名稱為 E ] 的頂點 和 [編号為 1，名稱為 B ] 的頂點 的權重為： 7
    '''

3. 搜尋路徑

在圖中經常做的操作，就是查找從一個頂點到另一個頂點的路徑。如怎麼查找到 A0 到 E4 之間的路徑長度：

從人的直覺思維角度查找一下，可以找到如下路徑：

{A0，B1，C2，E4} 路徑長度為 8。
{A0，D3，E4} 路徑長度為 7。
{A0，B1，C2，D3，E4} 路徑長度為 15。

人的思維是知識性、直覺性思維，在路徑查找時不存在所謂的嘗試或碰壁問題。而計算機是試探性思維，就會出現這條路不通，再找另一條路的現象。

是以路徑算法中常常會以錯誤為代價，在查找過程中會走一些彎路。常用的路徑搜尋算法有 2 種：

廣度優先搜尋。
深度優先搜尋。

3.1 廣度優先搜尋

先看一下廣度優先搜尋的示意圖：

廣度優先搜尋的基本思路：

确定出發點，本案例是 A0 頂點。
以出發點相鄰的頂點為候選點，并存儲至隊列。
從隊列中每拿出一個頂點後，再把與此頂點相鄰的其它頂點做為候選點存儲于隊列。
不停重複上述過程，至到找到目标頂點或隊列為空。

在如上的有向權重圖中，使用廣度搜尋到的路徑與候選節點進入隊列的先後順序有關系。如第 1 步确定候選節點時

B1

和

D3

誰先進入隊列，對于後面的查找也會有影響。

上圖使用廣度搜尋可找到

A0~E4

路徑是：

{A0，B1，D3，C2，E4}

其實

{A0，B1，C2，E4}

也是一條有效路徑，有可能搜尋不出來，這裡因為搜尋到

B1

後不會馬上搜尋

C2

，因為

B3

先于

C2

進入，在有向權重圖中，廣度優先搜尋算法隻能保證找到路徑，而不能儲存找到最短路徑。

無向無權重圖中，廣度優先搜尋可以搜尋到頂點之間的最短路徑。

編碼實作廣度優先搜尋：

廣度優先搜尋需要借助隊列臨時存儲選節點，本文使用清單模拟隊列。

在圖類中實作廣度優先搜尋算法的方法：

class Graph():
    
    # 省略其它代碼

    '''
    廣度優先搜尋算法
    '''
    def bfs(self, from_v, to_v):
        # 查找與 fv 相鄰的節點
        self.find_neighbor(from_v)
        # 臨時路徑
        lst_path = [from_v]
        # 重複條件：隊列不為空
        while len(self.queue_stack) != 0:
            # 從隊列中一個節點（模拟隊列）
            tmp_v = self.queue_stack.pop(0)
            # 添加到清單中
            lst_path.append(tmp_v)
            # 是不是目标節點
            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)
    '''
    查找某一節點的相鄰節點，并添加到隊列（棧）中
    '''
    def find_neighbor(self, find_v):
        if find_v.visited:
            return
        find_v.visited = True
        # 找到儲存 find_v 節點相鄰節點的清單
        lst = self.matrix[find_v.v_id]
        for idx in range(len(lst)):
            if lst[idx] != 0:
                # 權重不為 0 ，可判斷相鄰
                self.queue_stack.append(self.vert_list[idx])

廣度優先搜尋過程中，需要随時擷取與目前節點相鄰的節點，

find_neighbor()

方法的作用就是用來把目前節點的相鄰節點壓入隊列中。

測試廣度優先搜尋算法：

if __name__ == "__main__":
    # 初始化圖對象
    g = Graph(5)
    # 添加頂點
    for _ in range(len(g.matrix)):
        v_name = input("頂點的名稱（ q 為退出）：")
        if v_name == 'q':
            break
        v = Vertex(v_name)
        g.add_vertex(v)

    # 節點之間的關系
    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("----------- 廣度優先路徑搜尋--------------")
    f_v = g.find_vertex(0)
    t_v = g.find_vertex(4)
    g.bfs(f_v,t_v)
    '''
    輸出結果
    頂點的名稱（ q 為退出）：A
    頂點的名稱（ q 為退出）：B
    頂點的名稱（ q 為退出）：C
    頂點的名稱（ q 為退出）：D
    頂點的名稱（ q 為退出）：E
    -----------頂點與頂點關系--------------
    [編号為 0，名稱為 A ] 的頂點 和 [編号為 1，名稱為 B ] 的頂點 的權重為： 3
    [編号為 0，名稱為 A ] 的頂點 和 [編号為 3，名稱為 D ] 的頂點 的權重為： 5
    [編号為 1，名稱為 B ] 的頂點 和 [編号為 2，名稱為 C ] 的頂點 的權重為： 4
    [編号為 2，名稱為 C ] 的頂點 和 [編号為 3，名稱為 D ] 的頂點 的權重為： 6
    [編号為 2，名稱為 C ] 的頂點 和 [編号為 4，名稱為 E ] 的頂點 的權重為： 1
    [編号為 3，名稱為 D ] 的頂點 和 [編号為 4，名稱為 E ] 的頂點 的權重為： 2
    [編号為 4，名稱為 E ] 的頂點 和 [編号為 1，名稱為 B ] 的頂點 的權重為： 7
    ----------- 廣度優先路徑搜尋--------------
    找到一條路徑 [0, 1, 3, 2, 4]
    找到一條路徑 [0, 1, 3, 2, 3, 4]
    '''

本案例僅顯示從一個頂點到另一個頂點的搜尋過程，路徑距離計算不在此計算。

使用遞歸實作廣度優先搜尋算法：

'''
    遞歸方式實作廣度搜尋
    '''
    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 深度優先搜尋算法

先看一下深度優先算法的示意圖。

深度優先搜尋算法與廣度優先搜尋算法不同之處：候選節點是放在棧中的。因棧是先進後出，是以，搜尋到的節點順序不一樣。

使用循環實作深度優先搜尋算法：

深度優先搜尋算法需要用到棧，本文使用清單模拟。

'''
    深度優先搜尋算法
    使用棧存儲下一個需要查找的節點
    '''
    def dfs(self, from_v, to_v):
        # 查找與 from_v 相鄰的節點
        self.find_neighbor(from_v)
        # 臨時路徑
        lst_path = [from_v]
        # 重複條件：棧不為空
        while len(self.queue_stack) != 0:
            # 從棧中取一個節點（模拟棧）
            tmp_v = self.queue_stack.pop()
            # 添加到清單中
            lst_path.append(tmp_v)
            # 是不是目标節點
            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__":
    # 初始化圖對象
    g = Graph(5)
    # 添加頂點
    for _ in range(len(g.matrix)):
        v_name = input("頂點的名稱（ q 為退出）：")
        if v_name == 'q':
            break
        v = Vertex(v_name)
        g.add_vertex(v)

    # 節點之間的關系
    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])
    # 輸出頂點及邊a
    print("-----------頂點與頂點關系--------------")
    g.find_vertexes()

    print("----------- 深度優先路徑搜尋--------------")
    f_v = g.find_vertex(0)
    t_v = g.find_vertex(4)
    g.dfs(f_v, t_v)
    '''
    輸出結果
    頂點的名稱（ q 為退出）：A
    頂點的名稱（ q 為退出）：B
    頂點的名稱（ q 為退出）：C
    頂點的名稱（ q 為退出）：D
    頂點的名稱（ q 為退出）：E
    -----------頂點與頂點關系--------------
    [編号為 0，名稱為 A ] 的頂點 和 [編号為 1，名稱為 B ] 的頂點 的權重為： 3
    [編号為 0，名稱為 A ] 的頂點 和 [編号為 3，名稱為 D ] 的頂點 的權重為： 5
    [編号為 1，名稱為 B ] 的頂點 和 [編号為 2，名稱為 C ] 的頂點 的權重為： 4
    [編号為 2，名稱為 C ] 的頂點 和 [編号為 3，名稱為 D ] 的頂點 的權重為： 6
    [編号為 2，名稱為 C ] 的頂點 和 [編号為 4，名稱為 E ] 的頂點 的權重為： 1
    [編号為 3，名稱為 D ] 的頂點 和 [編号為 4，名稱為 E ] 的頂點 的權重為： 2
    [編号為 4，名稱為 E ] 的頂點 和 [編号為 1，名稱為 B ] 的頂點 的權重為： 7
    ----------- 深度優先路徑搜尋--------------
    找到一條路徑: [0, 3, 4]
    找到一條路徑: [0, 3, 1, 2, 4]
    '''

使用遞歸實作深度優先搜尋算法：

'''
    遞歸實作深度搜尋算法
    '''
    def def_dg(self, from_v, to_v):
        self.searchPath.append(from_v)
        if from_v.v_id != to_v.v_id:
            # 查找與 from_v 節點相連的子節點
            lst = self.find_neighbor_(from_v)
            if lst is not None:
                for tmp_v in lst[::-1]:
                    self.def_dg(tmp_v, to_v)
    """
    查找某一節點的相鄰節點，以清單方式傳回
    """
    def find_neighbor_(self, find_v):
        if find_v.visited:
            return
        find_v.visited = True
        # 查找與 find_v 節點相鄰的節點
        lst = self.matrix[find_v.v_id]
        return [self.vert_list[idx] for idx in range(len(lst)) if lst[idx] != 0]

遞歸實作時，不需要使用全局棧，隻需要獲到目前節點的相鄰節點便可。

Python 圖_系列之基于鄰接矩陣實作廣度、深度優先路徑搜尋算法

1. 圖理論

1.1 圖的概念

1.2 定義圖

1.3 圖的抽象資料結構

2. 圖的存儲實作

2.1 鄰接矩陣

2.2 編碼實作鄰接矩陣

3. 搜尋路徑

3.1 廣度優先搜尋

3.2 深度優先搜尋算法

4. 總結

繼續閱讀

來自python的【條件控制/語句循環/break/continue/else/pass】一、條件控制二、語句循環

無法解析的外部符号 wmain，該符号在函數 "void cdecl mainCRTStartupHelper(struct HINSTANCE *,unsigned short con......

TestLink導出用例轉換工具(XML2Excel)

YAML簡介和PyYAML安全操作YAML支援的類型YAML的優點：yaml的基本文法python操作

Small tricks

libsvm for python 安裝

學習軟體測試基礎測試第七天

Zeppelin 配置通路 REST APIApache Zeppelin Configuration REST API

【Torch】最簡潔logging使用指南

27. Remove Element(清單)題目代碼

Cloud Studio初體驗

使用 ctypes 進行 Python 和 C 的混合程式設計

【python】【資料處理】畫多元資料分布圖

【python】netconf協定對接管理裝置

「Python 網絡自動化」NETCONF —— Python 使用 NETCONF 管理配置 H3C 網絡裝置

在python中建立excel并寫入