图

解释：

• II (6,6,6,6,3,3,2,2)：所有顶点度数之和为 $6+6+6+6+3+3+2+2 = 34$，是奇数，违反了图论中“图的度数和必须为偶数”的基本性质。
• IV (8,7,7,6,4,2,1,1)：包含一个度数为 8 的顶点，但整个图仅有 8 个顶点，这意味着该顶点需与其余 7 个顶点相连。然而序列中存在度数为 1 的顶点，其只能与一个顶点相连，无法满足与度数为 8 的顶点的连接需求。

• 当 u 和 v 位于同一 BFS 层时，它们的最短路径长度相等，即 $d(r, u) = d(r, v)$
• 当 u 比 v 更早被访问时，若不在同一层，则 $d(r, u) < d(r, v)$

解释：

• 在无向图中，顶点集合大小为 $ n $ 时，最多可构造 $ \frac{n(n-1)}{2} $ 条边。
• 对于每一条可能的边，存在两种状态：存在 或 不存在。
• 因此，所有可能的无向图数量等于从 $ \frac{n(n-1)}{2} $ 条边中进行二元选择的组合数： $$ 2^{\frac{n(n-1)}{2}} $$

解析

• P 的正确性：在无向图中，添加一条边会使两个顶点的度数各增加 1。由于每次操作都改变两个顶点的奇偶性，奇度顶点的总数始终为偶数（如从偶数变为偶数 +2 或偶数 -2）。
• Q 的正确性：每条边对总度数的贡献为 2（连接两个顶点），因此所有顶点的度数之和恒等于 $2 \times$ 边数，必然是偶数。即使存在奇数度数的顶点，其总和仍会被偶数个奇数相加抵消（如 $3 + 5 = 8$）。

有向无环图（DAG）的核心特性

• 拓扑排序支持：通过无环结构实现任务顺序排列
• 依赖管理优势：天然适合表达任务间的先后约束关系
• 调度优化能力：可有效进行资源分配与进度规划

DAG 的这些特性使其成为项目管理工具（如甘特图、PERT 图）的基础数据结构，能避免循环依赖导致的逻辑矛盾。

解析：

• 有环图：最大边数为 $ \frac{n(n-1)}{2} $
• 无环图：边数最多的无环图是一个生成树，此时边数为 $ n-1 $

因此，正确答案是 $ n-1 $ 条边。

以下解释是针对本题前一部分的内容：

要使顶点 i 成为汇点，必须不存在从 i 到任何其他顶点的边。根据题目给出的输入条件，A[i][j]=1 表示存在从 i 到 j 的边，A[i][j]=0 表示不存在该边。对于 i 成为汇点，需要满足：对所有 j，A[i][j]=0（无出边），且对所有 j，A[j][i]=1（所有其他顶点都指向 i）。上述伪代码从 i=0 开始检查每个顶点是否为汇点。它实际上会检查 i 之后的所有顶点 j 是否可能成为汇点。该算法的巧妙之处在于不检查 j 小于 i 的情况。循环选出的 i 可能不是汇点，但确保不会忽略潜在的汇点。最终在 do-while 循环后会验证 i 是否真正为汇点。

当 A[i][j]为 0 时，i 是潜在汇点。因此 E1 应为!A[i][j]。若此条件不成立，则 i 不是汇点。所有 j<i 也不能是汇点，因为不存在从 i 到 j 的边。此时下一个潜在汇点可能是 j。所以 E2 应为 i=j。

关于本题的解释：
以下伪代码验证上述选出的潜在汇点是否确实为汇点。

flag = 1;
for (j = 0; j < n; j++)
    if ((j != i) && E3)
        flag = 0;

flag=0 表示 i 不是汇点。一旦发现 i 不符合汇点条件，立即设置 flag=0。若存在任意 j≠i 使得以下任一条件成立，则 i 不是汇点：

• 出边存在：A[i][j] = 1（存在从 i 出发的边）
• 未被指向：A[j][i] = 0（未被其他顶点指向）

因此 E3 应为 (A[i][j] || !A[j][i])。选项 D 正确。

在 Prim 算法中，我们从任意一个节点开始，不断探索已包含节点的最小成本邻居。具体执行过程如下：

1. 初始化：选择任意起始节点（如 d），将其加入生成树集合。
2. 迭代扩展：每次从未选边中选择连接已选节点与未选节点的最小权重边。
3. 终止条件：当所有节点均被包含时停止。

选项分析：

