笔记:最小生成树——Kruskal算法 深藏阁楼爱情的钟 2022-06-17 02:44 161阅读 0赞 /\*最小生成树——Kruskal算法 思想:要连接n个城镇,则最少需要n-1条边,也就意味着每两个结点之间都有一条边, 可以先用一个结构体数组记录边的信息,然后每次在选取最小的边,但是需要判断 这条边所连通的的两个结点是否已经连通,因此主要代码实现可以分为两个过程,首先记录边的信息并排序, 第二个过程则为选出当前的最优边,然后可以通过并查集判断这条边将要连通的两个结点是否已经连通, 最小生成树问题不同于最短路径,最短路径是判断在整个图中两个结点的最短优化解,而最小生成树则为连接整个图的整体最优解。 \*/ 题目引入:5-10 镖局运镖(A卷) (30分) 镖局的运镖,就是运货(类似现在的物流)。镖局每到一个新地方开展业务,都需要对运镖途中的绿林好汉进行打点。好说话的打点费就比较低,不好说话的打点费就比较高。龙门镖局现在有一趟镖请你来规划路线,已知城市的地图,你需要选择一些道路进行疏通,以便镖局可以到达任意一个城市,要求花费的银子越少越好。 输入格式: 第一行有两个数n和m,n表示有n个城市(编号从1到n),m表示有m条道路。接下来m行,每行形如“a b c”用来表示一条道路,意思是城市a到城市b连通且打点需要花费的银子数是c。 输出格式: 若通过打点能抵达所有城市,则输出最少需要花费的银子总数。若不能抵达所有的城市则输出“impossible”。 输入样例: 3 3 1 2 1 1 3 2 2 3 4 输出样例: 3 以下为代码笔记 /*最小生成树——Kruskal算法*/ #include <stdio.h> #include <stdlib.h> struct node { int u; int v; int w; }ans[5004];//结构体数组:记录边的信息 int n, f[504];//f[]数组:记录并查集中的每个结点的boss信息 int cmp(const void *a, const void *b) { struct node *c = (struct node *)a; struct node *d = (struct node *)b; return c->w - d->w; }//升序排序 void Init(int a[]);//并查集的初始化操作 int Getf(int v);//并查集的寻找boss操作 int Merge(int u, int v);//并查集的合并操作 int main() { int m, sum, cnt; while(scanf("%d %d", &n, &m) != EOF) { for(int i = 0; i < m; i++) scanf("%d %d %d", &ans[i].u, &ans[i].v, &ans[i].w); qsort(&ans[0], m, sizeof(ans[0]), cmp);//对边的信息进行快速排序 sum = 0, cnt = 0; Init(f);//并查集记录数组的初始化 for(int i = 0; i < m; i++) { if(Merge(ans[i].u, ans[i].v))//通过合并操作判断当前边所连接的两个结点是否在同一集合 { cnt++; sum += ans[i].w; } if(cnt == n-1) break; } if(cnt == n-1) printf("%d\n", sum); else//可能并不能构建最小生成树 printf("impossible\n"); } return 0; } void Init(int a[])//并查集的初始化操作 { for(int i = 1; i <= n; i++) a[i] = i;//初始化默认每个结点的boss是其本身 } int Getf(int v)//并查集的寻找boss操作 { if(v == f[v]) return f[v]; else { f[v] = Getf(f[v]);//路径压缩操作 return f[v]; } } int Merge(int u, int v)//并查集的合并操作(对当前两个结点的boss进行合并) { int t1 = Getf(u);//寻找第一个结点的boss int t2 = Getf(v);//寻找第二个结点的boss if(t1 != t2) { f[t2] = t1;//boss之间的的角逐合并 return 1; } else return 0; }
还没有评论,来说两句吧...