Python實(shí)現(xiàn)圖的廣度和深度優(yōu)先路徑搜索算法

更新時(shí)間：2022年04月25日 10:29:21 作者：一枚大果殼

圖是一種抽象數(shù)據(jù)結(jié)構(gòu)，本質(zhì)和樹結(jié)構(gòu)是一樣的。圖與樹相比較，圖具有封閉性，可以把樹結(jié)構(gòu)看成是圖結(jié)構(gòu)的前生。本文將利用Python實(shí)現(xiàn)圖的廣度和深度優(yōu)先路徑搜索算法，感興趣的可以學(xué)習(xí)一下

前言

圖是一種抽象數(shù)據(jù)結(jié)構(gòu)，本質(zhì)和樹結(jié)構(gòu)是一樣的。

圖與樹相比較，圖具有封閉性，可以把樹結(jié)構(gòu)看成是圖結(jié)構(gòu)的前生。在樹結(jié)構(gòu)中，如果把兄弟節(jié)點(diǎn)之間或子節(jié)點(diǎn)之間橫向連接，便構(gòu)建成一個(gè)圖。

樹適合描述從上向下的一對(duì)多的數(shù)據(jù)結(jié)構(gòu)，如公司的組織結(jié)構(gòu)。

圖適合描述更復(fù)雜的多對(duì)多數(shù)據(jù)結(jié)構(gòu)，如復(fù)雜的群體社交關(guān)系。

1. 圖理論

借助計(jì)算機(jī)解決現(xiàn)實(shí)世界中的問題時(shí)，除了要存儲(chǔ)現(xiàn)實(shí)世界中的信息，還需要正確地描述信息之間的關(guān)系。

如在開發(fā)地圖程序時(shí)，需要在計(jì)算機(jī)中正確模擬出城市與城市、或城市中各道路之間的關(guān)系圖。在此基礎(chǔ)上，才有可能通過算法計(jì)算出從一個(gè)城市到另一個(gè)城市、或從指定起點(diǎn)到目標(biāo)點(diǎn)間的最佳路徑。

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

圖結(jié)構(gòu)能很好的對(duì)現(xiàn)實(shí)世界中如上這些信息之間的復(fù)雜關(guān)系進(jìn)行映射。以此可使用算法方便的計(jì)算出如航班線路中的最短路徑、如火車線路中的最佳中轉(zhuǎn)方案，如社交圈中誰與誰關(guān)系最好、婚姻網(wǎng)中誰與誰最般配……

1.1 圖的概念

頂點(diǎn)：頂點(diǎn)也稱為節(jié)點(diǎn)，可認(rèn)為圖就是頂點(diǎn)組成的集合。頂點(diǎn)本身是有數(shù)據(jù)含義的，所以頂點(diǎn)都會(huì)帶有附加信息，稱作"有效載荷"。

頂點(diǎn)可以是現(xiàn)實(shí)世界中的城市、地名、站名、人……

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

如下圖（項(xiàng)點(diǎn)1）到（頂點(diǎn)2）之間的邊只有一方向（箭頭所示為方向），稱為單向邊。類似現(xiàn)實(shí)世界中的單向道。

（頂點(diǎn)1）到（頂點(diǎn)2）之間的邊有兩個(gè)方向（雙向箭頭），稱為雙向邊。 城市與城市之間的關(guān)系為雙向邊。

權(quán)重： 邊上可以附加值信息，附加的值稱為權(quán)重。有權(quán)重的邊用來描述一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的連接強(qiáng)度。

如現(xiàn)實(shí)生活中的地鐵路線中，權(quán)重可以描述兩個(gè)車站之間時(shí)間長度、公里數(shù)、票價(jià)……

邊描述的是頂點(diǎn)之間的關(guān)系，權(quán)重描述的是連接的差異性。

路徑：

先了解現(xiàn)實(shí)世界中路徑概念

如：從一個(gè)城市開車去另一個(gè)城市，就需要先確定好路徑。也就是 從出發(fā)地到目的地要經(jīng)過那些城市？要走多少里程？

可以說路徑是由邊連接的頂點(diǎn)組成的序列。因路徑不只一條，所以，從一個(gè)項(xiàng)點(diǎn)到另一個(gè)項(xiàng)點(diǎn)的路徑描述也不指一種。

