BFS解無權重最短路徑

 使用廣度優先搜尋 (BFS) 來解無權重圖的最短路徑問題。它的應用場景例如在地圖導航中找到兩地之間的最短路徑。

def shortest_path(graph, start, end):
queue = deque([(start, [start])]) # 使用佇列進行 BFS
visited = set([start])

while queue:
    node, path = queue.popleft()
    if node == end:
        return path  # 找到終點，返回路徑
    for neighbor in graph[node]:
        if neighbor not in visited:
            visited.add(neighbor)
            queue.append((neighbor, path + [neighbor]))

測試

graph_list = {
0: [1, 2],
1: [0, 3],
2: [0, 3],
3: [1, 2]
}
print(“節點 0 到節點 3 的最短路徑:”, shortest_path(graph_list, 0, 3)) # 預期輸出: [0, 1, 3]

程式追踪

1. 初始化：

   • 使用 queue 佇列來進行 BFS，並將起始節點 start 和目前路徑 [start] 作為一個元組放入佇列中。
   • 初始化 visited 集合來儲存已訪問過的節點，避免重複訪問。
   • 起始狀態如下：

     queue = deque([(start, [start])])  # 佇列：[(0, [0])]
     visited = set([start])  # 訪問集合：{0}
     

2. 開始 BFS 搜尋：

   • 進入 while 迴圈，每次從 queue 中取出一個節點和該節點的當前路徑 (node, path)。
   • 首次迭代中，node 為 0，path 為 [0]。

3. 檢查終點：

   • 如果 node 是終點 end，則直接返回 path，因為 BFS 找到的第一條到達終點的路徑即為最短路徑。
   • 在首次迭代中，node 為 0，不是終點 3，所以繼續進行下一步。

4. 遍歷鄰居：

   • 取出 node 的所有鄰居節點，逐個檢查每個 neighbor 是否已訪問過：
     • 若 neighbor 未被訪問過，將其加入 visited 集合，並將 (neighbor, path + [neighbor]) 放入 queue 中。這樣可以追踪到每個節點的路徑。
   • 在首次迭代中，節點 0 的鄰居是 1 和 2，都未被訪問，依序將 (1, [0, 1]) 和 (2, [0, 2]) 加入 queue。更新後狀態如下：

     queue = deque([(1, [0, 1]), (2, [0, 2])])
     visited = {0, 1, 2}
     

5. 重複步驟 2-4：

   • 再次從 queue 中取出下一個節點，直到找到終點或 queue 為空。
   • 第二次迭代時，取出 (1, [0, 1])，檢查 node 為 1 的鄰居 0 和 3。
     • 0 已訪問過，略過。
     • 3 未被訪問過，加入 visited 並將 (3, [0, 1, 3]) 放入 queue 中。
   • 當取出 (3, [0, 1, 3]) 時，發現 node 已為 end，所以返回 [0, 1, 3] 作為最短路徑。

---

結果

• 測試輸出：[0, 1, 3]，表示節點 0 到節點 3 的最短路徑。

---

這段程式運用 BFS 的層級遍歷特性，確保找到的第一條符合條件的路徑即為最短路徑。queue 負責儲存當前節點及其累計路徑，visited 避免節點重複訪問。

---

補充說明

在這段程式中，deque([(start, [start])]) 的寫法是正確的，原因在於：

• deque([(start, [start])]) 使用的是一個列表 [(start, [start])]，該列表包含一個元組 (start, [start])。這樣可以初始化 deque 時，一次就放入多個元素，並保持每個元素的結構。
• deque((start, [start])) 則會導致錯誤，因為 deque() 會將整個元組 (start, [start]) 視為一個可迭代對象。這樣會將 start 和 [start] 當作分開的兩個元素放入 deque 中，而不是一個完整的元組。

deque([(start, [start])]) 的用法可以將 deque 初始化為包含單個元組的結構，而 deque((start, [start])) 則會將元組拆開，導致錯誤。