一圈一圈往外擴,用佇列。在不加權的圖或迷宮上,它找到的一定是最短路。
佇列當引擎 —— 起點入列;每次從佇列前端拿一個,把它沒走過的鄰居排到尾端。
記錄走過的 visited —— 避免重複、避免在有環的圖裡繞圈。
距離自然分層 —— 鄰居的距離 = 自己的距離 + 1;佇列裡永遠是「近的先出」。
第一次碰到就最短 —— 因為由近到遠,第一次抵達目標的步數不可能更少。
想像水波從起點擴散 —— 第 1 圈是 1 步能到的、第 2 圈是 2 步的、第 3 圈是 3 步的…
BFS 就是照這個順序處理節點 —— 所以「第一次碰到 X」時,X 一定落在最近的那一圈。
前提是「每一步成本一樣」(不加權) —— 一旦邊有不同權重(距離、時間、費用),就要改用 Dijkstra(堆積那頁)。
石頭丟進水裡,漣漪一圈一圈往外,同一圈的地方同時被碰到 —— 這就是 BFS 的分層。
火從一點往四周同速燒開,一定先燒到近的、再燒到遠的。
先告訴直接朋友(第 1 圈),他們再傳給他們的朋友(第 2 圈),越遠的越晚知道。
從 S 出發要走到 G,深色是牆。按「下一步」讓水波擴散一圈:琥珀是這一圈(距離剛好等於圈數)、淡綠是更早碰到的、格子裡的數字是離 S 幾步。碰到 G 後會回溯出綠色最短路。
從 BFS 骨架、記距離、還原路徑,到迷宮、層序走訪、多源 BFS、單字接龍、二分圖染色。
❌ 出列時才標記 visited —— 會讓同一節點被重複入列、佇列爆量。要在「入列時」就標記。
❌ 用 BFS 找加權最短路 —— BFS 只保證「步數最少」;邊有權重要用 Dijkstra。
❌ 忘了 visited —— 有環的圖會無限繞。
❌ 用 list.pop(0) 當佇列 —— 那是 O(n),要用 deque.popleft()(呼應佇列那頁)。
visited 要在「入列時」標記,而不是「出列時」?會差在哪?把答案打到對話裡,我幫你對。