第 10 章图论基础 · 知识细节练习

壹

图的基本概念

6 QUESTIONS · 2 POINTS EACH

第 1 题 A1 未作答

判断题：图由顶点集合和边集合组成，每条边连接两个顶点。

（1 分）

A

正确

B

错误

第 2 题 A2 未作答

判断题：无向图的边没有方向（ $(u,v)$ 与 $(v,u)$ 相同），有向图的边有方向（弧）。

（1 分）

A

正确

B

错误

第 3 题 A3 未作答

判断题：无向图中顶点的度 = 与它相连的边数；有向图分入度和出度。

（1 分）

A

正确

B

错误

第 4 题 A4 未作答

判断题：无向图中所有顶点的度数之和 = 边数的 $2$ 倍（每条边贡献 $2$ 个度）。

（1 分）

A

正确

B

错误

第 5 题 A5 未作答

判断题：路径是顶点序列（相邻顶点间有边）；环是起点 = 终点的路径。

（1 分）

A

正确

B

错误

第 6 题 A6 未作答

判断题：无向图中任意两顶点都有路径相连，则图连通；极大连通子图叫连通分量。

（1 分）

A

正确

B

错误

贰

特殊图

6 QUESTIONS · 2 POINTS EACH

第 7 题 B1 未作答

$4$ 个顶点的无向完全图有（）条边。

（1 分）

A

$4$

B

$6$

C

$8$

D

$12$

第 8 题 B2 未作答

判断题： $n$ 个顶点的有向完全图有 $n(n-1)$ 条弧（任意两点间双向各一条）。

（1 分）

A

正确

B

错误

第 9 题 B3 未作答

判断题：树 = 连通且无环的无向图； $n$ 个顶点的树恰有 $n-1$ 条边。

（1 分）

A

正确

B

错误

第 10 题 B4 未作答

判断题：边数接近 $n^2$ 的图是稠密图，边数接近 $n$ 的图是稀疏图。

（1 分）

A

正确

B

错误

第 11 题 B5 未作答

判断题：无向图中任意两个顶点之间都存在路径，则称该图是连通图；否则是非连通图（可分成若干连通分量）。

（1 分）

A

正确

B

错误

第 12 题 B6 未作答

判断题：带权图的每条边有一个数值（权），如距离、费用、时间。

（1 分）

A

正确

B

错误

叁

图的存储

7 QUESTIONS · 2 POINTS EACH

第 13 题 C1 未作答

判断题：邻接矩阵用 $g[i][j]$ 表示顶点 $i$ 到 $j$ 是否有边（或边权）。

（1 分）

A

正确

B

错误

第 14 题 C2 未作答

判断题： $n$ 个顶点的邻接矩阵占 $O(n^2)$ 空间。

（1 分）

A

正确

B

错误

第 15 题 C3 未作答

判断题：邻接表为每个顶点维护一个链表（邻居列表）。

（1 分）

A

正确

B

错误

第 16 题 C4 未作答

判断题： $n$ 个顶点 $m$ 条边的邻接表占 $O(n+m)$ 空间。

（1 分）

A

正确

B

错误

第 17 题 C5 未作答

判断题：稀疏图适合邻接表、稠密图适合邻接矩阵。

（1 分）

A

正确

B

错误

第 18 题 C6 未作答

判断题：邻接矩阵判断两点是否有边只需 $O(1)$ （直接查 g[i][j]）。

（1 分）

A

正确

B

错误

第 19 题 C7 未作答

判断题：邻接表遍历某顶点的所有邻居，用时与它的度数成正比。

（1 分）

A

正确

B

错误

肆

图的遍历

7 QUESTIONS · 2 POINTS EACH

第 20 题 D1 未作答

判断题：DFS 沿一条路径走到底，走不动才回溯——"一条路走到黑"。

（1 分）

A

正确

B

错误

第 21 题 D2 未作答

判断题：BFS 按"离起点距离由近到远"逐层访问——先访问的近邻、后远邻。

（1 分）

A

正确

B

错误

第 22 题 D3 未作答

判断题：DFS 用栈（或递归的系统栈）、BFS 用队列实现。

（1 分）

A

正确

B

错误

