以邊數計的最短路徑（shortest paths in number of edges）

有時唯一重要的成本是一趟旅程要走幾步，而不是每步多長。兩個人之間隔了幾層「朋友的朋友」？騎士橫越棋盤最少需幾步？從一篇維基百科文章點到另一篇要幾下？在這些情況裡每條邊都算一步，最短路徑就是邊數最少的那條。這是無權圖中自然的距離，而廣度優先搜尋恰好把它算出來。

BFS 靠的是依距離遞增的順序抵達頂點。把起點的距離設為 0；當 BFS 第一次透過某條由 u 出發的邊發現頂點 v 時，它令 dist(v) = dist(u) + 1。這之所以正確、而不只是看似合理，靠的是佇列不變量：BFS 在任何距離 k+1 的頂點之前處理完所有距離 k 的頂點，所以任何頂點第一次被發現時，都是從最近可能的圈被發現的——沒有更短的路徑會在稍後才被找到。你可以對距離做歸納來證明 dist(v) 恰是真正的最短距離：在距離 0 時成立，而若每個距離 k 的頂點都得到正確值，那麼它們尚未被發現的鄰居確實位於距離 k+1，且 BFS 正是這樣標記它的。從 v 沿父指標回溯到起點，便重建出一條真正邊數最少的路徑，而不只是它的長度。

這是「幾度分隔」、最少步數謎題、網路跳數，以及更大演算法內部子程序背後的主力。配上鄰接串列它花 O(n + m)——線性，而且不可能更好，因為你可能得看遍整張圖。關鍵的提醒：這是邊數最少，只有在所有邊成本相同時才等於最便宜的路徑。一旦邊帶有不同權重，BFS 對最低成本就給出錯誤答案，你必須改用戴克斯特拉（非負權重）或貝爾曼-福特（一般權重）。一個有用的中間情況：若權重是很小的整數，有時仍可藉由拆分重邊用類似 BFS 的方法，但乾淨的說法是：純 BFS 解的是無權情況。