BFS 樹（the BFS tree）

廣度優先搜尋以同心圈的方式探索圖：先是起點，接著是離它一條邊的所有頂點，再來是離它兩條邊的所有頂點，依此類推，像池塘上擴散的漣漪。在擴散時，它透過恰好一條邊發現每個新頂點——也就是它第一次抵達所經由的那條邊。若你只保留這些「發現邊」、丟掉其餘的邊，剩下的就是一棵以起點為根的樹，這就是 BFS 樹。它是搜尋走到哪裡、又怎麼走到的骨架。

機制如下。BFS 維護一個佇列，起初只放著起點 s，並把 s 標記為已拜訪、距離 0。它反覆從佇列取出一個頂點 u，查看 u 的鄰居；任何尚未拜訪的鄰居 v 被標記為已拜訪、距離設為 d(u)+1、父節點記為 u，並排入佇列。因為佇列是先進先出，每個距離 k 的頂點都會在任何距離 k+1 的頂點被碰到之前完全處理完——正是這個不變量讓同心圈乾淨俐落。父指標構成 BFS 樹：從任一頂點沿父指標回溯到 s，便描出 BFS 所找到的路徑，而關鍵在於那條路徑的邊數最少，因為 BFS 在最早（最短）的圈上就抵達每個頂點。在無向圖中，任何非樹邊所連的兩個頂點，其 BFS 層級至多相差一——沒有任何邊會橫跨兩層以上，這正是為何層級編號等於真正的距離。

BFS 樹之所以重要，是因為它的結構同時回答了好幾個問題：頂點在樹中的深度就是它離起點以邊數計的最短路徑距離、樹本身是一個稀疏的子圖（n-1 條邊）卻保留了所有那些最短距離、而層級編號讓你一趟就能測試二分圖。配上鄰接串列它跑在 O(n + m)。誠實的提醒：這裡的「最短」指的是邊數最少，只有在每條邊計數相同時才成立。給邊不同的權重，BFS 樹便不再給出最便宜的路徑——那是戴克斯特拉的工作，不是 BFS 的。