第 23 题 D4 未作答

判断题：DFS/BFS 都要用 visited 标记已访问顶点，防止重复访问和死循环。

（1 分）

A

正确

B

错误

第 24 题 D5 未作答

判断题：DFS/BFS 遍历图的时间复杂度是 $O(n + m)$ （每个顶点和每条边各访问一次）。

（1 分）

A

正确

B

错误

第 25 题 D6 未作答

判断题：从每个未访问顶点出发做 DFS/BFS，启动的总次数 = 连通分量个数。

（1 分）

A

正确

B

错误

第 26 题 D7 未作答

判断题：同一张图，DFS 序和 BFS 序通常不同（DFS 深入、BFS 逐层）。

（1 分）

A

正确

B

错误

伍

图的性质

6 QUESTIONS · 2 POINTS EACH

第 27 题 E1 未作答

判断题： $n$ 个顶点的连通无向图至少有 $n-1$ 条边（树是最少的）。

（1 分）

A

正确

B

错误

第 28 题 E2 未作答

$5$ 个顶点的无向完全图有（）条边。

（1 分）

A

$5$

B

$10$

C

$15$

D

$20$

第 29 题 E3 未作答

某无向图有 $6$ 条边，所有顶点的度数之和是（）。

（1 分）

A

$6$

B

$3$

C

$12$

D

$24$

第 30 题 E4 未作答

判断题：有向图中所有顶点入度之和 = 出度之和 = 边数。

（1 分）

A

正确

B

错误

第 31 题 E5 未作答

判断题：连通图的生成树 = 包含全部顶点、恰有 $n-1$ 条边的连通子图。

（1 分）

A

正确

B

错误

第 32 题 E6 未作答

判断题：最小生成树（MST）是边权和最小的生成树，Prim/Kruskal 算法可求。

（1 分）

A

正确

B

错误

陆

路径与最短路

7 QUESTIONS · 2 POINTS EACH

第 33 题 F1 未作答

判断题：无权图路径长度 = 经过的边数；带权图路径长度 = 边权和。

（1 分）

A

正确

B

错误

第 34 题 F2 未作答

判断题：无权图中 BFS 首次访问某顶点的距离就是最短距离。

（1 分）

A

正确

B

错误

第 35 题 F3 未作答

判断题：无权图（每步代价相同）上，BFS 第一次访问某顶点时的层数（dist 值）就是它到起点的最短距离。

（1 分）

A

正确

B

错误

第 36 题 F4 未作答

判断题：BFS 求最短路时，dist 数组初值设 $-1$ （未访问），起点设 $0$ —— $-1$ 同时兼任"未访问"标记。

（1 分）

A

正确

B

错误

第 37 题 F5 未作答

判断题：BFS 求最短路时用 pre 数组记录每个节点的来路（上一个节点），从终点沿 pre 回溯到起点，就能还原出最短路径。

（1 分）

A

正确

B

错误

第 38 题 F6 未作答

判断题：网格迷宫的最短路 = BFS 逐层扩散；泛洪算法（Flood Fill）本质上也是"从起点逐层扩散标记"的同一形态。

（1 分）

A

正确

B

错误

第 39 题 F7 未作答

判断题：多源 BFS = 把所有起点先入队、dist 都设 $0$ ，一次 BFS 即可求出每个节点到最近起点的距离。

（1 分）

A

正确

B

错误

柒

存储与实现

6 QUESTIONS · 2 POINTS EACH

第 40 题 G1 未作答

判断题：int g[N][N]; 中 g[i][j] = 1 表示边 $(i,j)$ 存在（无权图），带权图存权值。

（1 分）

A

正确

B

错误

第 41 题 G2 未作答

判断题：vector<int> g[N]; 中 g[i] 是顶点 $i$ 的邻居列表。

（1 分）

A

正确

B

错误

第 42 题 G3 未作答

判断题：无向图加边 $(u,v)$ 时，邻接表要 g[u].push_back(v) 和 g[v].push_back(u) 两次。

（1 分）

A

正确

B

错误

第 43 题 G4 未作答

判断题：邻接表中顶点 $i$ 的度数 = g[i].size()；邻接矩阵中 = 第 $i$ 行的 1 的个数。