• 正确选项需满足每一步都选择当前可扩展的最小权重边。
• 选项 C 的边序列 (d, f), (f, c), (d, a), (a, b), (c, e), (f, h), (g, h), (g, i) 符合 Prim 算法的贪心策略。
• 其他选项存在提前选择非最小权重边或跳过必要连接的情况。

当图中所有边的权重相等时，最小生成树的构造可通过以下方式实现：

• 深度优先搜索（DFS）：通过遍历图构建深度优先树，该树即为有效生成树
• 时间复杂度分析：DFS 的时间复杂度由访问所有顶点（n）和边（m）决定，因此总时间为 O(m+n)
• 结论：此方法在等权图中可直接获得最优解，无需比较权重排序

解析

• 情况 1：如果删除的是 G 中的孤立顶点（即该顶点本身构成一个连通分量），则 G 的连通分量数会减少为 7。
• 情况 2：如果 G 是星型图，则删除其关节点后会得到 19 个连通分量。
  因此，G 的连通分量数量应介于 7 到 19 之间。

当顶点按差值为 12 连接时，连通分量数减少至 4：

• 第一列（1-4）与第五列（9-12）相连
• 第二列（5-8）与第六列（13-16）相连
• 第三列（17-20）与第七列（25-28）相连
• 第四列（21-24）与第八列（29-32）相连

由于差值为 8 的连接关系已被差值为 12 的连接覆盖，所有顶点最终归并为 4 个独立连通分量。因此选项 (B) 正确。

解析：

• 广度优先搜索（BFS）执行的是层级遍历
• 使用队列可以很好地实现这一特性
• 队列采用先进先出（FIFO）的顺序
• 先入队的节点会首先被探索，从而保持遍历的顺序

解析： 根据 DFS 的时间戳规则：

• 发现时间戳 按递增顺序记录首次访问节点的顺序
• 完成时间戳 按递减顺序记录回溯时的节点完成顺序

选项 A 的划分符合以下访问路径：

1. 从起点 a 出发，依次访问 b → e
2. 回溯至 a 后继续访问 c → d → h
3. 最终访问剩余分支 f → g

该顺序与时间戳的递增/递减规律完全匹配，因此选项 A 正确。

解释

根据 DFS 时间戳规则：

• 发现时间戳较小的节点先被访问
• 完成时间戳较大的节点最后被回溯

选项 A 中的时间戳顺序符合 DFS 遍历的特性。
其他选项均存在时间戳矛盾（如子树完成时间早于父节点发现时间等）。

解释：
邻接表表示法具有以下优势：

1. 空间效率更高：特别适合稀疏图，节省存储空间。
2. 图遍历算法时间复杂度更低：DFS 和 BFS 在邻接表中为 $O(V + E)$，而在邻接矩阵中为 $O(V^2)$。
3. 添加新顶点更灵活：相较于邻接矩阵，邻接表更容易扩展顶点数量。

Dijkstra 算法执行流程解析：

1. 当算法处理到顶点 C 时，其邻接顶点 D 和 E 的临时距离分别被计算为 7 和 6
2. 此时优先级队列中最小距离顶点为 E（距离值 6 < 7）
3. 根据算法规则，下一步将选择距离最小的顶点 E 进行松弛操作
4. 最终通过路径 S → A → C → E → T 构成最短路径 SACET

关键结论：由于 Dijkstra 算法始终选择当前已知最短距离的顶点进行扩展，因此在 C 节点处理阶段会选择距离更小的 E 节点继续搜索

Dijkstra 单源最短路径算法不能保证在包含负权边的图中正确工作，但该算法在给定图中有效。
让我们逐步验证：

• 第一次遍历后
  • b: 1
  • b 是最小值，因此 b 的最短距离为 1。
• 第二次遍历后
  • c: 3，e: -2
  • e 是最小值，因此 e 的最短距离为 -2
• 第三次遍历后
  • c: 3，f: 0
  • f 是最小值，因此 f 的最短距离为 0
• 第四次遍历后
  • c: 3，g: 3
  • 两者相同，选择 g，因此 g 的最短距离为 3
• 第五次遍历后
  • c: 3，h: 5
  • c 是最小值，因此 c 的最短距离为 3
• 第六次遍历后
  • h: -2
  • h 是最小值，因此 h 的最短距离为 -2

注意：虽然最终所有顶点都被处理，但由于图中存在负权边（如 e→h 的 -4），Dijkstra 算法理论上无法保证正确性。但在本例中，由于负权边未形成负权环且起点 a 到相关顶点的路径权重始终递增，算法仍能得出正确结果。

