Python怎麼實現圖的廣度與深度優先路徑搜尋演算法

前言

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

圖與樹比較，圖具有封閉性，可以把樹結構看成是圖結構的前生。如果將兄弟節點或子節點之間的水平連接應用於樹狀結構，則可以建立圖形結構。

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

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

1. 圖理論

借助電腦解決現實世界中的問題時，除了儲存現實世界中的訊息，也需要正確地描述訊息之間的關係。

如在開發地圖程式時，需要在電腦中正確模擬出城市與城市、或城市中各道路之間的關係圖。只有在這個基礎上，才能用演算法計算出從一個城市到另一個城市，或從指定起點到目標點的最佳路徑。

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

圖結構可以有效地反映現實世界中如上所述資訊之間的複雜關係。以此可使用演算法方便的計算出如航班線路中的最短路徑、如火車線路中的最佳中轉方案，如社交圈中誰與誰關係最好、婚姻網中誰與誰最般配……

1.1 圖的概念

頂點：頂點也稱為節點，可認為圖就是頂點組成的集合。頂點本身是有數據意義的，所以頂點都會帶有附加訊息，稱作"有效載荷"。

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

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

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

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

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

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

邊描述的是頂點之間的關係，權重描述的是連結的差異性。

路徑：

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

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

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

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

• 沒有權重路徑的長度是路徑上的邊數。

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

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

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

圖的型別：

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

• 有向圖： 邊有方向的圖稱為有向圖。

• 無向圖： 邊沒有方向的圖表稱為無向圖。

• 加權圖： 邊上面有權重資訊的圖表稱為加權圖。

• 無環圖： 沒有環的圖形稱為無環圖。

• 有向無環圖： 沒有環的有向圖，簡稱 DAG。

1.2 定義圖

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

所有頂點構成集合訊息，這裡以 V 表示（如地圖程式中，所有城市構在頂點集合）。

所有邊構成集合訊息，這裡用 E 表示（城市與城市之間的關係描述）。

如何描述邊？

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

若以 G 表示圖，則 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, 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怎麼實現圖的廣度與深度優先路徑搜尋演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章！