（1 分）

A

正确

B

错误

第 44 题 G5 未作答

判断题：从一个顶点 DFS 后统计 visited 为真的个数 = $n$ ，则图连通。

（1 分）

A

正确

B

错误

第 45 题 G6 未作答

判断题：读入图通常先读 $n$ （顶点数）和 $m$ （边数），再逐条读 $u\ v$ （或带权 $u\ v\ w$ ）。

（1 分）

A

正确

B

错误

捌

易错综合

5 QUESTIONS · 2 POINTS EACH

第 46 题 H1 未作答

判断题：无向图边数 = 所有顶点度数之和 ÷ 2。

（1 分）

A

正确

B

错误

第 47 题 H2 未作答

判断题：无向图的邻接矩阵是对称矩阵（ $g[i][j] = g[j][i]$ ）。

（1 分）

A

正确

B

错误

第 48 题 H3 未作答

判断题：自环 = 起点终点相同的边（贡献 2 个度）；重边 = 两点间多条边。

（1 分）

A

正确

B

错误

第 49 题 H4 未作答

判断题：DFS/BFS 忘记标记 visited 会重复访问，无向图上甚至死循环。

（1 分）

A

正确

B

错误

第 50 题 H5 未作答

下列说法错误的是（）。

（1 分）

A

$n$ 顶点连通图至少 $n-1$ 条边

B

完全图边数 $n(n-1)/2$

C

BFS 用队列

D

邻接矩阵空间 $O(n)$

玖

邻接矩阵代码

6 QUESTIONS · 2 POINTS EACH

第 51 题 I1 未作答

01const int N = 10;
02int g[N][N];   // 邻接矩阵，全局数组默认全 0（无边）

判断题：全局数组 g 默认初始化为 0， $0$ 表示没有边。

（1 分）

A

正确

B

错误

第 52 题 I2 未作答

01const int N = 10;
02int g[N][N];
03
04// 无向图加边 (u, v)：
05g[u][v] = 1;
06______;

横线处应填（）。

（1 分）

A

g[v][u] = 1

B

g[u][v] = 2

C

g[v][v] = 1

D

g[u][u] = 1

第 53 题 I3 未作答

01const int N = 10;
02int g[N][N];
03
04// 有向图加边（u → v 的弧）：
05g[u][v] = 1;

判断题：有向图加边只写一个方向，g[v][u] 不加。

（1 分）

A

正确

B

错误

第 54 题 I4 未作答

01const int N = 10;
02int g[N][N];
03// 无向图邻接矩阵
04int deg(int u, int n) {
05    int d = 0;
06    for (int j = 1; j <= n; j++)
07        d += g[u][j];
08    return d;
09}

判断题：无向图中顶点 $u$ 的度数 = 矩阵第 $u$ 行中 $1$ 的个数（行和）。

（1 分）

A

正确

B

错误

第 55 题 I5 未作答

01const int N = 10;
02int g[N][N];
03
04// 判断 u 和 v 之间是否有边：
05if (______) cout << "有边";

横线处应填（）。

（1 分）

A

g[u][v]

B

g[u][v] == 0

C

g[u] + g[v]

D

u == v

第 56 题 I6 未作答

01const int N = 10;
02int g[N][N];
03// 无向图：顶点 1-4，边 (1,2) (1,3) (1,4) (3,4)
04// 输出所有边（i < j 只输出一次）：
05for (int i = 1; i <= n; i++)
06    for (int j = i + 1; j <= n; j++)
07        if (g[i][j]) cout << i << ' ' << j << endl;

判断题：j 从 i+1 开始避免无向边输出两次。

（1 分）

A

正确

B

错误

拾

邻接表代码

7 QUESTIONS · 2 POINTS EACH

第 57 题 J1 未作答

01#include <vector>
02const int N = 10;
03vector<int> g[N];   // 邻接表：g[i] 存顶点 i 的所有邻居

判断题：g[i] 是一个动态数组（vector），存放顶点 $i$ 的邻居列表。

（1 分）

A

正确

B

错误

第 58 题 J2 未作答

