🏷️ 知识点：最小生成树
设无向图 G=(V,E) 和 G’=(V’,E’)，如果 G’ 是 G 的生成树，则下面说法错误的是（ ）。
A. G’ 是 G 的子图 B. G’ 是 G 的连通分量 C. G’ 是 G 的极小连通子图且 V’=V D. G’ 是 G 的一个无环子图
[tag_link]
正确答案：B
生成树是无向连通图的一个子图，它包含原图的所有顶点，并且是树结构，因此是无环的连通图。 选项A正确，因为生成树的顶点集和边集都是原图的子集，所以它是原图的子图。 选项B错误，因为连通分量是极大连通子图，即不能再添加任何顶点或边而保持连通。 生成树是极小连通子图，不是极大连通子图。 对于连通图，其唯一的连通分量是图本身，而生成树是它的一个真子图（除非原图本身就是树），因此生成树不是连通分量。 选项C正确，生成树是极小连通子图，意味着去掉任意一条边都会破坏其连通性，并且顶点集与原图相同（V’=V）。 选项D正确，生成树作为树结构，不包含任何环，因此是无环子图。
在具有 n 个顶点的图 G 中，若最小生成树不唯一，则（ ）。
A. G 的边数一定大于 n-1 B. G 的权值最小的边一定有多条 C. G 的最小生成树代价不一定相等 D. 上述选项都不对
[tag_link]
正确答案：A
最小生成树（MST）不唯一意味着图 G 中存在至少两个不同的生成树，它们的总权值相同且都是最小的。 选项 A 指出 G 的边数一定大于 n-1。 这是因为如果图 G 的边数等于 n-1，则 G 本身是一棵树，其生成树唯一，与 MST 不唯一矛盾。 因此，要存在多个 MST，图 G 必须有多余的边，即边数至少为 n，故边数大于 n-1 必然成立。 选项 B 错误，因为 MST 不唯一并不要求权值最小的边有多条。 例如，一个包含三个顶点、边权分别为 1、2、2 的图，最小权值边只有一条（权值 1），但存在两个 MST（总权值均为 3）。 选项 C 错误，因为所有最小生成树的代价必须相等，否则其中代价较大的就不是“最小”生成树。 综上，选项 A 正确。
求下面带权图的最小（代价）生成树时，可能是克鲁斯卡（Kruskal）算法第 2 次选中但不是普里姆（Prim）算法（从 V4 开始）第 2 次选中的边是（）。
A. (b, e) B. (a, e) C. (d, c) D. (a, b)
[tag_link]
选中的第一条边一定是权值最小的 (V1,V4), B 错误。由于V1和V4已经可达，第二条边含有V1和V4的权值为 8 的一定符合 prim 算法 ，排除 A、D。
已知无向连通图 G 中各边的权值均为 1，下列算法中，一定能够求出图 G 中从某顶点到其余各个顶点最短路径的是（ ）。
I. 普利姆算法
II. 克鲁斯卡尔算法
III. 图的广度优先搜索
A. 仅 I B. 仅 III C. 仅 I、II D. I、II、III
[tag_link]
正确答案：B
各边权值都为 1 时，路径权值就等于经过的边数。BFS 从源点按层扩展，BFS 的层数就是边数，所以某顶点第一次被发现时得到的就是从源点到它的最短路径，III 正确。Prim 和 Kruskal 的目标是最小化整棵生成树的总权值，不是同时最小化某个源点到各顶点的距离，I、II 均不保证成立。因此仅 III 正确，选 B。
设有向图 G=(V,E)，其中顶点集 V 的大小为 n=|V|，每条边 e∈E 都标记有一个唯一的字符（不同边可标记相同字符）。定义字符串集 S 为：所有由 G 中任意一条路径（路径可包含单个顶点，对应空字符串）上的边标记按顺序拼接而成的字符串的集合。以下说法错误的是（ ）
A. 若图 G 无环，则 S 是有限集 B. 若图 G 无环，则 S 中存在长度为 |V| 的字符串 C. 若图 G 有环，则 S 中存在长度大于 |V| 的字符串 D. 若图 G 有环，则 S 中存在长度小于 2|V| 的字符串
[tag_link]
正确答案：B
**【解析】**对于选项 A：若图 G 无环，则任意路径不能重复经过顶点，否则会形成环，因此最长路径的边数不超过n−1。由于图是有限的，所有可能的路径数量有限，每条路径对应一个字符串（可能重复），但字符串集合 S 由有限个字符串组成，故 S 是有限集。A 正确。对于选项 B：若图 G 无环，则任意路径最多经过n个不同的顶点，因此边数最多为n−1，对应的字符串长度最多为n−1。所以 S 中不可能存在长度为n的字符串。B 错误。对于选项 C：若图 G 有环，则存在一个环，可以从环上某点出发沿环行走任意多圈，得到任意长的路径，从而产生长度大于n的字符串。C 正确。对于选项 D：若图 G 有环，S 中至少包含空字符串（长度为0），而0<2n（n≥1），因此存在长度小于2n的字符串。D 正确。综上，说法错误的是 B。
如果具有 个顶点的图是一个环，则它有（ ）棵生成树。
A. B. C. D. 1
[tag_link]
正确答案：B
由于图是一个环，它包含 n 个顶点和 n 条边。 生成树是连接所有顶点且无环的子图，对于环图，只需移除任意一条边即可打破环并得到一棵生成树。 环中共有 n 条边，每条边的移除对应一棵不同的生成树，因此生成树的数量为 n。
已知无向图 G 如下所示，使用克鲁斯卡尔（Kruskal）算法求图 G 的最小生成树，加入到最小生成树中的边依次是（ ）。
A. (b,f), (b,d), (a,e), (c,e), (b,e) B. (b,f), (b,d), (b,e), (a,e), (c,e) C. (a,e), (b,e), (c,e), (b,d), (b,f) D. (a,e), (c,e), (b,e), (b,f), (b,d)
[tag_link]
正确答案：A
Kruskal 算法 按边权递增检查边，只加入不会形成环的边。依次选 (b,f)=5、(b,d)=6；(d,f)=7 会在 b-d-f 中成环，跳过；再选 (a,e)=9、(c,e)=10、(b,e)=11，此时 6 个顶点由 5 条边连通，MST 完成。因此选 A。
下列关于最小生成树的叙述中，正确的是（）。
Ⅰ．最小生成树的代价唯一
Ⅱ．所有权值最小的边一定会出现在所有的最小生成树中
Ⅲ．使用普里姆（Prim）算法从不同顶点开始得到的最小生成树一定相同
Ⅳ．使用普里姆算法和克鲁斯卡尔（Kruskal）算法得到的最小生成树总不相同
A. 仅Ⅰ
B. 仅Ⅱ
C. 仅Ⅰ、Ⅲ
D. 仅Ⅱ、Ⅳ
[tag_link]
正确答案：A
对于 Ⅰ， 最小生成树 的树形可能不唯一，但所有最小生成树的总代价都等于全局最小值，因此代价唯一，Ⅰ正确。
对于Ⅱ，若若干条并列最小边本身构成一个环，生成树必须从环中至少舍弃一条边，所以并非每条最小权边都会出现在所有 MST 中，Ⅱ错误。
对于Ⅲ，取 3 个顶点组成三角形，3 条边权值都相同。从不同顶点开始或采用不同的并列边选择顺序，Prim 可得到不同的 MST，Ⅲ错误。
对于Ⅳ，当 MST 唯一时，Prim 与 Kruskal 必须得到同一棵树，因此“总不相同”错误。故仅Ⅰ正确，选 A。
下列叙述中，不符合 m 阶 B 树定义要求的是()。
A. 根节点最多有 m 棵子树
B. 所有叶结点都在同一层上
C. 各结点内关键字均升序或降序排列
D. 叶结点之间通过指针链接
[tag_link]
正确答案：D
选项 A、B 和 C 都是 B-树的特点，而选项 D 则是 B+ 树的特点。注意区别 B-树和 B+ 树各 自的特点。
已知关键字序列5,8,12,19,28,20,15,22是小根堆(最小堆),插入关键字3,调整后得到的 小 根 堆 是 ( ) 。
A.3,5,12,8,28,20,15,22,19
B.3,5,12,19,20,15,22,8,28
C.3,8,12,5,20,15,22,28,19
D.3,12,5,8,28,20,15,22,19
[tag_link]
正确答案：A
根据关键字序列得到的 小根堆 的二叉树形式如下图所示。
5 8 12 19 28 20 15 22 5 8 12 19 28 20 15 22 3 3 5 12 8 28 20 15 22 19 (1) (2) (3) 插入关键字 3 时，先将其放在小顶堆的末端，如图 (2) 所示。
再将该关键字向上进行调整，得到的结果如图 (3) 所示。
所以，调整后的小顶堆序列为 3, 5, 12, 8, 28, 20, 15, 22, 19。
在外部排序的k路归并过程中，归并趟数为d。下列关于k、d、初始归并段及内存大小的说法中，正确的是（ ）Ⅰ.k越大，d越小Ⅱ. 初始归并段数不影响dⅢ. 内存大小限制初始归并段的最大长度
A. Ⅰ B. Ⅰ、Ⅱ C. Ⅰ、Ⅲ D. Ⅱ、Ⅲ
[tag_link]
正确答案：C
**【解析】**在外部排序的 k 路归并过程中，归并趟数d与初始归并段数m满足关系d=⌈logkm⌉。
- 对于说法Ⅰ：k越大，logkm越小，因此d越小，正确。
- 对于说法Ⅱ：d直接依赖于m，初始归并段数变化会影响d，错误。
- 对于说法Ⅲ：生成初始归并段时，数据需读入内存进行内部排序，因此初始归并段的最大长度受内存大小限制，正确。综上，Ⅰ和Ⅲ正确，对应选项 C。
任何一个无向连通图的最小生成树（ ）。
A. 有一棵或多棵 B. 只有一棵 C. 一定有多棵 D. 可能不存在
[tag_link]
正确答案：A
结论
选 A。无向连通图至少存在一棵最小生成树，但权值相同时可能存在多棵。
推导
连通图可通过不断选取不成环的边得到生成树，有限棵生成树中总权值最小者即为 MST；若不同边组合具有相同最小代价，MST 不唯一。
易错点
连通性保证存在性，不保证唯一性；D 把“可能不唯一”误解成“可能不存在”。
用 Prim 算法和 Kruskal 算法构造图的最小生成树，所得到的最小生成树（ ）。
A. 相同 B. 不相同 C. 可能相同，可能不同 D. 无法比较
[tag_link]
正确答案：C
结论
选 C。
推导
两种算法都遵循 MST 的贪心性质。若 MST 唯一，二者必得到同一棵树；若存在等权边导致多个 MST，选边顺序可能不同，结果也可能不同。
易错点
“都是最小生成树”不等于“边集合必相同”；应区分最小代价相同与树形唯一。
下列关于图的生成树和最小生成树的叙述中，正确的是（ ）。
A. 只要无向连通图中没有权值相同的边，则其最小生成树唯一 B. 只要无向图中有权值相同的边，则其最小生成树一定不唯一 C. 从 n 个顶点的连通图中选取 n-1 条权值最小的边，即可构成最小生成树 D. 设连通图 G 含有 n 个顶点，则含有 n 个顶点、n-1 条边的子图一定是 G 的生成树
[tag_link]
正确答案：A
结论
选 A。
推导
无向连通图所有边权互异时，Kruskal 或 Prim 每一步的最小合法边唯一，故 MST 唯一。B 中等权边不一定参与竞争；C 只按权值选边可能成环；D 还需满足连通性。
易错点
“n 个顶点、n−1 条边”只是树的必要数量条件，不足以保证无环且连通。
（10 分）下面有一种称为“破圈法”的求解最小生成树的方法：所谓“破圈法”就是“任取一圈，去掉圈上权最大的边”，反复执行这一步骤，直到没有圈为止。 试判断这种方法是否正确。如果正确，请说明理由；如果不正确，举出反例（注：圈就是回路）。
[tag_link]
**【答案】** 正确
**【解析】** 连通图的生成树包括图中的全部 n 个顶点和足以使图连通的 n-1 条边，最小生成树是边上权值之和最小的生成树。故可按权值从大到小对边进行排序，然后从大到小将边删除。每删除一条当前权值最大的边后，就去测试图是否仍连通，若不再连通，则将该边恢复。若仍连通，继续向下删；直到剩 n-1 条边为止。
破圈法的正确性基于最小生成树的一个关键性质：在连通无向图的任意一个圈中，权值最大的边一定不属于任何最小生成树（如果边权互异，则该边绝对不在最小生成树中；如果边权有重复，则存在至少一个最小生成树不包含该边）。执行破圈法时，每次任选一个圈并去掉其中权最大的边，相当于移除了一条不在最小生成树中的边，且由于圈是连通的，去掉一条边不会破坏图的连通性。反复执行这一操作，直到图中没有圈为止，此时得到的图是连通且无环的，即为一棵生成树。由于去除的边都不在最小生成树中，而剩下的边数恰好为顶点数减一，因此这棵生成树就是最小生成树。综上，破圈法是求解最小生成树的一种正确方法。
请回答下列问题：
(1) 试证明若图中各条边的权值各不相同，则它的最小生成树唯一。 (2) Prim 算法和 Kruskal 算法生成的最小生成树一定相同吗？ (3) 画出下列带权图 G 的所有最小生成树。
[tag_link]
**【解析】** (1) 采用反证法证明：假设图中有两个不同的最小生成树 和 。设 是 中但不在 中的权值最小的边。将 添加到 中，会形成一个环，该环中至少存在一条边 不在 中。由于图中各边权值各不相同，比较 和 的权值。若 ，则在 中用 替换 会得到一棵权值更小的生成树，与 是最小生成树矛盾；若 ，则在 中用 替换 会得到一棵权值更小的生成树，与 是最小生成树矛盾。因此假设不成立，最小生成树唯一。
(2) Prim 算法和 Kruskal 算法都是贪心算法，用于求解最小生成树。当图中边权值各不相同时，最小生成树唯一，因此两种算法必然得到相同的最小生成树。但当图中存在权值相同的边时，最小生成树可能不唯一，两种算法在选择边时可能做出不同选择，从而生成不同的最小生成树。因此，它们生成的最小生成树不一定相同。
(3) 根据 Kruskal 算法，先把 的边（权值 ）加入集合，而接下来选择下一条边时，因为有两条权值为 的边可以选择，那么因为不同的选择就会生成出不同的最小生成树。若选择 ，然后同样出现 与 的选择，而不管先选择哪条边，另一条边也会成为下一个选择的对象，所以这里不影响树的结构，最后答案为左边这棵树；而当之前第二次选择边的时候，选择 则会是右边的最小生成树。
（10 分）下图所示是一带权有向图的邻接表。其中出边表中的每个结点均含有三个字段，依次为边的另一个顶点在顶点表中的序号、边上的权值和指向下一个边结点的指针。试求：
（1）该带权有向图的图形。 （2）从顶点 V1 为起点的广度优先搜索的顶点序列及对应的生成树。 （3）以顶点 V1 为起点的深度优先搜索生成树。 （4）由顶点 V1 到顶点 V3 的最短路径。 （5）若将该图看成无向图，用 Prim 算法给出图 G 的一棵最小生成树的生成过程。
[tag_link]
**【解析】** (1) 该邻接表存储对应的带权有向图如下：
(2) 以顶点 为起点的广度优先搜索的顶点序列依次为 ，对应的生成树如下：
(3) 生成树：顶点集合 ，边的集合 。（图略）
(4) V1 到 V3 最短路径为 67: (V1—V4—V3)。
(5) 从 V1 点开始，第一趟寻找 V1 和点集 之间的最小权值的边。(V5,V1)。
第二趟寻找点集 和点集 之间的最小权值的边。(V5,V6)。
第三趟寻找点集 和点集 之间的最小权值的边。(V1,V4)。
第四趟寻找点集 和点集 之间的最小权值的边。(V4,V2)。
第五趟寻找点集 和点集 之间的最小权值的边。(V2,V3)。
所以最小生成树的边集合为 （图形略）。
设有 n 个顶点的无向连通图的最小生成树不唯一，则下列说法中正确的是（ ）。
A. 图的边数一定大于 n-1 B. 图的权值最小的边一定有多条 C. 图的最小生成树的代价不一定相等 D. 图的各条边的权值不相等
[tag_link]
正确答案：A
结论
选 A。MST 不唯一时，原图不可能本身就是唯一的 n−1 条边树，因此边数必大于 n−1。
推导
所有 MST 的代价都等于全局最小代价，故 C 错；导致不唯一的等权边不必是全图最小权边，B 错；D 与不唯一相矛盾，边权全异反而保证唯一。
易错点
树形不唯一与最小代价不唯一是两回事：MST 可以有多棵，但代价必相同。
使用 Prim（普里姆）算法求带权连通图的最小（代价）生成树（MST）。请回答下列问题。
(1) 对下列图 G，从顶点 A 开始求 G 的 MST，依次给出按算法选出的边。
(2) 图 G 的 MST 是唯一的吗？
(3) 对任意的带权连通图，满足什么条件时，其 MST 是唯一的？
[tag_link]
1）Prim 算法 属于贪心策略。算法从一个任意的顶点开始，一直长大到覆盖图中所有顶点为止。算法每一步在连接树集合 S 中顶点和其他顶点的边中，选择一条使得树的总权重增加最小的边加入集合 S。当算法终止时，S 就是最小生成树。① S 中顶点为 A，候选边为 (A,D),(A,B),(A,E)，选择 (A,D) 加入 S。② S 中顶点为 A,D，候选边为 (A,B),(A,E),(D,E),(C,D)，选择 (D,E) 加入 S。③ S 中顶点为 A,D,E，候选边为 (A,B),(C,D),(C,E)，选择 (C,E) 加入 S。④ S 中顶点为 A,D,E,C，候选边为 (A,B),(B,C)，选择 (B,C) 加入 S。⑤ S 就是最小生成树。依次选出的边为 (A,D),(D,E),(C,E),(B,C)（4 分）【评分说明】每正确选对一条边且次序正确，给 1 分。若考生选择的边正确，但次序不完全正确，酌情给分。
2）图 G 的 MST 是唯一的。（2 分）第一小题的最小生成树包括了图中权值最小的四条边，其他边都比这四条边大，所以此图的 MST 唯一。
3）当带权连通图的任意一个环中所包含的边的权值均不相同时，其 MST 是唯一的。（2 分）此题不要求回答充分必要条件，所以回答一个限制边权值的充分条件即可。【评分说明】①若考生答案中给出的是其他充分条件，例如“带权连通图的所有边的权值均不相同”，同样给分。②若考生给出的充分条件对图的顶点数和边数做了某些限制，例如，限制了图中顶点的个数（顶点个数少于 3 个）、限制了图的形状（图中没有环）等，则最高给 1 分。③答案部分正确，酌情给分。
拟建设一个光通信骨干网络连通 BJ、CS、XA、QD、JN、NJ、TL 和 WH 等 8 个城市，题 42 图中无向边上的权值表示两个城市间备选光缆的铺设费用。
请回答下列问题。
(1) 仅从铺设费用角度出发，给出所有可能的最经济的光缆铺设方案（用带权图表示），并计算相应方案的总费用。
(2) 题 42 图可采用图的哪一种存储结构？给出求解问题
(1) 所使用的算法名称。
(3) 假设每个城市采用一个路由器按
(1) 中得到的最经济方案组网，主机 H1 直接连接在 TL 的路由器上，主机 H2 直接连接在 BJ 的路由器上。若 H1 向 H2 发送一个 TTL=5 的 IP 分组，则 H2 是否可以收到该 IP 分组？
[tag_link]
1）为了求解最经济的方案，可以把问题抽象为求无向带权图的最小生成树。可以采用手动 Prim 算法或 Kruskal 算法作图。注意本题最小生成树有两种构造，如下图所示。
方案的总费用为 16。
2）存储题中的图可以采用邻接矩阵（或邻接表）。构造最小生成树采用 Prim 算法（或 Kruskal算法）。
3）TTL= 5，即 IP 分组的生存时间（最大传递距离）为 5，方案 1 中 TL 和 BJ 的距离过远，TTL = 5 不足以让 IP 分组从 H1 传送到 H2，因此 H2 不能收到 IP 分组。而方案 2 中 TL 和 BJ 邻近，H2 可以收到 IP 分组。
用 Prim 算法求一个带权连通图的最小生成树，在算法执行的某个时刻，已选取的顶点集合 U={1,2,3}，已选取的边集合 TE={(1,2),(2,3)}，要选取下一条权值最小的边，应当从（ ）组中选取。
A. {(1,4),(3,4),(3,5),(2,5)} B. {(3,4),(3,5),(4,5),(1,4)} C. {(1,2),(2,3),(3,5)} D. {(4,5),(1,3),(3,5)}
[tag_link]
正确答案：A
结论
选 A。
推导
Prim 的候选边必须横跨割 (U, V−U)，即一端在 {1,2,3}、另一端在未加入顶点集合。只有 A 中的边全部满足该条件；然后从 A 的候选边中选权值最小者。
易错点
已选边 TE 不能再次作为候选；连接 U 内两个顶点的边会形成内部边，不属于 Prim 当前割边集合。
用 Kruskal 算法求一个带权连通图的最小生成树。在算法执行的某时刻，已选取的边集合为 TE={(1,2),(2,3),(3,5)}。要选取下一条权值最小的边，不可能选取的边是（ ）。
A. (3,6)
B. (2,4)
C. (1,3)
D. (1,4)
[tag_link]
正确答案：C
结论
选 C。
推导
Kruskal 按边权递增尝试加入边，但若候选边的两个端点已经在同一连通分量中，就会形成回路，必须跳过。TE 已使 1、2、3、5 连成一棵树，因此 (1,3) 会闭合回路，不可能被选入；其余边仍可能连接不同分量。
易错点
“权值最小”不等于“必选”：Kruskal 还要检查加入该边是否成环。
下面的()方法可以判断出一个有向图是否有环(回路)。 I. 深度优先遍历 Ⅱ .拓扑排序Ⅲ .求最短路径 IV. 广度优先遍历
A. I 、Ⅱ 、IV B.I 、Ⅲ 、IV C.I 、Ⅱ 、Ⅲ D. 全部可以
[tag_link]
正确答案：A
右图所示有向图的所有拓扑序列共有()个。
A. 4 B.6 C. 5 D.7
[tag_link]
正确答案：C
下列关于图的说法中，正确的是()。 I. 有向图中顶点V的度等于其邻接矩阵中第V行中1的个数 IⅡ . 无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵 Ⅲ .在带权图G 的最小生成树G₁中，某条边的权值可能会超过未选边的权值 IV. 若有向无环图的拓扑序列唯一，则可以唯一确定该图
A. I 、Ⅱ 和 Ⅲ B. Ⅲ 和 IV C. II D. IV
[tag_link]
正确答案：C
下图所示的AOE 网中，关键路径长度为()。 a₂=4√a₁=6 a₃= a₂=4 √ 心 四 心 四 a₇=9a₄=1 a₇=9 ag=7₂ a₅=1 ag=7 a1₀=2 V8) au=4 W
A. 16 B. 17 C.1 8 D. 19
[tag_link]
正确答案：C
若某带权图为G=(V,E), a=4 a₆=4 其 中V={ v1,V₂,V3,V4,Vs,V6,V₇,V₈,V₉,V10},E={<v1,V ₂>5,<v1, v₃>6,<v₂,V₅>3,<v3,V₅>6,<v3,v₄>3,<v4,V₅>3,<v4,V₇>1,<v4,Vg>4,<vs,V₆>4,<vs,v₇>2,<v₆, V1o>4,<v₇,v₉>5,<v₈,V₉>2,<v₉,V1o>2}( 注：边括号外的数据表示边上的权值),则G的 关键路径的长度为()。
A. 19 B. 20 C. 21 D.22
[tag_link]
正确答案：
下面是一种称为“破圈法”的求解最小生成树的方法：所谓“破圈法”,是指“任取 一圈，去掉圈上权最大的边”,反复执行这一步骤，直到没有圈为止。试判断这种方 法是否正确。若正确，说明理由；若不正确，举出反例(注：圈就是回路)。
[tag_link]
参考答案
这种方法正确。
先看“最终得到树”：从连通图的一个回路中删除一条边，不会破坏连通性，因为该边的两个端点仍可沿回路中的其余边互相到达。反复删除到没有回路时，图仍连通且无环，所以得到一棵生成树。
再证明“权值最小”。设当前回路中被删除的最大权边为 e。取当前图的一棵最小生成树 T：
- 若
e不在T中，删除e不影响T； - 若
e在T中，删去e会把T分成两个连通分量。原回路上必有另一条跨越这两个分量的边f，且w(f) ≤ w(e)。用f替换e后仍为生成树，且总权值不增，因此仍能得到一棵最小生成树。
所以每次“破圈”后，剩余图中始终至少保留一棵最小生成树；最终只剩一棵生成树时，它必为最小生成树。
易错点
环上最大权边并不一定唯一。若有多条并列最大边，任删其中一条即可；不能说所有最大边都绝不属于任何最小生成树。
已知有向图如右图所示。 1)写出该图的邻接矩阵表示并据此给出从顶点1出发的 深度优先遍历序列。 2)求该有向图的强连通分量的数目。 3)给出该图的任意两个拓扑序列。 4)若将该图视为无向图，分别用Prim 算法和 Kruskal 算 法求最小生成树。
[tag_link]
C
对右图所示的无向图，按照 Dijkstra 算法，写出从顶点1到其 他各个顶点的最短路径和最短路径长度(顺序不能颠倒)。
[tag_link]
A
下图所示为一个用 AOE 网表示的工程。
- 画出此图的邻接表表示。 2)完成此工程至少需要多少时间? 3)指出关键路径。 4)哪些活动加速可以缩短完成工程所需的时间? a₅=2a₁=2 a₅=2 —a₂=5— a₃=5
[tag_link]
A
一连通无向图，边非负权值，问用 Dijkstra 最短路径算法能否给出一棵生成树，该树是 否一定是最小生成树?说明理由。
[tag_link]
参考答案
Dijkstra 算法能给出一棵以源点为根的最短路径树，但这棵树不一定是最小生成树。
原因是两种贪心目标不同：Dijkstra 每次固定“从源点到某顶点的当前最短距离”，而 Prim 每次选择“已入树顶点集合到树外的最轻边”。前者优化每个顶点到源点的路径，后者优化整棵树的边权总和。
反例：无向图有边 a-b=5、a-c=5、a-d=5、b-d=1、c-d=1。从 a 出发执行 Dijkstra，在三个距离同为 5 的顶点中先固定 d 时，a-b 和 a-c 仍分别比绕经 d 的距离 6 更短，因此可得到边集 {a-b,a-c,a-d}，总权值为 15。最小生成树则可取 {a-d,b-d,c-d}，总权值为 7。
所以“能生成树”正确，“一定是最小生成树”错误。
1.1.1
[tag_link]
D
1.1.2
[tag_link]
D
1.1.5
[tag_link]
D
1.1.6 标识路由器的IP地址 Link1 ID
[tag_link]
D
1.1.2
[tag_link]
D
1.1.1
[tag_link]
D
1.1.6
[tag_link]
D
1.1.5 所连路由器的Router ID IP
[tag_link]
D
1.1.1
[tag_link]
D
1.1.2
[tag_link]
D
1.1.5
[tag_link]
D
1.1.6 Link1的本地IP地址 Metric 3 3 6 6 Link1的费用 Link2 ID
[tag_link]
D
1.1.5
[tag_link]
D
1.1.6
[tag_link]
D
1.1.1
[tag_link]
D
1.1.2 所连路由器的Router ID IP
[tag_link]
D
1.1.9
[tag_link]
D
1.1.13
[tag_link]
D
1.1.10
[tag_link]
D
1.1.14 Link2的本地IP地址 Metric 2 4 2 4 Link2的费用 Net1 Prefix 192.1.1.0/24 192.1.6.0/24 192.1.5.0/24 192.1.7.0/24 直连网络Net1的网络前缀 Metric 1 1 1 1 到达直连网络Net1的费用 E0 192.1.1.0/24 1 L0
[tag_link]
D
1.1.1 RI L1
[tag_link]
D
1.1.9 2
[tag_link]
D
1.1.2 1 192.1.6.0/24 3 R2
[tag_link]
D
1.1.13 4 192.1.5.0/24 1
[tag_link]
D
1.1.10 6 R3 10.1.1.5 10.1.1.6
[tag_link]
D
1.1.14 R4 1 192.1.7.0/24 请回答下列问题。 1)本题中的网络可抽象为数据结构中的哪种逻辑结构? 2)针对表中的内容，设计合理的链式存储结构，以保存表中的链路状态信息 ( LSI) 。 要求给出链式存储结构的数据类型定义，并画出对应表的链式存储结构示 意图(示意图中可仅以ID 标识结点)。 3)按照Dijkstra 算法的策略，依次给出 R1 到达子网192.1.x.x 的最短路径及费用。
[tag_link]
D