Kruskal 最小生成树

按权升序遍历所有边,通过并查集规避环路,构建总权最小连通树

已选边: 0 总权值: 0 状态: 就绪

算法说明

时间复杂度:O(E log E),E为边数

空间复杂度:O(V)

核心思想:将所有边按权值升序排序,依次尝试加入生成树。使用并查集(路径压缩+按秩合并)判断加入该边是否形成环路:若两端点已连通则跳过,否则加入。最终得到总权值最小的连通子图。

核心代码