01#include <vector>
02const int N = 10;
03vector<int> g[N];
04
05// 无向图加边 (u, v)：
06g[u].push_back(v);
07______;

横线处应填（）。

（1 分）

A

g[v].push_back(u)

B

g[u].push_back(u)

C

g[v].push_back(v)

D

（什么都不写）

第 59 题 J3 未作答

01#include <vector>
02const int N = 10;
03vector<int> g[N];
04
05// 有向图加边（u → v）：
06g[u].push_back(v);

判断题：有向图只 push_back 一次，出边进 g[u]。

（1 分）

A

正确

B

错误

第 60 题 J4 未作答

01#include <vector>
02const int N = 10;
03vector<int> g[N];
04
05// 遍历顶点 u 的所有邻居：
06for (int v : g[u]) cout << v << ' ';

判断题：范围 for 逐个取出 g[u] 中的邻居，与度数成正比。

（1 分）

A

正确

B

错误

第 61 题 J5 未作答

01#include <vector>
02const int N = 10;
03vector<int> g[N];
04
05// 顶点 u 的度数（无向图）：
06int d = g[u].size();

判断题：g[u].size() 就是顶点 $u$ 的度数。

（1 分）

A

正确

B

错误

第 62 题 J6 未作答

01// 稀疏图 n = 100000, m = 100000：
02// 邻接矩阵：100000² 个 int 会爆内存
03// 邻接表：vector<int> g[100001] 只存 2m 个元素

判断题：稀疏大图必须用邻接表，邻接矩阵 $n^2$ 空间会爆。

（1 分）

A

正确

B

错误

第 63 题 J7 未作答

01struct Edge { int u, v, w; };   // 边表：每条边一行（起点、终点、权）
02Edge e[M];

判断题：边表 = 结构体数组存所有边，适合按边遍历（如 Kruskal 排序边）。

（1 分）

A

正确

B

错误

拾壹

DFS 代码

7 QUESTIONS · 2 POINTS EACH

第 64 题 K1 未作答

01const int N = 10;
02vector<int> g[N];
03bool vis[N];
04
05// DFS 递归框架
06void dfs(int u) {
07    vis[u] = true;              // 标记已访问
08    for (int v : g[u])          // 遍历所有邻居
09        if (!vis[v]) dfs(v);    // 未访问则深入
10}

判断题：DFS 框架 = 标记自己 + 对每个未访问邻居递归深入。

（1 分）

A

正确

B

错误

第 65 题 K2 未作答

// 无向图：1-2、1-3、2-4、3-4（邻接表按编号升序）
// 从 1 开始 DFS（访问时输出编号），输出为（ ）。

（1 分）

A

1 2 4 3

B

1 3 4 2

C

1 2 3 4

D

1 4 2 3

第 66 题 K3 未作答

01const int N = 10;
02vector<int> g[N];
03bool vis[N];
04int n;
05
06// 统计连通分量个数
07int cnt = 0;
08for (int i = 1; i <= n; i++)
09    if (!vis[i]) {
10        cnt++;
11        dfs(i);   // 从 i 出发遍历整个分量
12    }

判断题：cnt 每次从"未访问顶点"出发 DFS 都加 1——cnt 即连通分量数。

（1 分）

A

正确

B

错误

第 67 题 K4 未作答

01// 从顶点 1 做一次 DFS，结束后统计 vis[1..n] 为 true 的个数
02int reach = 0;
03for (int i = 1; i <= n; i++)
04    if (vis[i]) reach++;
05// reach == n 说明图连通

判断题：一次 DFS 后 reach == n ⇔ 图连通。

（1 分）

A

正确

B

错误

第 68 题 K5 未作答

01// 无向图 DFS 判环：访问邻居 v 时，若 v 已访问且 v 不是 u 的父亲，则有环
02void dfs(int u, int fa) {
03    vis[u] = true;
04    for (int v : g[u]) {
05        if (!vis[v]) dfs(v, u);
06        else if (v != fa) hasCycle = true;   // 遇到非父亲的已访问点 = 有环
07    }
08}

判断题：无向图 DFS 中"已访问邻居 ≠ 父亲"说明有环（两条路径相遇）。

（1 分）

A

正确

B

错误

