6.4.1.2 Kruskal 算法
原书定位
印刷页P233起,对应PDF第245页。下文为目视整理的知识提要;完整内容见原书对照。
所有边按权非降序处理,若一条边的两个端点属于不同连通分量就选入并合并,否则跳过。用并查集判定是否成环;连通图选满 条边即可停止。
排序占 ,并查集配合按规模合并和路径压缩的总操作代价接近线性,适合稀疏图。选择的边最初可形成多棵树,最后合为一棵;不能要求每一步都与起点相连。

Kruskal 构造过程,原书P233。
对应练习
关联知识
原书对照
展开原书对照截图


原书定位
印刷页P233起,对应PDF第245页。下文为目视整理的知识提要;完整内容见原书对照。
所有边按权非降序处理,若一条边的两个端点属于不同连通分量就选入并合并,否则跳过。用并查集判定是否成环;连通图选满 条边即可停止。
排序占 ,并查集配合按规模合并和路径压缩的总操作代价接近线性,适合稀疏图。选择的边最初可形成多棵树,最后合为一棵;不能要求每一步都与起点相连。

Kruskal 构造过程,原书P233。