在圖結(jié)構(gòu)中如何計(jì)算路徑？

無權(quán)重路徑的長度是路徑上的邊數(shù)。
有權(quán)重路徑的長度是路徑上的邊的權(quán)重之和。

如上圖從（頂點(diǎn)1）到（頂點(diǎn)3）的路徑長度為 8。

環(huán)： 從起點(diǎn)出發(fā)，最后又回到起點(diǎn)（終點(diǎn)也是起點(diǎn)）就會(huì)形成一個(gè)環(huán)，環(huán)是一種特殊的路徑。如上 (V1, V2, V3, V1) 就是一個(gè)環(huán)。

圖的類型：

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

有向圖： 邊有方向的圖稱為有向圖。
無向圖： 邊沒有方向的圖稱為無向圖。
加權(quán)圖： 邊上面有權(quán)重信息的圖稱為加權(quán)圖。
無環(huán)圖： 沒有環(huán)的圖被稱為無環(huán)圖。
有向無環(huán)圖： 沒有環(huán)的有向圖，簡稱 DAG。

1.2 定義圖

根據(jù)圖的特性，圖數(shù)據(jù)結(jié)構(gòu)中至少要包含兩類信息：

所有頂點(diǎn)構(gòu)成集合信息，這里用 V 表示（如地圖程序中，所有城市構(gòu)在頂點(diǎn)集合）。

所有邊構(gòu)成集合信息，這里用 E 表示（城市與城市之間的關(guān)系描述）。

如何描述邊？

邊用來表示項(xiàng)點(diǎn)之間的關(guān)系。所以一條邊可以包括 3 個(gè)元數(shù)據(jù)（起點(diǎn)，終點(diǎn)，權(quán)重）。當(dāng)然，權(quán)重是可以省略的，但一般研究圖時(shí)，都是指的加權(quán)圖。

如果用 G 表示圖，則 G = (V, E)。每一條邊可以用二元組 (fv, ev) 也可以使用三元組 （fv,ev,w） 描述。

fv 表示起點(diǎn)，ev 表示終點(diǎn)。且 fv，ev 數(shù)據(jù)必須引用于 V 集合。

如上的圖結(jié)構(gòu)可以描述如下：

# 5 個(gè)頂點(diǎn)
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 圖的抽象數(shù)據(jù)結(jié)構(gòu)

圖的抽象數(shù)據(jù)描述中至少要有的方法：

Graph ( ) ：用來創(chuàng)建一個(gè)新圖。
add_vertex( vert )：向圖中添加一個(gè)新節(jié)點(diǎn)，參數(shù)應(yīng)該是一個(gè)節(jié)點(diǎn)類型的對(duì)象。
add_edge(fv，tv )：在 2 個(gè)項(xiàng)點(diǎn)之間建立起邊關(guān)系。
add_edge(fv，tv，w )：在 2 個(gè)項(xiàng)點(diǎn)之間建立起一條邊并指定連接權(quán)重。
find_vertex( key ): 根據(jù)關(guān)鍵字 key 在圖中查找頂點(diǎn)。
find_vertexs( )：查詢所有頂點(diǎn)信息。
find_path( fv,tv)：查找.從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)之間的路徑。

2. 圖的存儲(chǔ)實(shí)現(xiàn)

圖的存儲(chǔ)實(shí)現(xiàn)主流有 2 種：鄰接矩陣和鏈接表，本文主要介紹鄰接矩陣。

2.1 鄰接矩陣

使用二維矩陣（數(shù)組）存儲(chǔ)頂點(diǎn)之間的關(guān)系。

如 graph[5][5] 可以存儲(chǔ) 5 個(gè)頂點(diǎn)的關(guān)系數(shù)據(jù)，行號(hào)和列號(hào)表示頂點(diǎn)，第 v 行的第 w 列交叉的單元格中的值表示從頂點(diǎn) v 到頂點(diǎn) w 的邊的權(quán)重，如 grap[2][3]=6 表示 C2 頂點(diǎn)和 D3 頂點(diǎn)的有連接（相鄰），權(quán)重為 6

