完整程序：BFS 最短距离与路径条数

无向图的边为 (1,2),(1,3),(2,4),(3,4),(3,5),(4,6),(5,6),(6,7)，邻居按编号升序。完成第 1～12 题。

vector<int> g[8];
int dist[8], parent[8], ways[8];
queue<int> q;
fill(dist, dist + 8, -1);
dist[1] = 0;
ways[1] = 1;
q.push(1);
while (!q.empty()) {
    int u = q.front(); q.pop();
    cout << u << " ";
    for (int v : g[u]) {
        if (dist[v] == -1) {
            dist[v] = dist[u] + 1;
            parent[v] = u;
            q.push(v);
        }
        if (dist[v] == dist[u] + 1)
            ways[v] += ways[u];
    }
}

第 1 题

程序输出的出队顺序是什么？

{{ input(1) }}

---

第 2 题

dist[4] 的值是多少？

{{ input(2) }}

---

第 3 题

dist[6] 的值是多少？

{{ input(3) }}

---

第 4 题

dist[7] 的值是多少？

{{ input(4) }}

---

第 5 题

parent[4] 的值是多少？

{{ input(5) }}

---

第 6 题

parent[6] 的值是多少？

{{ input(6) }}

---

第 7 题

从 1 到 4 的最短路条数 ways[4] 是多少？

{{ input(7) }}

---

第 8 题

从 1 到 6 的最短路条数 ways[6] 是多少？

{{ input(8) }}

---

第 9 题

从 1 到 7 的最短路条数 ways[7] 是多少？

{{ input(9) }}

---

第 10 题

把队列改为栈后，第一次到达某点是否仍保证是无权最短路？

{{ select(10) }}

• 保证
• 不保证

---

第 11 题

若把“发现即标记”改成出队时才标记，可能导致（ ）。

{{ select(11) }}

• 同一顶点重复入队
• 所有距离自动减一
• 图变成有向图
• 复杂度必为 $O(1)$

---

第 12 题

邻接表 BFS 的时间复杂度是（ ）。

{{ select(12) }}

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

---