第 69 题 K6 未作答

01const int N = 10;
02vector<int> g[N];
03bool vis[N];
04
05// 统计 u 所在连通块的顶点数
06int dfs(int u) {
07    vis[u] = true;
08    int sz = 1;                    // 自己算 1 个
09    for (int v : g[u])
10        if (!vis[v]) sz += dfs(v); // 加上每个子连通块
11    return sz;
12}

判断题：sz = 1 + 各子树大小——连通块大小的递归统计。

（1 分）

A

正确

B

错误

第 70 题 K7 未作答

判断题：图很大（如 $10^5$ 个顶点排成一条链）时，DFS 递归深度可能过大导致栈溢出——可改用显式栈或 BFS。

（1 分）

A

正确

B

错误

拾贰

BFS 代码

7 QUESTIONS · 2 POINTS EACH

第 71 题 L1 未作答

01const int N = 10;
02vector<int> g[N];
03bool vis[N];
04
05// BFS 队列框架
06queue<int> q;
07q.push(s); vis[s] = true;         // 起点入队并标记
08while (!q.empty()) {
09    int u = q.front(); q.pop();   // 出队访问
10    for (int v : g[u])
11        if (!vis[v]) {
12            vis[v] = true;        // 入队时标记（防重复入队）
13            q.push(v);
14        }
15}

判断题：BFS 框架 = 起点入队 → 循环出队、把未访问邻居标记并入队。

（1 分）

A

正确

B

错误

第 72 题 L2 未作答

// 无向图：1-2、1-3、1-4、3-4（邻接表按编号升序）
// 从 1 开始 BFS（出队时输出编号），输出为（ ）。

（1 分）

A

1 2 3 4

B

1 3 4 2

C

1 4 3 2

D

1 2 4 3

第 73 题 L3 未作答

01const int N = 10;
02vector<int> g[N];
03int dist[N];   // dist[v] = 起点到 v 的最短距离（-1 表示未访问）
04
05// BFS 求无权图最短路
06queue<int> q;
07dist[s] = 0; q.push(s);
08while (!q.empty()) {
09    int u = q.front(); q.pop();
10    for (int v : g[u])
11        if (dist[v] == -1) {
12            dist[v] = dist[u] + 1;
13            q.push(v);
14        }
15}

判断题：dist[v] = dist[u] + 1——BFS 首次到达就是最短路（无权图）。

（1 分）

A

正确

B

错误

第 74 题 L4 未作答

无向图：1-2、2-3、3-4（一条链），从 1 开始 BFS

dist[1]=0, dist[2]=1, dist[3]=2, dist[4]=3

判断题：链上 BFS 的距离 = 顶点到起点的边数。

（1 分）

A

正确

B

错误

第 75 题 L5 未作答

判断题：BFS 同样可以判断连通性——从起点 BFS 后检查所有顶点是否被访问。

（1 分）

A

正确

B

错误

第 76 题 L6 未作答

判断题：求无权图最短路用 BFS（首次到达即最短）；DFS 不能保证最短路。

（1 分）

A

正确

B

错误

第 77 题 L7 未作答

判断题：visited 标记的本质是剪枝——保证每个顶点只处理一次，遍历总代价 $O(n+m)$ 。

（1 分）

A

正确

B

错误

拾叁

图的综合代码

6 QUESTIONS · 2 POINTS EACH

第 78 题 M1 未作答

01const int N = 10;
02vector<int> g[N];
03int n, m;   // n 顶点数、m 边数
04
05cin >> n >> m;
06for (int i = 1; i <= m; i++) {
07    int u, v;
08    cin >> u >> v;
09    g[u].push_back(v);
10    g[v].push_back(u);   // 无向图双向
11}

判断题：读入 $m$ 条边，每条无向边往两个邻接表各加一次。

（1 分）

A

正确

B

错误

第 79 题 M2 未作答

01const int N = 10;
02int g[N][N];          // 邻接矩阵
03vector<int> adj[N];   // 转换目标：邻接表
04
05for (int i = 1; i <= n; i++)
06    for (int j = 1; j <= n; j++)
07        if (g[i][j]) adj[i].push_back(j);