相鄰矩陣的優(yōu)點(diǎn)就是簡單，可以清晰表示那些頂點(diǎn)是相連的。因不是每兩兩個(gè)頂點(diǎn)之間會(huì)有連接，會(huì)導(dǎo)致大量的空間閑置，稱這種矩陣為”稀疏“的。

只有當(dāng)每一個(gè)頂點(diǎn)和其它頂點(diǎn)都有關(guān)系時(shí)，矩陣才會(huì)填滿。所以，使用這種結(jié)構(gòu)存儲(chǔ)圖數(shù)據(jù)，對(duì)于關(guān)系不是很復(fù)雜的圖結(jié)構(gòu)而言，會(huì)產(chǎn)生大量的空間浪費(fèi)。

鄰接矩陣適合表示關(guān)系復(fù)雜的圖結(jié)構(gòu)，如互聯(lián)網(wǎng)上網(wǎng)頁之間的鏈接、社交圈中人與人之間的社會(huì)關(guān)系……

2.2 編碼實(shí)現(xiàn)鄰接矩陣

因頂點(diǎn)本身有數(shù)據(jù)含義，需要先定義頂點(diǎn)類型。

頂點(diǎn)類：

"""
節(jié)（頂）點(diǎn)類
"""
class Vertex:
    def __init__(self, name, v_id=0):
        # 頂點(diǎn)的編號(hào)
        self.v_id = v_id
        # 頂點(diǎn)的名稱
        self.v_name = name
        # 是否被訪問過:False 沒有 True:有
        self.visited = False

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

頂點(diǎn)類中 v_id 和 v_name 很好理解。為什么要添加一個(gè) visited？

這個(gè)變量用來記錄頂點(diǎn)在路徑搜索過程中是否已經(jīng)被搜索過，避免重復(fù)搜索計(jì)算。

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

初始化方法

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

    def __init__(self, nums):
        # 一維列表，保存節(jié)點(diǎn)，最多只能有 nums 個(gè)節(jié)點(diǎn)
        self.vert_list = []
        # 二維列表，存儲(chǔ)頂點(diǎn)及頂點(diǎn)間的關(guān)系(權(quán)重)
        # 初始權(quán)重為 0 ，表示節(jié)點(diǎn)與節(jié)點(diǎn)之間還沒有建立起關(guān)系
        self.matrix = [[0] * nums for _ in range(nums)]
        # 頂點(diǎn)個(gè)數(shù)
        self.v_nums = 0
        # 使用隊(duì)列模擬隊(duì)列或棧，用于廣度、深度優(yōu)先搜索算法
        self.queue_stack = []
        # 保存搜索到的路徑
        self.searchPath = []
        
    # 暫省略……

初始化方法用來初始化圖中的數(shù)據(jù)類型：

一維列表 vert_list 保存所有頂點(diǎn)數(shù)據(jù)。

二維列表 matrix 保存頂點(diǎn)與頂點(diǎn)之間的關(guān)系數(shù)據(jù)。

queue_stack 使用列表模擬隊(duì)列或棧，用于后續(xù)的廣度搜索和深度搜索。

怎么使用列表模擬隊(duì)列或棧？

列表有 append()、pop() 2 個(gè)很價(jià)值的方法。

append() 用來向列表中添加數(shù)據(jù)，且每次都是從列表最后面添加。

pop() 默認(rèn)從列表最后面刪除且彈出數(shù)據(jù)， pop(參數(shù)) 可以提供索引值用來從指定位置刪除且彈出數(shù)據(jù)。

使用 append() 和 pop() 方法就能模擬棧，從同一個(gè)地方進(jìn)出數(shù)據(jù)。

使用 append() 和 pop(0) 方法就能模擬隊(duì)列，從后面添加數(shù)據(jù)，從最前面獲取數(shù)據(jù)

searchPath ：用來保存使用廣度或深度優(yōu)先路徑搜索中的結(jié)果。

添加新節(jié)（頂）點(diǎn)方法：

    """
    添加新頂點(diǎn)
    """
    def add_vertex(self, vert):
        if vert in self.vert_list:
            # 已經(jīng)存在
            return
        if self.v_nums >= len(self.matrix):
            # 超過相鄰矩陣所能存儲(chǔ)的節(jié)點(diǎn)上限
            return
        # 頂點(diǎn)的編號(hào)內(nèi)部生成
        vert.v_id = self.v_nums
        self.vert_list.append(vert)
        # 數(shù)量增一
        self.v_nums += 1

