您的位置: 首页 > 文章 > 采用Kruskal算法构造最小生成树 采用Kruskal算法构造最小生成树 分类: 文章 • 2025-06-18 08:24:58 1、问题 画出采用Kruskal算法构造最小生成树的过程，并按实验报告模板编写算法。 2、解析 对于所有的边，每次取一条最短的边（不能重复取），判断它的两个端点是否已经在一个连通块中了（并查集维护），如果是，那么取下一条边；如果没在一个连通块中，则把两个连通块（不一定是两个点）连在一起，答案加上当前边的长度。直到所有的点都在一个连通块中结束。 3、设计 4、分析 时间复杂度：O（nlogn) (n为边数）
