图
广度优先搜索
广度优先搜索（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 算法。
又称
另见