從 Terry 的模擬面試題，談圖上做廣度優先搜尋 (BFS) 的各種眉角

16 min readApr 27, 2023

前情提要

相信不少人看過了 Terry 最近很紅的影片，誠徵資深實習生｜面試過程公開，後續也引發了很多精彩的關於管理 v.s. 工程的討論，諸如管理者的工程技術是否重要、資料結構與演算法的實用價值、面試中溝通能力的重要性…等等，雖然這些都很有趣，但這篇文章想聚焦在 BFS 這個看似很單純的問題上面，來認真剖析這個貌似簡單的面試送分題，到底藏有多少該注意的細節。

會想寫這篇的主因是影片中剛好挑了一個 BFS 最基礎題目，應該是所有正在學演算法的人都要會的核心基本功，但卻給了很有意思的 follow up，引發了很有趣的思考方向。

沒看過影片的人也沒關係，由於這篇僅會討論資料結構與演算法，所以只要簡單看一下下面提敘即可無痛閱讀！

題目是這樣的：

Warm up: 給定一個圖與起點，請遍歷整張圖，並按照與起點距離的順序印出，若距離一樣則順序不限
Follow up: 每次問一個點的出邊（他可以走到的其他點），需要耗時 1 秒，如何做優化

從結論來說的話，這題雖然看似 Leetcode Easy 的送分題，但一旦認真展開討論，份量絕對足以支撐一場完整的 30~40min 面試。

如果你對廣度優先搜尋不熟，那這篇可以幫你好好複習一次，順便整理很多面試官愛問的延伸問題。如果你已經很熟了，也可以看看有沒有你沒想過的東西，或幫我檢視有沒有我沒想到的東西，讓我們一起交流進步！那廢話不多說，就讓我們開始吧！

最基本的 BFS

這章節幫大家複習一下基礎 BFS，如果你很熟練可以直接跳過。

一般做圖的題目時，只要聽到跟距離有關，且邊沒有權重，那思路一般就是先朝廣度優先搜尋 (BFS) 去想

BFS 的基本，就是從起始點開始，一層一層搜尋下去，以下圖為例，這是一個有向圖，如果從 node 0 出發，相同顏色的 node 會屬於同一個層級，以跟出發點的距離來看，黃色是 1，綠色是 2，紅色是 3。BFS 的最大用途就是你可以依據跟起始點的距離遠近，依次印出所有的點（同一層內的順序不管）。

那如果想要好好維持這種”一層一層”展開的性質，勢必在走訪過程中，要知道兩件事，第一個是下一層有誰，第二個則是哪些點已經走過不要再碰，例如最後的 node 8 又會走回 node 3，但 node 3 我們知道走過了，所以不會認為他的距離在 node 8 之後。

接下來講解思考的方向。但首先確立一下，本篇中，我的圖的紀錄方式階採用 Adjacency List，我們可以將上面這張圖翻譯成下面這樣。

edges = {
  0: [1, 2, 5],
  1: [3, 4],
  2: [5, 7],
  3: [],
  4: [],
  5: [7],
  7: [8],
  8: [3]
}

# edges[x] 就代表了所有從 node x 可以連到的 nodes

Note: 有的面試官會請你從選擇圖表示法開始，我自己經驗是 Adjacency List 泛用性最高，code 也最好寫，時間空間複雜度也較好，所以都會拿他當第一選擇，除非有很特殊條件發現他不好用，才會改選 Adjancency Matrix 或真的刻一個 Node class 出來。

怎麼紀錄看過的點？

第一個爭論點，影片中面試者 Nic 用 Array 來紀錄，其實這並非不行，甚至在特定情境下是效能最好的。因為我可以開一個跟 Node 數量一樣長度的 Array，每個 index 代表一個 node 的狀態，一開始值都是 0，一但走過就改成 1，這種僅對特定位置 memory 做讀寫的工作，對電腦來說非常省力。

那問題是什麼？

有沒有發現我上圖偷偷少了 node 6，假如這個 node 不是連續的，或不是從 0 開始，例如編號是 0, 100, 999, 1000000，那你有可能得浪費很多的記憶體在上面，甚至編號不是數字，而是 A, B, C，這招就不能用了。

當然聰明的人會想到，那我先用 hash table 建一張 mapping 表不就好了？把每個 node 重新對應回 0~N。但這樣無論如何都得浪費一個計算 hash 的時間，那不如直接用更簡單的資料結構 — Set 就好，背後做的事幾乎一樣。

所以最正確的做法，是面試官 Terry 提示的，開一個空的 Set，然後看過的 node 就將它放進去。利用 Set 在插入與查詢都是 O(1) 的特性，來當作記錄器使用，（c++ 使用者要記得用 unordered_set）。