• Dijkstra 算法

  • 时间复杂度：O(|V|² + |E|)
  • 适用于有权图

• Warshall 算法

  • 时间复杂度：O(|V|³)
  • 通常用于传递闭包，而非最短路径

• DFS

  • 不适用于寻找最短路径

• BFS

  • 时间复杂度：O(|E| + |V|)
  • 适用于无权图，能有效找到最短路径

解析：

1. Bellman Ford 算法的基本时间复杂度为 Θ(VE)
   • V 表示顶点数量
   • E 表示边的数量
2. 在完全图中，边数 E 满足 E = Θ(V²)
3. 代入计算得最终时间复杂度： $$ Θ(V \times V^2) = Θ(V^3) $$
4. 因此选项 C 是正确答案。

请看以下反例说明：

• 原始图结构
  四条边及对应权重：
  • s-a: 1
  • a-b: 1
  • b-t: 1
  • s-t: 4

   1     1     1
s-----a-----b-----t
 \               /
  \             /
   \___________/
        4

• 修改前最短路径
  路径 s-a → a-b → b-t 总权重 = 1 + 1 + 1 = 3

• 修改后权重变化
  所有边权重 +1 后：

  • s-a: 2
  • a-b: 2
  • b-t: 2
  • s-t: 5

• 修改后路径比较

  • 原路径总权重 = 2 + 2 + 2 = 6
  • 新路径 s-t 总权重 = 5

• 结论
  修改后原最短路径不再是全局最优解，说明"最短路径始终不变"的陈述不成立。

解析

• 核心原理：拓扑排序利用 DAG 的特性，按拓扑序依次松弛每条边，确保每个节点的最短路径被唯一确定。
• 时间复杂度：$O(V + E)$，这是目前已知针对 DAG 的最优解法。
• 对比其他选项：
  • Dijkstra 算法需依赖优先队列，时间复杂度通常为 $O(E \log V)$ 或更高。
  • Bellman Ford 算法虽可处理负权边，但时间复杂度为 $O(VE)$，效率较低。
  • 强连通分量与最短路径问题无直接关联。
• 应用场景：特别适合任务调度、数据流分析等 DAG 相关问题。

• Dijkstra 算法：采用贪心算法，通过每次选择未确定最短路径的顶点中距离最小的节点进行扩展。
• Bellman Ford 算法：基于动态规划，通过松弛操作逐步更新最短路径估计值。
• Floyd Warshall 算法：同样属于动态规划，利用矩阵迭代计算所有点对之间的最短路径。

• 一条单边权重为 5 的路径
• 另一条由权重 2 和 3 组成的双边路径
  它们的总权重相同（2 + 3 = 5）

• Dijkstra 算法：基于贪心策略，每次选择当前距离最小的节点进行松弛操作，优先保证局部最优解。
• Bellman-Ford 算法：通过动态规划迭代所有边，逐步更新最短路径估计值，允许全局调整。
• 结论：两种算法虽然计算路径的方式不同，但在无负权边的情况下，最终得到的最短路径权重必然一致。但由于路径选择策略差异，实际经过的边可能不同。

Bellman-Ford 最短路径算法是单源最短路径算法。因此它只能检测从给定源点可达的负权环，而非图中所有可能存在的负权环。考虑一个不连通图，其中某个负权环完全无法从源点到达的情况。

如果存在负权环，则在最短路径计算中会体现出来——因为每次经过该环都会使路径长度不断减小。

在使用**二进制堆（Binary Heap）**实现的 Dijkstra 算法中，时间复杂度主要来自两部分操作：

1. 取出当前距离最小的顶点：最多执行 $|V|$ 次，每次操作代价是 $\log|V|$，总共是 $O(|V| \log|V|)$。
2. 更新邻接点的距离：最多执行 $|E|$ 次，每次操作代价是 $\log|V|$，总共是 $O(|E| \log|V|)$。

所以总时间复杂度为：

$$O(|V| \log|V| + |E| \log|V|) = O((|E| + |V|) \log|V|)$$

解析

在原始输入矩阵中，若存在从 j 到 k 的边则 A[j, k]=1，否则为 0。

关键分析步骤：

1. 算法本质
   表达式 A[j, k] = max(A[j, k], A[j, i] + A[i, k]) 实际上是在计算从 j 到 k 的路径中经过中间节点 i 的最大边数。每次迭代时，算法尝试通过新增的中间节点 i 来延长已知路径。

