首页 > 代码库 > 月球美容计划之最小生成树(MST)
月球美容计划之最小生成树(MST)
寒假学的两个算法,普里姆,克鲁斯卡尔终于弄明白了,可以发总结了
先说说普里姆,它的本质就是贪心,先从任意一个点开始,找到最短边,然后不断更新更新len数组,然后再选取最短边并标记经过的点,直到所有的点被标记,或者说已经选好了n-1条边。
拿SDUTOJ2144为例,代码如下,可做模板
#include <stdio.h> #include <string.h> #define INF 1000000 //最小生成树 //普里姆 int G[200][200]; int len[200]; bool vis[200]; int prm (int n) { int i,k,ans = 0; memset (vis,0,sizeof(vis)); for (i = 2;i <= n;i++)//初始化 len[i] = G[1][i]; vis[1] = 1; for (i = 1;i < n;i++) //循环n - 1次 { //因为n个顶点的MST一定是n-1条边 int imin = INF,xb; for (k = 1;k <= n;k++) if (!vis[k] && imin > len[k]) { imin = len[k]; xb = k; } if (imin == INF) //没有找到最小值,说明图不连通 return -1; vis[xb] = 1; ans += imin; for (k = 1;k <= n;k++) if (!vis[k] && len[k] > G[xb][k]) len[k] = G[xb][k]; } return ans; } int main() { int n,m; while (~scanf ("%d%d",&n,&m)) { int i,k; for (i = 1;i <= n;i++) for (k = 1;k <= n;k++) if (i != k) G[i][k] = INF; else G[i][k] = 0; for (i = 0;i < m;i++) { int a,b,c; scanf ("%d%d%d",&a,&b,&c); if (G[a][b] > c) //如果有边多次录入,选权最小的那个 G[a][b] = G[b][a] = c; } int ans = prm(n); printf ("%d\n",ans); } return 0; }
克鲁斯卡尔,一个排序一个并查集只是表面,实质还是贪心,只不过普里斯是任选一个点选最短路,而克鲁斯卡尔是看全局,全体边排序,当然,因为排序,导致时间复杂度不容易降下来。
同样的题,代码如下:
#include <stdio.h> #include <stdlib.h> #include <string.h> #define INF 1000000 //最小生成树 //克鲁斯卡尔 int vis[200]; struct eg { int v,u,w; }e[100000]; int cont; int cmp (const void *a,const void *b) { struct eg *ta = (struct eg *)a; struct eg *tb = (struct eg *)b; return ta->w - tb->w; } int fin (int a) { int r = a; while (vis[r] != r) r = vis[r]; int k; while (vis[a] != a) { k = vis[a]; vis[a] = r; a = vis[k]; } return r; } int add (int a,int b) { vis[fin(a)] = fin (b); return 0; } int kls(int n,int m) { int i; int ans = 0; for (i = 0;i <=n;i++) vis[i] = i; for (i = 0;i < m;i++) { if (fin(e[i].u) != fin(e[i].v)) { add (e[i].u,e[i].v); ans += e[i].w; } } return ans; } int main() { int n,m; while (~scanf ("%d%d",&n,&m)) { cont = 0; int i,k; for (i = 0;i < m;i++) { int a,b,c; scanf ("%d%d%d",&a,&b,&c); //如果有边多次录入,选权最小的那个 int tf = 1; for (k = 0;k < cont;k++) { if ((e[k].u == a && e[k].v == b) || (e[k].u == b && e[k].v == a)) { tf = 0; if (e[k].w > c) e[k].w = c; } } if (tf) { e[cont].u = a; e[cont].v = b; e[cont++].w = c; } } qsort(e,cont,sizeof(e[0]),cmp); int ans = kls(n,m); printf ("%d\n",ans); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。