老實說，直接用 Array 記反而是很多競賽高手愛用的方式，因為絕大多數競賽題目都很老實的給 0~N 或 1~N 的編號方式，這樣做在執行效率上最好。但以面試跟實際工作來說，我還是建議 Set 是最通用且理論上正確的做法。

Terry 面試官提問的：你知道 Array 跟 Set 的差別嗎？也是很基礎常見的重要知識，如果你覺得還不清楚最好趁這次機會搞懂喔。

怎樣做到好好的一層一層前進

熟手會膝反射的想到 BFS 要用 Queue，但我們先不聊他，比起背教科書的最佳解，讓我們先從更直觀的基礎出發，去慢慢探索一個演算法的思路，想想看，如果面試官不讓你用 Queue，你會怎麼做呢？

其實 BFS 最原始的想法就是，走完一層，再走下一層

我們是不是可以用一個 Array，去紀錄這一層所有的 nodes，然後換一個 Array 紀錄下一層所有的 nodes？當然如果每一層都要開一個新的 Array，要浪費很多空間，但有個常見的小技巧就是我只開兩個，一個當這層，另一個當作下一層，而每次走完一整層之後，由於當前這層已經不需要了，那我就把他們交換，並把不要的清空就好。

中文講起來可能很繞口，寫成 code 如下或許更好懂

edges = { ... } # 抄上面圖的定義
visited = set([0]) # 拿來紀錄看過的 node，起點可以直接放進去
cur_level = [0] # 紀錄當前這層的 node，由於起點是 0，所以一開始只有 0
nxt_level = [] # 紀錄下一層的 node，一開始是空的

while(cur_level): # 全部空掉就結束
  for node in cur_level: # 把這層 array 裡面每個 node 看一次
    print(node)  
    for nxt in edges[node]: # 把所有 node 可以走到的新的點，都放到下一層 array 去
      if nxt not in visited: # 用 visited set 確保沒有走到已經看過的點
        nxt_level.append(nxt)
        visited.add(nxt) # 記得紀錄起來他看過了
  cur_level = nxt_level # 一點小巧思，把 cur_level 指向 nxt_level 的記憶體位置 
  nxt_level = [] # 最後把 nxt_level 換成一個空的

這種雙 Array 交互替換的技巧，其實也很常出現在動態規劃的題目中，拿來簡單的減少空間複雜度（M*N -> 2*N)，如果以前沒看過，值得順手學一下。

改用 Queue 怎麼做？

接著就來聊聊為什麼要用 Queue？如果你把上面那個做法每一輪的 cur_level 印出來，其實你會得到

[0], [1,2,5], [3,4,7], [8]

透過觀察，如果我每次都能好好的從左（頭）至右（尾）的遍歷一個 Array，並把新看到的 node 就無腦塞到尾端去，得到的結果會跟上面很類似。下面簡單敘述過程，想像我有一個空的記錄容器 [ ]，一開始放 0 進去變成 [0]。

從 [0] 開始，我先把 0 給拿出來，容器又變空的 [ ]，但我接著把 0 能走到的 1, 2, 5 都塞到最後，就得到 [1, 2, 5]
接著 [1, 2, 5] 裡面，我先把最左邊的 1 拿出來，剩 [2, 5]，並把他走到的 3, 4 塞到最後面去，會變成 [2, 5, 3, 4]
接著我一樣拿最左邊的 2 出來，變 [5, 3, 4]，而他可以走到 5 跟 7，但 5 已經看過所以不管他，只把 7 放到最後，變成了 [5, 3, 4, 7]
這樣依此類推下去，你最後就可以按照順序走完了，而這種適合從左邊拿，從右邊塞的資料結構，剛好就是 Queue。也就是所謂的先進先出。

現在讓我們用 Queue 來寫一個最教科書範例的 BFS 吧！

visited = set([0]) # 拿來紀錄看過的 node，起點可以直接放進去
queue = [0] # 我們的 queue

while (queue):
  node = queue.pop(0) # pop(0) 代表 pop 掉第一個元素，也就是從左邊拿出一個元素
  print(node)
  for nxt in edges[node]:
    if nxt not in visited:
      queue.append(nxt)
      visited.add(nxt)

寫完了！但這個範例 code，如果你沒有感覺到什麼不對，那事情就很不對了，上面的 code 有個非常致命的錯誤，如果你一眼就看到，表示你對基礎資料結構的敏感度很不錯，這問題就是

Array 從左邊拿出一個元素，花的時間複雜度是 O(N)，不是 O(1)

