队列实现 BFS

一句话理解

队列实现 BFS：push 起点，while 取 front。

为什么要学

标准模板。

讲解

q.push(s); vis[s]=1; while(!q.empty()){ u=q.front(); q.pop(); for v: if !vis push }。

例子

queue<int> q;
vis[s] = 1; q.push(s);
while (!q.empty()) {
    int u = q.front(); q.pop();
    for (int v : g[u]) if (!vis[v]) {
        vis[v] = 1; q.push(v);
    }
}

进队时标记，保证每个点一次。

常见错误

• 出队时才 vis，队列会堆满重复点。
• 空队列还 front。