上述方法注意一點(diǎn)，節(jié)點(diǎn)的編號(hào)由圖內(nèi)部邏輯提供，便于節(jié)點(diǎn)編號(hào)順序的統(tǒng)一。

添加邊方法

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

  '''
    添加節(jié)點(diǎn)與節(jié)點(diǎn)之間的邊，
    如果是無權(quán)重圖，統(tǒng)一設(shè)定為 1 
    '''
    def add_edge(self, from_v, to_v):
        # 如果節(jié)點(diǎn)不存在
        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 節(jié)點(diǎn)的編號(hào)為行號(hào)，to_v 節(jié)點(diǎn)的編號(hào)為列號(hào)
        self.matrix[from_v.v_id][to_v.v_id] = 1

    '''
    添加有權(quán)重的邊
    '''
    def add_edge(self, from_v, to_v, weight):
        # 如果節(jié)點(diǎn)不存在
        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 節(jié)點(diǎn)的編號(hào)為行號(hào)，to_v 節(jié)點(diǎn)的編號(hào)為列號(hào)
        self.matrix[from_v.v_id][to_v.v_id] = weight

添加邊信息的方法有 2 個(gè)，一個(gè)用來添加無權(quán)重邊，一個(gè)用來添加有權(quán)重的邊。

查找某節(jié)點(diǎn)

使用線性查找法從節(jié)點(diǎn)集合中查找某一個(gè)節(jié)點(diǎn)。

    '''
    根據(jù)節(jié)點(diǎn)編號(hào)返回節(jié)點(diǎn)
    '''
    def find_vertex(self, v_id):
        if v_id >= 0 or v_id <= self.v_nums:
            # 節(jié)點(diǎn)編號(hào)必須存在
            return [tmp_v for tmp_v in self.vert_list if tmp_v.v_id == v_id][0]

查詢所有節(jié)點(diǎn)

  '''
    輸出所有頂點(diǎn)信息
    '''
    def find_only_vertexes(self):
        for tmp_v in self.vert_list:
            print(tmp_v)

此方法僅為了查詢方便。

查詢節(jié)點(diǎn)之間的關(guān)系

    '''
    迭代節(jié)點(diǎn)與節(jié)點(diǎn)之間的關(guān)系（邊）
    '''
    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], '的權(quán)重為：', w)

測試代碼：

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

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

3. 搜索路徑

在圖中經(jīng)常做的操作，就是查找從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的路徑。如怎么查找到 A0 到 E4 之間的路徑長度：

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

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

人的思維是知識(shí)性、直觀性思維，在路徑查找時(shí)不存在所謂的嘗試或碰壁問題。而計(jì)算機(jī)是試探性思維，就會(huì)出現(xiàn)這條路不通，再找另一條路的現(xiàn)象。

所以路徑算法中常常會(huì)以錯(cuò)誤為代價(jià)，在查找過程中會(huì)走一些彎路。常用的路徑搜索算法有 2 種：

廣度優(yōu)先搜索
深度優(yōu)先搜索

3.1 廣度優(yōu)先搜索

先看一下廣度優(yōu)先搜索的示意圖：

廣度優(yōu)先搜索的基本思路：

確定出發(fā)點(diǎn)，本案例是 A0 頂點(diǎn)。
以出發(fā)點(diǎn)相鄰的頂點(diǎn)為候選點(diǎn)，并存儲(chǔ)至隊(duì)列。
從隊(duì)列中每拿出一個(gè)頂點(diǎn)后，再把與此頂點(diǎn)相鄰的其它頂點(diǎn)做為候選點(diǎn)存儲(chǔ)于隊(duì)列。
不停重復(fù)上述過程，至到找到目標(biāo)頂點(diǎn)或隊(duì)列為空。

使用廣度搜索到的路徑與候選節(jié)點(diǎn)進(jìn)入隊(duì)列的先后順序有關(guān)系。如第 1 步確定候選節(jié)點(diǎn)時(shí) B1 和 D3 誰先進(jìn)入隊(duì)列，對(duì)于后面的查找也會(huì)有影響。

