反圈法(最小生成树)最小生成树的算法
来源:学生作业帮 编辑:搜搜做题作业网作业帮 分类:数学作业 时间:2024/06/23 20:17:48
反圈法(最小生成树)
最小生成树的算法
最小生成树的算法
主要有两个:
1.普里姆(Prim)算法
特点:时间复杂度为O(n2).适合于求边稠密的最小生成树.
2.克鲁斯卡尔(Kruskal)算法
特点:时间复杂度为O(eloge)(e为网中边数),适合于求稀疏的网的最小生成树.
1.普里姆(Prim)算法
特点:时间复杂度为O(n2).适合于求边稠密的最小生成树.
2.克鲁斯卡尔(Kruskal)算法
特点:时间复杂度为O(eloge)(e为网中边数),适合于求稀疏的网的最小生成树.