题40

题40

题目

Q:【2020 统考真题】已知无向图 如下所示,使用 Kruskal 算法求图 的最小生成树，加到最小生成树中的边依次是 ( ).

A.
B.
C.
D.

分析

A:kruskal算法求最小生成树-aw每次选择权重最小的集合，合并集合
如果要连接的两个点，已经在同一个集合中，那么就不连接，就需要跳过

解

Kruskal 算法: 按权值递增顺序依次选取 条边,并保证这 条边不构成回路。初始构造一个仅含 个顶点的森林;
第一步,选取权值最小的边 加入最小生成树;
第二步,剩余边中权值最小的边为 ,加入最小生成树,第二步操作后权值最小的边 不能选,因为会与之前已选取的边形成回路;
接下来依次选取权值 对应的边加入最小生成树,此时 6 个顶点形成了一棵树,最小生成树构造完成。
按照上述过程,加到最小生成树的边依次为 , 。其生成过程如下所示。