上圖使用廣度搜索可找到 A0~E4 路徑是：

{A0，B1，D3，C2，E4}

其實(shí) {A0，B1，C2，E4} 也是一條有效路徑，有可能搜索不出來，這里因?yàn)樗阉鞯?nbsp;B1 后不會(huì)馬上搜索 C2，因?yàn)?nbsp;B3 先于 C2 進(jìn)入，廣度優(yōu)先搜索算法只能保證找到路徑，而不能保存找到最佳路徑。

編碼實(shí)現(xiàn)廣度優(yōu)先搜索：

廣度優(yōu)先搜索需要借助隊(duì)列臨時(shí)存儲(chǔ)選節(jié)點(diǎn)，本文使用列表模擬隊(duì)列。

在圖類中實(shí)現(xiàn)廣度優(yōu)先搜索算法的方法：

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

    '''
    廣度優(yōu)先搜索算法
    '''
    def bfs(self, from_v, to_v):
        # 查找與 fv 相鄰的節(jié)點(diǎn)
        self.find_neighbor(from_v)
        # 臨時(shí)路徑
        lst_path = [from_v]
        # 重復(fù)條件：隊(duì)列不為空
        while len(self.queue_stack) != 0:
            # 從隊(duì)列中一個(gè)節(jié)點(diǎn)（模擬隊(duì)列）
            tmp_v = self.queue_stack.pop(0)
            # 添加到列表中
            lst_path.append(tmp_v)
            # 是不是目標(biāo)節(jié)點(diǎn)
            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)
    '''
    查找某一節(jié)點(diǎn)的相鄰節(jié)點(diǎn)，并添加到隊(duì)列（棧）中
    '''
    def find_neighbor(self, find_v):
        if find_v.visited:
            return
        find_v.visited = True
        # 找到保存 find_v 節(jié)點(diǎn)相鄰節(jié)點(diǎn)的列表
        lst = self.matrix[find_v.v_id]
        for idx in range(len(lst)):
            if lst[idx] != 0:
                # 權(quán)重不為 0 ，可判斷相鄰
                self.queue_stack.append(self.vert_list[idx])

廣度優(yōu)先搜索過程中，需要隨時(shí)獲取與當(dāng)前節(jié)點(diǎn)相鄰的節(jié)點(diǎn)，find_neighbor() 方法的作用就是用來把當(dāng)前節(jié)點(diǎn)的相鄰節(jié)點(diǎn)壓入隊(duì)列中。

測試廣度優(yōu)先搜索算法：

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

    # 節(jié)點(diǎn)之間的關(guān)系
    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("----------- 廣度優(yōu)先路徑搜索--------------")
    f_v = g.find_vertex(0)
    t_v = g.find_vertex(4)
    g.bfs(f_v,t_v)
    '''
    輸出結(jié)果
    頂點(diǎn)的名稱（ q 為退出）：A
    頂點(diǎn)的名稱（ q 為退出）：B
    頂點(diǎn)的名稱（ q 為退出）：C
    頂點(diǎn)的名稱（ q 為退出）：D
    頂點(diǎn)的名稱（ q 為退出）：E


    ----------- 廣度優(yōu)先路徑搜索--------------
    找到一條路徑 [0, 1, 3, 2, 4]
    找到一條路徑 [0, 1, 3, 2, 3, 4]
    '''

使用遞歸實(shí)現(xiàn)廣度優(yōu)先搜索算法：

   '''
    遞歸方式實(shí)現(xiàn)廣度搜索
    '''
    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 深度優(yōu)先搜索算法

先看一下深度優(yōu)先算法的示意圖。

深度優(yōu)先搜索算法與廣度優(yōu)先搜索算法不同之處：候選節(jié)點(diǎn)是放在棧中的。因棧是先進(jìn)后出，所以，搜索到的節(jié)點(diǎn)順序不一樣。

使用循環(huán)實(shí)現(xiàn)深度優(yōu)先搜索算法：