2. 数值含义

   - 初始状态：A[j,k] 表示是否存在直接边（1 或 0） - 迭代过程：A[j,k] 最终表示从 j 到 k 的最长路径所含的边数 - 上界约束：由于简单路径不能重复顶点，最长路径至多包含 n-1 条边

3. 结论推导

   - 当 A[j,k] = n-1 时，说明存在一条长度为 n-1 的简单路径（覆盖所有顶点） - 若 A[j,k] ≥ n，则必然存在环（因为简单路径最多 n-1 条边） - 因此 D 选项表述了"简单路径最多包含 A[j,k] 条边"这一必然成立的关系

4. 错误选项排除

   • A 错误：当存在环时 A[j,k] 可能超过 n
   • B 错误：A[j,k] ≥ n-1 仅说明存在长度为 n-1 的路径，但不足以证明存在哈密顿回路
   • C 错误：算法求的是最长路径的边数，而非路径长度（权重总和）

注意：给定的图是无向的，因此边 (u, v) 也意味着 (v, u) 是一条边。

解释：
在无向图中，BFS 构建的最短路径树具有以下性质：

1. 非树边的特性：若边 (u, v) 不在 BFS 树 T 中，则 u 和 v 必须属于同一层或相邻层。
2. 距离差限制：
   • 若 u 和 v 属于同一层（即 d(u) = d(v)），则差值为 0。
   • 若 u 和 v 属于相邻层（如 d(u) = d(v) + 1 或 d(v) = d(u) + 1），则差值为 ±1。
3. 矛盾性分析：
   • 若假设 d(u) – d(v) = 2，则存在更短路径通过边 (u, v) 直接连接 u 和 v，这与 BFS 树定义的最短路径性质矛盾。

因此，在无向图中，非树边两端点的距离差绝对值不可能超过 1。

任务是从顶点 1 到顶点 100 寻找路径中边数最少的方案，其中可以从顶点 i 移动到 i+1 或 $3 \times i$。由于目标是最小化边数，
我们更倾向于选择 $3 \times i$ 的路径。

• 正向尝试 3 的倍数路径
  1 → 3 → 9 → 27 → 81，此时无法继续使用 $3 \times i$ 路径，只能使用 i+1。这种方案会导致较长的路径。

• 反向从终点开始的策略
  若数值不是 3 的倍数则减 1，否则除以 3：
  100 → 99 → 33 → 11 → 10 → 9 → 3 → 1

  因此总共需要 7 条边。

设顶点为 0、1、2 和 3。

x 直接连接顶点 2 和 3。不经过 x 的情况下，从 2 到 3 的最短路径权重为 12（路径为 2-1-0-3）。

当 x 的值大于 12 时，路径 2-3 的直接边权重会超过替代路径 2-1-0-3 的总权重（12），此时最短路径将不再包含权重为 x 的边。因此，x 的最大取值为 12，此时仍满足存在最短路径包含该边的条件。

根据三角不等性原理：

1. 若存在路径 $s \rightarrow \cdots \rightarrow u \rightarrow v$，则满足 $d(s,u) + w(u,v) \geq d(s,v)$
2. 已知 $d(s,u)=53$，$d(s,v)=65$
3. 代入不等式得：$53 + w(u,v) \geq 65$
4. 推导结果：$w(u,v) \geq 12$

• Prim 算法：用于求解给定图的最小生成树（MST）。
• Dijkstra 算法：用于在有权图中从源点到其他所有节点的最短路径。
• Bellman-Ford 算法：用于在可能包含负权边的图中求解从源点到其他所有节点的最短距离。
• Floyd-Warshall 算法：它是一种所有节点对的最短路径算法，用于求解每对顶点之间的最短距离。

因此，选项（D）正确。

解析：
队列（先进先出/FIFO）是广度优先搜索（BFS）的核心数据结构。

• BFS 的核心特性是逐层遍历，即从起始节点出发，优先访问当前层级的所有相邻节点后再进入下一层级。
• 队列遵循 FIFO（First In First Out） 原则，能够保证节点按层级顺序依次被访问：
  • 先入队的节点会先被处理，其邻接节点随后入队；
  • 后入队的节点则等待前序节点处理完成后再处理，从而维持遍历的层次性。
• 相比之下，栈（LIFO）更适合深度优先搜索（DFS），而列表缺乏严格的顺序约束机制。

A

