构建最小生成树普利姆算法和克鲁斯卡尔算法(P&C)
2021/12/30 11:07:39
本文主要是介绍构建最小生成树普利姆算法和克鲁斯卡尔算法(P&C),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
普利姆算法和克鲁斯卡尔算法的思想可以归为贪心算法即:以每次局部最优解最后得全局最优解。
相同点:
- 都适用于无向图。
- 都是用了贪心思想
不同点:
- 普利姆算法是顶点优先,克鲁斯卡尔是边优先。二者应对不同情况效率不同。
- 普利姆算法平均时间复杂度为O(n^2),是顶点数的平方。
- 克鲁斯卡尔算法平均时间复杂度取决于选用的排序算法,是和边数相关的。
普利姆算法分析如下:
for (int k = 0; k < g.n; k++) {
// 用邻接矩阵存储无向图, 维护一个 lowcost[],一个vset[] vset数组用于记录已经选择的顶点 for (int i = 0; i < g.n; i++){ //找到lowcost中 没有被选择过的最小值 if (vset[i] == 0 && lowcast[i] < min){ min = lowcast[i]; min_index = i; } } // 将 min_index 点并入 vset[min_index] = 1; //维护lowcost数组 for (int j = 0; j < g.n; j++){ // min_index 点位新加入的点, 只要该点到其他点的距离小于 lowcost[j] 就覆盖,由此lowcost[]一直都是子树到各点的最小距离 if (vset[j] == 0 && g.edges[min_index][j] < lowcost[j] ){ lowcost[j] =g.edges[min_index][j]; }
}
}
克鲁斯卡尔算法运用并查集工具判断是否形成回路。 并查集本质是在一个数组存了一棵二叉树,通过查找不同子节点的根节点判断是否会形成回路。
//并查集工具 public int getRoot(int a){ // v[] 存放二叉树 while(a != v[a]){ a = v[a]; } return a; } //定义边的类 包含边的左节点有节点和边的长度 class Edge{ int leftNode; int rightNode; int length } //初始化并查集工具用到的数组 for (int i = 0; i < g.n; i++){ v[i] = i; }
// 将边按照从小到大顺序排列 sort(Edge[] edges, g.E);
for (int i = 0; i < g.e; i++){ // 获取左右两个节点的根节点 leftNode = getRoot(edges[i].leftNode); rightNode = getRoot(edges[i].rightNode); if (leftNode != rightNode){ // 说明是两棵独立的子树 可以合并 v[leftNode] = rightNode; }
}
这篇关于构建最小生成树普利姆算法和克鲁斯卡尔算法(P&C)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28pyqt 怎么打包整个项目-icode9专业技术文章分享
- 2024-09-28laravel Commands 创建带有参数的 Artisan 命令的步骤和示例-icode9专业技术文章分享
- 2024-09-28antd怎么实现渲染tiff图片-icode9专业技术文章分享
- 2024-09-28英文半角中划线和中文全角的中划线有什么区别-icode9专业技术文章分享
- 2024-09-28nvm npm 和node 他们之间有什么关系-icode9专业技术文章分享
- 2024-09-28Node Version Manager (nvm)使用教程-icode9专业技术文章分享
- 2024-09-28nvm命令太慢,是什么原因-icode9专业技术文章分享
- 2024-09-28Kotlin 如何增加、删除和修改 MutableStateFlow 中的值。-icode9专业技术文章分享
- 2024-09-28Kotlin的stateFlow.update 写法介绍-icode9专业技术文章分享
- 2024-09-28kotlin 怎么获取当前时间格式-icode9专业技术文章分享