🔯從Python來學BFS廣度優先探索 與 等權圖的最短路徑Shortest Path

Pranay Pareek on Unsplash

定義

圖Graph: 由節點和邊所組成的一個網狀資料結構。

圖的表達方式Graph representation:

常見的有相鄰串列adjacency list或相鄰矩陣adjacency matrix。

本文以adjacenct list作為示範。

節點Vertex: 節點，也稱之為Node，圖的基本組成單元之一。

邊Edge: 邊，可分為有向邊Directed Edge，或無向邊Undirected Edge。

有向邊只能從起點走向終點。無向邊則可以雙向通過。

本文以有向邊作為示範。

廣度優先拜訪BFS:

從某個指定的起點開始探索整張圖，由內而外，逐層拜訪所有相鄰的節點。

比喻:

就好像一個小石頭(或小水滴)掉入水中，同心圓往外一層一層水波紋擴散的模式。

等權圖 Equal weighted Graph

圖中所有的邊的成本都相同，最常見的簡化版本是每條邊的成本都為1。

最短路徑 Shortest Path:

從起點出發，走到終點的最短路徑(或最小成本)。

當圖Graph是Edge成本都為1的等權圖的時候，
最短路徑 = 最佳路徑上經過的Edge總數。

範例 等權圖中 A→D 的最短路徑

演算法 用BFS來找等權圖中的最短路徑

1.建造一個BFS_queue，初始化時，放入起點和計步器(一開始歸零)。

2.遵循BFS演算法，從BFS_queue取出下一個要拜訪的節點和計步器的值。

3.由內而外逐層探索鄰居，並且將鄰居節點和計步器+1的值推入BFS_queue。

4.假如某一步發現現在的節點就是終點，則輸出成功訊息，並且把最短路徑的長度輸出。

5. 假如整張圖都拜訪完還是走不到終點，則輸出失敗訊息，提示無法從起點走到終點。

演算法的時間複雜度 O(V+E) 每個點至多拜訪一次，每條邊最多檢查一次。

詳細圖解 等權圖BFS最短路徑範例

最短路徑程式碼(底層依賴BFS廣度優先探索演算法)

    def shortest_path(self, start_node, target, visited=None):
        if visited is None:
            visited = set()

        bfs_queue = deque([(start_node, 0)])
        visited.add(start_node)
        
        while bfs_queue:
        
            cur, step = bfs_queue.popleft()
            if cur == target:
                print(f"shortest path from {start_node.value} to {target.value} takes {step} steps.")
                return

            print(cur.value)
            
            for edge in cur.edges:
                if edge.to_node not in visited:
                    visited.add(edge.to_node)
                    bfs_queue.append( (edge.to_node, step+1) )
        
        print(f"There is no shortest path from {start_node.value} to {target.value}.")
        return

體驗BFS廣度優先搜尋 與 等權圖最短路經的關聯

完整的等權圖BFS 廣度優先拜訪與最短路徑實作和程式碼

from collections import deque

class Node:
    def __init__(self, value):
        self.value = value
        self.edges = []

    def add_edge(self, edge):
        self.edges.append(edge)

class Edge:
    def __init__(self, from_node, to_node):
        self.from_node = from_node
        self.to_node = to_node

class Graph:
    def __init__(self):
        self.nodes = []

    def add_node(self, node):
        self.nodes.append(node)

    def add_edge(self, from_node, to_node):
        edge = Edge(from_node, to_node)
        from_node.add_edge(edge)

    def dfs(self, start_node, visited=None):
        if visited is None:
            visited = set()

        visited.add(start_node)
        print(start_node.value)
        for edge in start_node.edges:
            if edge.to_node not in visited:
                self.dfs(edge.to_node, visited)
  
    def shortest_path(self, start_node, target, visited=None):
        if visited is None:
            visited = set()

        
        bfs_queue = deque([(start_node, 0)])
        visited.add(start_node)
        
        while bfs_queue:
        
            cur, step = bfs_queue.popleft()
            if cur == target:
                print(f"shortest path from {start_node.value} to {target.value} takes {step} steps.")
                return

            print(cur.value)
            
            for edge in cur.edges:
                if edge.to_node not in visited:
                    visited.add(edge.to_node)
                    bfs_queue.append( (edge.to_node, step+1) )
        
        print(f"There is no shortest path from {start_node.value} to {target.value}.")
        return

def demo():
  # Graph and BFS demo

  # Create Graph
  graph = Graph()

  # Create Node
  nodeA = Node('A')
  nodeB = Node('B')
  nodeC = Node('C')
  nodeD = Node('D')
  nodeE = Node('E')
  nodeF = Node('F')

  # Add node into Graph  
  graph.add_node(nodeA)
  graph.add_node(nodeB)
  graph.add_node(nodeC)
  graph.add_node(nodeD)
  graph.add_node(nodeE)
  graph.add_node(nodeF)

  # Add edge into Graph
  graph.add_edge(nodeA, nodeB)
  graph.add_edge(nodeA, nodeC)
  graph.add_edge(nodeB, nodeD)
  graph.add_edge(nodeB, nodeE)
  graph.add_edge(nodeC, nodeF)
  graph.add_edge(nodeF, nodeD)

  print("BFS traversal starting from node A:")

  # 嘗試尋找從A走到D的最短路徑
  graph.shortest_path(nodeA, nodeD)
  
  # 嘗試尋找從C走到A的最短路徑
  #graph.shortest_path(nodeC, nodeA)

if __name__ == '__main__':
  demo()

測試輸出

BFS traversal starting from node A:
A
B
C
shortest path from A to D takes 2 steps.

結語

其實BFS廣度優先演算法就相當於水波紋從波源開始擴散的過程模擬。

當輸入是等權圖時，就可以利用這項特質，透過BFS來找從起點走到終點的最短路徑。

最短路徑(最小成本) = 水波紋擴散層數 = 從起點到終點 沿路經過的Edge總數

讀者可以透過紙筆追蹤演算法和程式執行邏輯，測試幾個簡單的小範例，

會有更深刻的了解和體會！

Graph圖論BFS相關的演算法練習題與詳解

BFS 經典入門題 Binary Tree Level Order Traversal_Leetcode #102

BFS 經典入門題 Binary Tree Level Order Traversal II Leetcode #107

BFS應用題 Find Largest Value in Each Tree Row Leetcode #515

BFS經典應用 最精簡公車路線搭乘次數 Bus Routes_Leetcode #815

一魚多吃 用BFS來列出拜訪路徑 Diagonal Traverse II_Leetcode#1424

一題多解 用DP、BFS去解 Pefect Square 完全平方數的化簡_Leetcode #279

合縱連橫: 從 圖論的應用題 理解BFS背後的本質

Graph theory圖論 DFS、BFS演算法的統整與比較