• 将顶点映射到任意实数值时，最短路径保持不变。
• 任何路径上的中间节点值都会相互抵消，最终仅剩起点和终点的值，其总和即为路径成本。
• 因此最短路径保持一致。

关键分析

• D 选项错误在于"当且仅当"的表述。若改为单纯的"如果"则正确。
• 给出的条件是充分而非必要条件，使得"仅当"部分无效。
• 本质上这意味着所有顶点的势能都为 0（因为它们与新顶点 s 通过零权重边相连）。
• B 和 C 选项也因相同原因错误（正负数限制并非必要条件）。

在 DFS 中，若’v’在’u’之后被访问，则以下两种情况必居其一：

1. (u, v) 是一条边。

     u  
   /   \  
  v     w  
 /     / \  
x     y   z  

2. ‘u’ 是叶节点。

     w  
   /   \  
  x     v  
 /     / \  
u     y   z  

在 DFS 中，访问完一个节点后，会先递归访问所有未访问过的子节点。如果没有未访问的子节点（u 是叶节点），则控制权返回到父节点，父节点再访问下一个未访问的子节点。因此选项 (C) 是正确答案。

下图展示了递归树具有最大深度的最坏情况。因此，递归深度为 19（包括第一个节点）。

以下示例说明了 A、B、C 都是错误的，所以正确选项为 D。

树边是深度优先搜索树中包含的边。如果一棵树中有 x 条树边，则该树包含 x+1 个顶点。

当图不连通时，DFS 的输出是一片森林。

1. 所有顶点都连通的情况。此时 k 必须等于 n-1。根据公式计算得连通分量数为 n-k = n-(n-1)=1
2. 没有任何顶点连通的情况。此时 k 必须等于 0。根据公式计算得连通分量数为 n-k = n-0=n

以下是六种不同的拓扑排序：

• a-b-c-d-e-f
• a-d-e-b-c-f
• a-b-d-c-e-f
• a-d-b-c-e-f
• a-b-d-e-c-f
• a-d-b-e-c-f

我们逐一验证所有选项：
选项 (A)：T 的根节点在 G 中永远不可能是关键点。此选项 错误。观察下图 G 的 DFS 树 T：

    r
   / \
a     b

当根节点可以成为关键点时，删除与 T 根节点对应的顶点会将图分割为两个连通分量。因此，T 的根节点在 G 中可能成为关键点。

选项 (B)：T 的根节点在 G 中是关键点当且仅当它有两个或更多子节点。此选项 正确。根据上述示例及以下树结构：

    r
   / \
a     b

若 T 的根节点只有一个子节点，则删除其对应顶点不会使图 G 分割为两个或更多连通分量。因此，T 的根节点至少需要有两个子节点才能成为关键点。

选项 (C)：T 的叶子节点在 G 中可能是关键点。此选项 错误。如下图 T 所示：

    p
   /
q

任何叶子节点仅连接到父节点。删除该叶子节点不会导致图 G 分割为多个连通分量。因此，T 的叶子节点不可能是关键点。

选项 (D)：如果 u 是 G 中的关键点，并且在 T 中 x 是 u 的祖先，y 是 u 的后代，则 G 中从 x 到 y 的所有路径都必须经过 u。此选项 错误。考虑图 G 的示例：

x - w - v - y
 \         /
  u       u

在通过 DFS 得到的树 T 中，u 是 G 的关键点，x 是 u 的祖先，y 是 u 的后代。尽管满足条件，但存在不经过 u 的路径（如 x→w→v→y）。因此，只有选项 B 正确。

考虑一棵完全二叉树，共有 3 层，总共有 7 个元素。每层的元素数量如下：

• 第 1 层：1 个元素
• 第 2 层：2 个元素
• 第 3 层：4 个元素

广度优先搜索（BFS）

进行 广度优先搜索 时，定义集合 A 包含第 1 层和第 2 层的所有元素：

• 第 1 层：第一个元素
• 第 2 层：第二个和第三个元素

因此：

• A = { 第 1、2、3 个元素 }

深度优先搜索（DFS）

进行 深度优先搜索 时，定义集合 B 包含：

• 第 1 层：第一个元素
• 第 2 层：第二个元素
• 第 3 层：第三个元素

因此：

• B = { 第 1、2、4 个元素 }

集合运算分析

• A ∩ B 包含 1 个元素（第 1 层的根节点）
• A - B 表示 A 中不属于 B 的元素，即 第 2 层中剩下的那个元素

结论

|A - B| = 1