判断题：扫描矩阵每个 $1$ ，往对应行加邻居—— $O(n^2)$ 转换。

（1 分）

A

正确

B

错误

第 80 题 M3 未作答

01const int N = 10;
02vector<int> g[N];
03// 统计所有顶点中度数最大的
04int maxDeg = 0;
05for (int i = 1; i <= n; i++)
06    maxDeg = max(maxDeg, (int)g[i].size());

判断题：g[i].size() 是度数，取 max 即最大度数。

（1 分）

A

正确

B

错误

第 81 题 M4 未作答

01const int N = 10;
02int g[N][N];
03int n;
04// 判断无向图是否是完全图：边数 == n*(n-1)/2
05int m = 0;
06for (int i = 1; i <= n; i++)
07    for (int j = i + 1; j <= n; j++)
08        if (g[i][j]) m++;
09// m == n*(n-1)/2 即完全图

判断题：统计 $i < j$ 的边数等于 $n(n-1)/2$ 即完全图。

（1 分）

A

正确

B

错误

第 82 题 M5 未作答

01const int N = 10;
02vector<int> g[N];
03// 无向图统计边数：度数之和 ÷ 2
04int sum = 0;
05for (int i = 1; i <= n; i++) sum += g[i].size();
06int m = sum / 2;

判断题：度数和 = $2m$ ，所以 sum / 2 就是边数。

（1 分）

A

正确

B

错误

第 83 题 M6 未作答

无向图：1-2、1-3、2-4、3-4

DFS 从 1：1 2 4 3（深入）

BFS 从 1：1 2 3 4（逐层）

判断题：DFS 序"深入优先"（2 之后先 4）、BFS 序"逐层优先"（先 3 后 4）——同一张图两种序。

（1 分）

A

正确

B

错误

拾肆

完善程序

7 QUESTIONS · 2 POINTS EACH

第 84 题 N1 未作答

01const int N = 10;
02int g[N][N];
03
04// 无向图加边 (u, v)：
05g[u][v] = 1;
06______;

横线处应填（）。

（1 分）

A

g[v][u] = 1

B

g[u][v] = 0

C

g[v][v] = 1

D

g[u][u] = 1

第 85 题 N2 未作答

01const int N = 10;
02vector<int> g[N];
03bool vis[N];
04
05void dfs(int u) {
06    vis[u] = true;
07    for (int v : g[u])
08        if (!vis[v]) ______;
09}

横线处应填（）。

（1 分）

A

dfs(v)

B

dfs(u)

C

vis[v] = true

D

return

第 86 题 N3 未作答

01const int N = 10;
02vector<int> g[N];
03bool vis[N];
04
05void bfs(int s) {
06    queue<int> q;
07    q.push(s); vis[s] = true;
08    while (!q.empty()) {
09        int u = q.front(); q.pop();
10        for (int v : g[u])
11            if (!vis[v]) {
12                vis[v] = true;
13                ______;
14            }
15    }
16}

横线处应填（）。

（1 分）

A

q.push(v)

B

q.push(u)

C

q.pop()

D

return

第 87 题 N4 未作答

01const int N = 10;
02vector<int> g[N];
03bool vis[N];
04
05void dfs(int u) {
06    ______;              // 标记当前顶点已访问
07    for (int v : g[u])
08        if (!vis[v]) dfs(v);
09}

横线处应填（）。

（1 分）

A

vis[u] = true

B

vis[v] = true

C

vis[u] = false

D

return

第 88 题 N5 未作答

01const int N = 10;
02vector<int> g[N];
03bool vis[N];
04int n, cnt = 0;
05
06for (int i = 1; i <= n; i++)
07    if (!vis[i]) {
08        ______;
09        dfs(i);
10    }

横线处应填（）。

（1 分）

A

cnt++

B

cnt = 0

C

vis[i] = true

D

i++

第 89 题 N6 未作答

01const int N = 10;
02int g[N][N];
03// 无向图顶点 u 的度数 = 第 u 行的和
04int deg = 0;
05for (int j = 1; j <= n; j++)
06    deg += ______;

横线处应填（）。

（1 分）

A

g[u][j]

B

g[j][u]

C

g[u][u]

D

