圖
廣度優先搜尋
廣度優先搜尋（BFS）像水面上的漣漪一樣，一圈一圈地探索圖。從一個頂點出發，先造訪所有直接鄰居（距離 1），再造訪它們所有尚未造訪的鄰居（距離 2），如此層層展開。它一層一層向外擴散，絕不會在近處的頂點還沒處理完之前，就一頭鑽進某一條分支深處。
支撐這種順序的引擎是一個佇列（先進先出）。先把起點入列，然後反覆取出佇列前端的頂點、標記為已造訪，並把它尚未見過的鄰居入列。佇列裡裝的正是當前的「前沿」，因此頂點是按到起點距離遞增的順序出列的。把頂點標記為已造訪至關重要——否則一旦遇到環，就會陷入無限迴圈。
BFS 對每個頂點只造訪一次、對每條邊只檢查一次，因此在鄰接表上執行時間為 O(V + E)。它最招牌的好處是：在無權圖中，BFS 第一次到達某頂點時所在的層數，就是該頂點到起點的最短距離（邊數最少）。這使 BFS 成為「每條邊權重都相同」時求最短路徑的首選工具。
queue<int> q;
vector<bool> seen(n, false);
q.push(start); seen[start] = true;
while (!q.empty()) {
int v = q.front(); q.pop();
for (int nb : adj[v])
if (!seen[nb]) { seen[nb] = true; q.push(nb); }
}在入列的那一刻就標記已造訪，這樣同一頂點不會被入列兩次。
只有在邊無權（或權重全相等）時，BFS 才給出最短路徑。權重各異時要改用 Dijkstra 演算法。
又稱
另見