Kruskal 最小生成树
按权升序遍历所有边,通过并查集规避环路,构建总权最小连通树
已选边: 0 总权值: 0 状态: 就绪
算法说明
时间复杂度:O(E log E),E为边数
空间复杂度:O(V)
核心思想:将所有边按权值升序排序,依次尝试加入生成树。使用并查集(路径压缩+按秩合并)判断加入该边是否形成环路:若两端点已连通则跳过,否则加入。最终得到总权值最小的连通子图。
按权升序遍历所有边,通过并查集规避环路,构建总权最小连通树
时间复杂度:O(E log E),E为边数
空间复杂度:O(V)
核心思想:将所有边按权值升序排序,依次尝试加入生成树。使用并查集(路径压缩+按秩合并)判断加入该边是否形成环路:若两端点已连通则跳过,否则加入。最终得到总权值最小的连通子图。