g[j][j]

第 90 题 N7 未作答

01const int N = 10;
02vector<int> g[N];
03int dist[N];   // 初始全 -1（未访问）
04
05void bfs(int s) {
06    queue<int> q;
07    dist[s] = 0;
08    q.push(s);
09    while (!q.empty()) {
10        int u = q.front(); q.pop();
11        for (int v : g[u])
12            if (dist[v] == -1) {
13                dist[v] = ______;
14                q.push(v);
15            }
16    }
17}

横线处应填（）。

（1 分）

A

dist[u] + 1

B

dist[v] + 1

C

1

D

dist[u]

拾伍

代码综合应用

5 QUESTIONS · 2 POINTS EACH

第 91 题 O1 未作答

无向图：1-2、1-3、2-4、3-4，从 1 开始 DFS（邻接表升序）

DFS 输出为（）。

（1 分）

A

1 2 4 3

B

1 2 3 4

C

1 3 4 2

D

4 3 2 1

第 92 题 O2 未作答

无向图：1-2、1-3、2-4、3-4，从 1 开始 BFS（邻接表升序）

BFS 输出为（）。

（1 分）

A

1 2 4 3

B

1 2 3 4

C

1 3 2 4

D

1 4 3 2

第 93 题 O3 未作答

无向图 n=6：

连通分量1：1-2-3（三条边的三角形）

连通分量2：4-5

连通分量3：6（孤立点）

连通分量个数是（）。

（1 分）

A

$2$

B

$3$

C

$1$

D

$6$

第 94 题 O4 未作答

无向图：1-2、2-3、3-4、4-5（一条链），从 1 开始 BFS

顶点 5 的最短距离 dist[5] 是（）。

（1 分）

A

$3$

B

$4$

C

$5$

D

$1$

第 95 题 O5 未作答

无向图 4 个顶点、6 条边（完全图 K4）

顶点度数之和是（），每个顶点度数是（）。

（1 分）

A

$6$ 和 $2$

B

$12$ 和 $3$

C

$12$ 和 $2$

D

$6$ 和 $3$

拾陆

代码易错

5 QUESTIONS · 2 POINTS EACH

第 96 题 P1 未作答

01// DFS 忘记标记 vis[u]：
02void dfs(int u) {
03    for (int v : g[u])
04        dfs(v);   // 没有 vis 判断，也没有标记
05}

判断题：无向图上 u 会访问邻居、邻居又访问回 u——死循环/无限递归。

（1 分）

A

正确

B

错误

第 97 题 P2 未作答

// 无向图加边 (u, v) 只写：
g[u].push_back(v);
// 漏了 g[v].push_back(u)

判断题：无向图只加一条边，会导致从 v 出发找不到 u——图"单行道化"。

（1 分）

A

正确

B

错误

第 98 题 P3 未作答

01const int N = 10;
02vector<int> g[N];   // 下标 0 ~ N-1
03// 顶点编号 1 ~ n 时，直接 g[10] 会越界

判断题：数组下标从 0 开始，顶点编号从 1 开始时要开 g[N+1] 或编号减 1。

（1 分）

A

正确

B

错误

第 99 题 P4 未作答

01// DFS 缺少"已访问"出口：
02void dfs(int u) {
03    for (int v : g[u]) {
04        dfs(v);      // 无 vis 判断
05    }
06}

判断题：即使单次调用能结束，重复访问同一顶点也会让复杂度爆炸——出口（vis）不可少。

（1 分）

A

正确

B

错误

第 100 题 P5 未作答

下列说法错误的是（）。

（1 分）

A

DFS 用栈、BFS 用队列

B

邻接表空间 $O(n+m)$

C

度数和 = $2 \times$ 边数

D

BFS 能保证带权图最短路

重置作答

第 10 章 图论基础 · 知识细节练习

判 分 报 告

图的基本概念

特殊图

图的存储

图的遍历

图的性质

路径与最短路

存储与实现

易错综合

邻接矩阵代码

邻接表代码

DFS 代码

BFS 代码

图的综合代码

完善程序

代码综合应用

代码易错

打印

导出 HTML 子卷

第 10 章图论基础 · 知识细节练习

判分报告