影片中用的語言是 Javascript，並用了 Array 的 unshift，一樣是從左邊拿元素的概念，而且一樣是 O(N) 的複雜度，如果你這個 pop 操作是 O(N)，那甚至不能稱之為 Queue 了，而整個 BFS 整體時間複雜度還會變成 O(N²)，這是完全不能接受的！（嚴格來說複雜度還要加上邊數 E 的變項，但這邊不是重點先不贅述）。

Queue 的 pop 與 push 應該都要是 O(1) 才合格。因此正確的做法，是使用 Python 內建的 deque 來做為 Queue 使用才對，讓我們重新寫一次正確版本，也是初學者該學會的第一版。

from collections import deque

visited = set([0])
queue = deque([0])

while (queue):
  node = queue.popleft()
  print(node)
  for nxt in edges[node]:
    if nxt not in visited:
      queue.append(nxt)
      visited.add(nxt)

常見面試延伸問題：如果不只要印出 node 編號，還要每次都順便印出他在哪一層，上面的兩個做法，你會怎樣修改呢？

但糟糕的地方在於，有些語言其實沒有原生內建的 Queue，很不幸的，影片中採用的 Node.js (Javascript）也是其中之一，所以如果你搜索 Javascript Queue Implementation 甚至會在 Google 前幾頁找到很多很多用 unshift 的寫法，但這是錯的！！！（聽說講三遍退流行了所以只講一遍）。甚至連知名演算法工具庫 OpenGenus/cosmos 以前的範例也給了這個錯誤作法，因此我當年還發了個 PR 幫忙修掉他。

所以該怎麼做？在 Python 你有 deque 可以用，c++ 也有 std::queue，而 Javascript 你得自己實作一個，或詢問面試官是否可以用第三方工具庫。要自己做的話，有興趣可以看我以前寫的版本。或者使用 Leetcode 官方承認的 library，但要先問一下面試官能不能接受。Leetcode 其實也有一題就是考如何自製 Queue，如果不熟悉很推薦順便做一下。順帶一提，如果要很完整無特別限制的 Queue，可以用 Linked List 來做，只是刻起來更囉唆一點。

囉唆了這麼久，終於把基本題講完了，但這題的重頭戲現在才正開始，想想看影片中 Terry 的 follow up 給了一個很神秘的條件，他的圖並不是像我上面那樣簡單的用 Adjancency List 給你的，而是給了你一個 fetchNeighbor() 的 function，可以問這個 node 連到那些 nodes，但這個 function 是個一次耗時 1 秒的 remote API，那這神秘的條件究竟有什麼意義？

非同步版本的 BFS

影片中的 Nic 直覺反應是用非同步的方式優化，看到不少人說扯到非同步去有點遠了，但不得不說，不管你覺得整部影片下來 Nic 的表現有多糟糕，對時間複雜度的概念有多差，但就這點來說他的直覺是對的！

Call 一次要 1 秒的限制是個非常大的 hint，想想看，一般來說我們思考演算法確實很少去想非同步的事情，但這個 follow up 的考核點恰恰就是非同步。如果你以為非同步已經超出演算法面試的範疇的話，不幸的消息是 Leetcode 其實也是有這題的，題目編號是 1242. Web Crawler Multithreaded，被分類在 Concurrency，雖然是鎖住的題目，但網路上還是找得到原題敘述，當然也可能在真實面試中出現。

我簡單描述一下 Leetcode 題目，目標是做一個簡易爬蟲，一開始給你一個 url，你爬了他之後，會在裡面找到更多的 url，而你就要繼續追著爬下去，不斷往前挖，當然中間也有些 url 會重複，你要避免重複訪問，直到不再有新的 url。這是不是跟 Terry 的 BFS 題目一模一樣。

那解題思路是什麼？你可以想一下，一般來說演算法的 Graph 題目，點數 V 與邊數 E 最大都頂多 1e8，否則光 input 記憶體先炸了，但 BFS 的時間複雜度是 O(V+E)，也就是說在一般合理 input 情況下，整個演算法執行起來大概都不到1 秒，甚至不到 0.1 秒。而你現在給了個特殊限制，是每問一次 Neighbor 就要 1 秒，那這時候對於整個系統的瓶頸，已經從演算法的層級，轉移到怎樣最小化 Call fetchNeighbor 的次數，或者是利用非同步的方式一次發送數個 fetchNeighbor 一起解決。

我們用原本的圖來解釋如下

當你一開始 node 0 呼叫了一次 fetchNeighbor，得到紅圈中的 node 1, 2, 5 之後，那一個簡單想法就是，我會希望他們三個可以透過非同步的方式同時呼叫 fetchNeighbor 就好，如此一來我就可以幾乎在 1 秒內一次解決 3 個 API call，達到 3 倍的加速，後面依此類推。(當然如果這是張退化成 Linked List 的圖，那這做法就沒加速到東西了)

一但有了這個思路，引發的大問題就是

我怎樣確保 visited 紀錄不會有 race condition？
我怎樣確保印出順序沒有亂掉？

影片中可惜的就是面試者沒處理這兩個根本問題，所以雖然大方向對了，但最終答案卻令人充滿疑問，而 Terry 面試官在這邊簡單詢問 big O 時面試者就先卡住了，當然也沒辦法展開更有意義的深度討論，這甚至都已經不是 big O 層級的問題了啊。

在上述兩個問題中，第一個問題比較大，如果你的 visited 沒有 lock 好，會有 race condition 的問題，也就是你其中一個 thread 走到了某個 node，將它塞到 queue 的尾端，但在還沒把他記錄到 visited 前，另一個 thread 不小心也走了一次，以為還沒 visited 就又把他放進去 queue 一次，結果你下一輪就有兩個重複的 node，如此有可能同一個 node 被走好幾次。

第二個問題相對好解決，你大可以先不管順序的 BFS / DFS 一次，把整張圖給爬完並紀錄到 memory 裡面，變成一個 Adjancency List 後，再跑一次基本題的解法，所以你第一次順序是亂的也沒差。基於上面的估算，整張圖建立所花的時間會大很多，而單純在 memory 上跑一遍 BFS 的時間則幾可忽略。

事實上，假如已事先知道所有 node 編號，我們甚至大可以一開始就全部或分批次的同時對多個 node 呼叫 fetchNeighbor，然後先把圖建立好，最後再一次 BFS，這樣絕對效能最佳，不管什麼圖都能處理，且寫起來也超級簡單。

所以可想而知，如果有再下一個 follow up，就是我的圖很大，不給你用先抓下整張圖的這種偷吃步的簡單做法（否則 memory 不夠用），或者如 Leetcode 般讓你事先不知道有多少 node，總之是要你非得老老實實的邊走邊展開。這就考驗你怎樣設計 lock 機制，盡可能地把可以一起做的事一起做掉，但卻不會打亂整體的順序與紀錄，最後或許還要考慮是否需要適時清 memory，這已經上升到微 system design 的層級了，但仍然足以把 code 寫出來的範圍。有興趣的讀者可以先自已想想，如果是你，會想怎麼做？

以下講一下我的做法，現在可以回來說為什麼上面我要講一個雙 Array 的版本了，因為如果你用這個思路去做，那非同步其實沒有很難改，單純就是每一輪先把該層 Array 中的 nodes 全部一起叫一次 fetchNeighbor ，並搜集不重複的 node 就好了。下面是一個簡單的範例，當然 Concurrency 做法有百百種，每個又可以展開很多細節討論，但這邊僅用最簡單的一種方式處理做範例。

import time
import threading

edges = { ... } # 抄開頭圖的定義

# 模擬 remote API 一次耗時 1 秒
def fetchNeighbor(node):
  time.sleep(1)
  return edges[node]

# Call remote API 問 Neighbor 並記錄到 set 裡
def job(node, neighbors):
  for nxt in fetchNeighbor(node):
    neighbors.add(nxt)

# 透過非同步方式一次詢問多個 nodes 的 neighbors
def fetchAllNeighbors(nodes):
  N = len(nodes)
  neighbors = set(); # 簡單利用 Set 的不重複性質，就不用擔心 race condition
  threads = []
  for i in range(N):
    threads.append(threading.Thread(target = job, args = (nodes[i], neighbors,)))
    threads[i].start()
  for i in range(N):
    threads[i].join()
  return neighbors

# 原本的 Code
visited = set([0])
cur_level = [0]
nxt_level = []

while(cur_level):
  for node in cur_level: # 印出這輪的 node 編號
    print(node)

  for nxt in fetchAllNeighbors(cur_level): # 一次非同步的找到所有的 neighbors
    if nxt not in visited:
      nxt_level.append(nxt)
      visited.add(nxt)
  cur_level = nxt_level
  nxt_level = []

這裡用了個小技巧，就是利用 Set 資料結構本身內容物不會重複的特性，就可以簡單處理 race condition 的問題，讓我們順利找到下一輪中不重複的 neighbor。Set 是不是很好用呢！

到此為止，才是這整題的全貌，我相信一場 30~40 分鐘的面試，要把上面問題全部討論完並不容易，這些是我聽到題目時腦中噴出來的各種想法，但好好組織整理一番並寫下這篇，也是兩三個小時過去了。所以 Graph BFS 一點都不單純，這題也不是送分題啊，希望對大家有幫助。

最後的最後，留個延伸思考，有沒有可能我連不同層的 node 也一起打包詢問，來提升更多效率？我自己一時沒想到什麼簡單漂亮的做法，如果有人有想法的話也歡迎在討論區一起討論！