Day10-A3 BFS与无权最短路专项（GESP七级风格）

独立训练BFS队列、分层访问、无权最短路与复杂度。后四题共用完整程序。

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main(){
    int n,m,s; cin>>n>>m>>s;
    vector<vector<int>> g(n+1);
    while(m--){int u,v;cin>>u>>v;g[u].push_back(v);g[v].push_back(u);}
    vector<int> d(n+1,-1); queue<int> q;
    d[s]=0; q.push(s);
    while(!q.empty()){
        int u=q.front(); q.pop();
        for(int v:g[u]) if(d[v]==-1){d[v]=d[u]+1;q.push(v);}
    }
    for(int i=1;i<=n;++i) cout<<d[i]<<' ';
}

第 1 题

广度优先遍历通常借助的数据结构是（ ）。

{{ select(1) }}

• 集合
• 队列
• 栈
• 二叉搜索树

第 2 题

无权图 BFS 第一次发现顶点 v 时得到的是（ ）。

{{ select(2) }}

• 最长简单路
• 源点到v的最少边数
• 拓扑编号
• v的度数

第 3 题

在顶点入队时立即标记访问，主要为了（ ）。

{{ select(3) }}

• 避免同一顶点重复入队
• 让边权变为1
• 删除所有环
• 把图排序

第 4 题

普通 BFS 不能直接解决（ ）。

{{ select(4) }}

• 图的层次遍历
• 可达性判断
• 含不同边权的最短代价
• 无权最短步数

第 5 题

输入 5 4 1，边为 1 2、1 3、2 4、4 5，输出为（ ）。

{{ select(5) }}

• 0 1 1 2 3
• 0 1 1 1 1
• 0 1 2 3 4
• 1 2 2 3 4

第 6 题

不可达顶点最后输出（ ）。

{{ select(6) }}

• n
• 0
• 1
• -1

第 7 题

d[v]=d[u]+1 表示（ ）。

{{ select(7) }}

• v编号比u大1
• v入度加1
• 删除边u-v
• v位于u的下一距离层

第 8 题

当前程序的总时间复杂度是（ ）。

{{ select(8) }}

• $O(m^2)$
• $O(n^3)$
• $O(n+m)$
• $O(2^n)$