深度優(yōu)先搜索算法需要用到棧，本文使用列表模擬。

    '''
    深度優(yōu)先搜索算法
    使用棧存儲(chǔ)下一個(gè)需要查找的節(jié)點(diǎn)
    '''
    def dfs(self, from_v, to_v):
        # 查找與 from_v 相鄰的節(jié)點(diǎn)
        self.find_neighbor(from_v)
        # 臨時(shí)路徑
        lst_path = [from_v]
        # 重復(fù)條件：棧不為空
        while len(self.queue_stack) != 0:
            # 從棧中取一個(gè)節(jié)點(diǎn)（模擬棧）
            tmp_v = self.queue_stack.pop()
            # 添加到列表中
            lst_path.append(tmp_v)
            # 是不是目標(biāo)節(jié)點(diǎn)
            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__":
    # 初始化圖對(duì)象
    g = Graph(5)
    # 添加頂點(diǎn)
    for _ in range(len(g.matrix)):
        v_name = input("頂點(diǎn)的名稱（ q 為退出）：")
        if v_name == 'q':
            break
        v = Vertex(v_name)
        g.add_vertex(v)

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

    print("----------- 深度優(yōu)先路徑搜索--------------")
    f_v = g.find_vertex(0)
    t_v = g.find_vertex(4)
    g.dfs(f_v, t_v)
    '''
    輸出結(jié)果
    頂點(diǎn)的名稱（ q 為退出）：A
    頂點(diǎn)的名稱（ q 為退出）：B
    頂點(diǎn)的名稱（ q 為退出）：C
    頂點(diǎn)的名稱（ q 為退出）：D
    頂點(diǎn)的名稱（ q 為退出）：E
    -----------頂點(diǎn)與頂點(diǎn)關(guān)系--------------
[編號(hào)為 0，名稱為 A ] 的頂點(diǎn) 和 [編號(hào)為 1，名稱為 B ] 的頂點(diǎn) 的權(quán)重為： 3
[編號(hào)為 0，名稱為 A ] 的頂點(diǎn) 和 [編號(hào)為 3，名稱為 D ] 的頂點(diǎn) 的權(quán)重為： 5
[編號(hào)為 1，名稱為 B ] 的頂點(diǎn) 和 [編號(hào)為 2，名稱為 C ] 的頂點(diǎn) 的權(quán)重為： 4
[編號(hào)為 2，名稱為 C ] 的頂點(diǎn) 和 [編號(hào)為 3，名稱為 D ] 的頂點(diǎn) 的權(quán)重為： 6
[編號(hào)為 2，名稱為 C ] 的頂點(diǎn) 和 [編號(hào)為 4，名稱為 E ] 的頂點(diǎn) 的權(quán)重為： 1
[編號(hào)為 3，名稱為 D ] 的頂點(diǎn) 和 [編號(hào)為 4，名稱為 E ] 的頂點(diǎn) 的權(quán)重為： 2
[編號(hào)為 4，名稱為 E ] 的頂點(diǎn) 和 [編號(hào)為 1，名稱為 B ] 的頂點(diǎn) 的權(quán)重為： 7
    ----------- 深度優(yōu)先路徑搜索--------------
    找到一條路徑: [0, 3, 4]
    找到一條路徑: [0, 3, 1, 2, 4]
    '''

使用遞歸實(shí)現(xiàn)深度優(yōu)先搜索算法：

    '''
    遞歸實(shí)現(xiàn)深度搜索算法
    '''
    def def_dg(self, from_v, to_v):
        self.searchPath.append(from_v)
        if from_v.v_id != to_v.v_id:
            # 查找與 from_v 節(jié)點(diǎn)相連的子節(jié)點(diǎn)
            lst = self.find_neighbor_(from_v)
            if lst is not None:
                for tmp_v in lst[::-1]:
                    self.def_dg(tmp_v, to_v)
    """
    查找某一節(jié)點(diǎn)的相鄰節(jié)點(diǎn)，以列表方式返回
    """
    def find_neighbor_(self, find_v):
        if find_v.visited:
            return
        find_v.visited = True
        # 查找與 find_v 節(jié)點(diǎn)相鄰的節(jié)點(diǎn)
        lst = self.matrix[find_v.v_id]
        return [self.vert_list[idx] for idx in range(len(lst)) if lst[idx] != 0]

遞歸實(shí)現(xiàn)時(shí)，不需要使用全局棧，只需要獲到當(dāng)前節(jié)點(diǎn)的相鄰節(jié)點(diǎn)便可。