长沙品质企业建站服务电话,建筑建设网站建设,怎么建立公司网站,一个人看的浏览器适用情景在最小生成树问题当中#xff0c;涉及到权重和最小值。并且这个图是稠密图(n^2 ~ m)的情形下时间复杂度O(N^2)算法解释先得知道一下什么是无向图的生成树#xff0c;树总该知道的吧#xff0c;生成树就是包含这个无向图中的n个点#xff0c;并且有n-1条边#xff…适用情景在最小生成树问题当中涉及到权重和最小值。并且这个图是稠密图(n^2 ~ m)的情形下时间复杂度O(N^2)算法解释先得知道一下什么是无向图的生成树树总该知道的吧生成树就是包含这个无向图中的n个点并且有n-1条边其实说白了就是一棵树当于从原先的无向图的结构当中“拿取”一部分组成了一棵树这棵树就叫做无向图的生成树。然后这棵树既然有n-1条边图当中边是有权重的这些边的权重之和最小的那棵树就称为无向图的最小生成树首先对于这个图来说首先是无向图说白了也是一种特殊的有向图然后prim算法适用于稠密图那既然是稠密图的话想当然就是用邻接矩阵去存储边。然后对于这个图而言正权边与负权边无关紧要最后对于重边和自环重边的话肯定是取小的然后环的话是不可能出现在最小生成树当中需要回避的int dist[N][N];然后对于这个邻接矩阵初始化操作变成无穷大等会儿要进行取小操作然后就是把边输入到这个邻接矩阵当中无向图的话实际上就是一种特殊的有向图罢了memset(g,0x3f3f3f3f,sizeof(g));
int a,b,c;
while(m--)
{scanf(%d %d %d,a,b,c);g[a][b]g[b][a]MIN(g[a][b],c);
}然后这是一个很关键的一步创建一个dist数组这个dist数组表示每个点到联通块集合的最短距离这个联通块集合不断壮大壮大最后就是我的一个最小生成树在一开始的话也全部都默认初始化为无穷大int dist[N];
memset(dist,0x3f,sizeof(dist));除此之外还需要一个数组st起标记作用就是去说明该点是否已经在联通块集合这个联通块集合不断壮大壮大最后就是我需要求的最小生成树当中。int st[N];然后接下来正式就是prim算法这个prim算法的话与迪杰斯特拉算法非常相似。首先是先去循环n次然后第一次循环的话由于是刚刚开始就选择一号点作为联通快集合的开拓点真正在联通块集合当中每一个点没有先来后到之分然后对于外循环的第一次他就是仅仅去更新一下别人的dist并且去标记一下自己已经进入联通块集合当中而已。然后对于接下来的每一次外循环与Dijkstra算法相似首先先去找集合外的距离联通块集合距离最近的点把这个点找到之后。先要去判断一下这个点距离集合的最短距离如果发现是初始化的那个无穷大值好那么这时候就说明生成不了最小生成树如果不是用这个点所能及更新它所能连接到的其他点的到联通块集合的最短距离并且呢把他自己呢要加入到联通块集合当中也就是说需要标记一下。by the way然后在这个过程当中我就可以去求我这个最后生成的最小生成树它的各边权重和。int res0; //最后生成的最小生成树它的各边权重和
for (int i0;in;i)
{int t0;for (int j1;jn;j){if (st[j]0 (t0 || dist[j]dist[t])){tj;}}if (i!0){if (dist[t]0x3f3f3f3f){printf(impossible\n);return 0;}else{resdist[t];}}st[t]1;for (int j1;jn;j){dist[j]MIN(dist[j],g[t][j]); }}
printf(%d\n,res);例题来源AcWing858. Prim算法求最小生成树 - AcWing题库#include stdio.h
#include string.h
#define MIN(a,b) ((a)(b)?(a):(b))
#define N 510
int g[N][N];
int dist[N];
int st[N];
int main()
{memset(dist,0x3f,sizeof(dist));int n,m;scanf(%d %d,n,m);memset(g,0x3f3f3f3f,sizeof(g));int a,b,c;while(m--){scanf(%d %d %d,a,b,c);g[a][b]g[b][a]MIN(g[a][b],c);}int res0;for (int i0;in;i){int t0;for (int j1;jn;j){if (st[j]0 (t0 || dist[j]dist[t])){tj;}}if (i!0){if (dist[t]0x3f3f3f3f){printf(impossible\n);return 0;}else{resdist[t];}}st[t]1;for (int j1;jn;j){dist[j]MIN(dist[j],g[t][j]); }}printf(%d\n,res);return 0;
}
