6.4.1.2 Kruskal 算法

教材导航 · 第6章

原书定位

印刷页P233起,对应PDF第245页。下文为目视整理的知识提要;完整内容见原书对照。

所有边按权非降序处理,若一条边的两个端点属于不同连通分量就选入并合并,否则跳过。用并查集判定是否成环;连通图选满 n−1n-1 条边即可停止。

排序占 O(mlog⁡m)O(m\log m),并查集配合按规模合并和路径压缩的总操作代价接近线性,适合稀疏图。选择的边最初可形成多棵树,最后合为一棵;不能要求每一步都与起点相连。

Kruskal 构造过程

Kruskal 构造过程,原书P233。

对应练习

6.4 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P233,PDF第245页

原书对照,原书P234,PDF第246页