内容简介:不用判断加入的点是否会形成连通图
- 先随意选一个点作为起点
- 将各个与起点之间连通的点之中权值最小的那个与点加入到最小生成树中
- 继续遍历与最小生成树中的点权值最小的点(未加入最小生成树的点),将它加入最小生成树中
- 重复第三个步骤直到所有的点加入到最小生成树中
与kruskal相比的优点
不用判断加入的点是否会形成连通图
算法步骤
- 将各个点之间的距离以无向图的形式存在邻接矩阵中。
- 用一个一维数组存储起始点到各个点的距离。
- 用一个标记数组存储各个点加入最小生成树的状态。
- 用一个数组记录当前节点是哪个节点连过来的。
- 所谓贪心,就是每次都找到权值最小的那条边(u,v)的v加入到最小生成树中,加进去之后对标记数组进行修改,表示该点已经加入到最小生成树中。对v中的距离数组进行更新,这里的更新不是把原数组中的所有数据都替换到新加入的点到所有的点的距离,而是与原先的点到同一个点(未加入)进行比较。倘若比原来的小则更新数组数据,同时对4中的来源数组进行更新,用来记录最小生成树,大于等于就跳过。循环n次(节点个数)后得到结果。
代码
#include<stdio.h> #define N 6 #define MAX 100000 int a[N][N],result[N][N]; int main() { int flag[100] = { 0 }; int neighbor[100],distance[100]; int u, v, l; //对数据进行初始化 for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) a[i][j] = MAX; } scanf("%d%d%d", &u, &v, &l); while (l != -1) { a[u][v] = l; a[v][u] = l; scanf("%d%d%d", &u, &v, &l); } for (int i = 0; i < N; i++) { neighbor[i] = 0; distance[i] = a[0][i]; } flag[0] = 1;//以第0个点为起点 for (int i = 1; i < N; i++) { int min = MAX; for (int j = 0; j < N; j++) { if (!flag[j] && min>distance[j]) { min = distance[j]; v = j; } }//找到距离最短那条边,并把v加进最小生成树 if (min < MAX) { flag[v] = 1; result[neighbor[v]][v] = distance[v]; result[v][neighbor[v]] = distance[v]; for (int j = 0; j < N; j++) { //更新distance数组,将距离小的加进去 if (!flag[j] && a[v][j] < distance[j]) { distance[j] = a[v][j]; neighbor[j] = v;//更新来源 } } } else break; } //将结果输出 for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) printf("%d ",result[i][j]); putchar(10);//换行 } return 0; } 复制代码
测试数据
0 1 5 0 2 6 0 3 4 1 2 1 1 3 2 2 3 2 2 4 5 2 5 3 3 5 4 4 5 4 -1 -1 -1 复制代码
以上所述就是小编给大家介绍的《prim算法的初步了解》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:- java – 了解罗盘的布局算法
- 面试官:负载均衡的算法你了解不?
- 一文带你全面了解限流算法
- 一文了解分布式一致性算法 EPaxos
- https优化必须了解ChaCha20-Poly1305算法
- 助力AI算法芯片化,这款“神器”你有必要了解下!
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。