系统分析师选择题 - 最小生成树 | 芝士架构

当前 - 选择题 - 最小生成树

题号：0120260500012

单选题

2026年5月第12题

题号：0120260500012

单选题

2026年5月第12题

最小生成树

中等

中频

反馈

连通带权无向图中连接所有顶点且总权值最小的无环子图称为（最小生成树）。

问题（1）

浓缩知识点

最小生成树要求连接所有顶点、边数为 $n-1$ 、不形成回路且总权值最小，可用 Prim 或 Kruskal 算法求解。它解决的是“用最低总代价连通所有节点”的网络设计问题，常见于布线、管网、通信链路选型等场景。与最短路径不同，最小生成树关注整体连通代价，不关心某两个顶点之间路径是否最短；若图不连通，则只能得到各连通分量的最小生成森林。数据库类知识点应先明确数据对象、约束和操作语义。关系模型强调表、元组、属性、键和完整性约束；事务题则围绕原子性、一致性、隔离性和持久性分析。

正确答案

本题考察的是最小生成树。

最小生成树要求连接所有顶点、边数为 $n-1$ 、不形成回路且总权值最小，可用 Prim 或 Kruskal 算法求解。

选项 A：最短路径树。最短路径树关注从源点到其他顶点的最短路径。但它不符合本题限定的“最小生成树”场景。
选项 B：关键路径。该项与本题考查的“最小生成树”场景或定义不匹配。
选项 C：最大流网络。最大流用于容量网络中的流量优化。但它不符合本题限定的“最小生成树”场景。
选项 D：最小生成树。最小生成树连接所有顶点且总权值最小。本题语境与该项一致，正确。

因此，选项 D 正确。