2023年8月1日发(作者：)

最⼩⽣成树之Kruskal算法 给定⼀个⽆向图，如果它任意两个顶点都联通并且是⼀棵树，那么我们就称之为⽣成树(Spanning Tree)。如果是带权值的⽆向图，那么权值之和最⼩的⽣成树，我们就称之为最⼩⽣成树(MST, Minimum Spanning Tree)。 我们由最⼩⽣成树的定义，可以延伸出⼀个修建道路的问题：把⽆向图的每个顶点看作村庄，计划修建道路使得可以在所有村庄之间通⾏。把每个村庄之间修建道路的费⽤看作权值，那么我们就可以得到⼀个求解修建道路的最⼩费⽤的问题。 常见求解最⼩⽣成树的算法有Kruskal算法和Prim算法。由于篇幅问题再此对于Prim算法，就不多做解释了。现在我们看看Kruskal算法，是怎么来求解最⼩⽣成树的问题。1、Kruskal算法描述 Kruskal算法是基于贪⼼的思想得到的。⾸先我们把所有的边按照权值先从⼩到⼤排列，接着按照顺序选取每条边，如果这条边的两个端点不属于同⼀集合，那么就将它们合并，直到所有的点都属于同⼀个集合为⽌。⾄于怎么合并到⼀个集合，那么这⾥我们就可以⽤到⼀个⼯具——-并查集(不知道的同学请移步：)。换⽽⾔之，Kruskal算法就是基于并查集的贪⼼算法。2、Kruskal算法流程 对于图G(V,E)，以下是算法描述：输⼊： 图G输出： 图G的最⼩⽣成树具体流程：(1)将图G看做⼀个森林，每个顶点为⼀棵独⽴的树(2)将所有的边加⼊集合S，即⼀开始S = E(3)从S中拿出⼀条最短的边(u,v)，如果(u,v)不在同⼀棵树内，则连接u,v合并这两棵树，同时将(u,v)加⼊⽣成树的边集E'(4)重复(3)直到所有点属于同⼀棵树，边集E'就是⼀棵最⼩⽣成树 我们⽤现在来模拟⼀下Kruskal算法，下⾯给出⼀个⽆向图B,我们使⽤Kruskal来找⽆向图B的最⼩⽣成树。

⾸先，我们将所有的边都进⾏从⼩到⼤的排序。排序之后根据贪⼼准则，我们选取最⼩边(A,D)。我们发现顶点A,D不在⼀棵树上，所以合并顶点A,D所在的树，并将边(A,D)加⼊边集E‘。 我们接着在剩下的边中查找权值最⼩的边，于是我们找到的(C,E)。我们可以发现，顶点C,E仍然不在⼀棵树上，所以我们合并顶点C，E所在的树，并将边(C,E)加⼊边集E' 不断重复上述的过程，于是我们就找到了⽆向图B的最⼩⽣成树，如下图所⽰：3、Kruskal算法的时间复杂度 Kruskal算法每次要从都要从剩余的边中选取⼀个最⼩的边。通常我们要先对边按权值从⼩到⼤排序，这⼀步的时间复杂度为为O(|Elog|E|)。Kruskal算法的实现通常使⽤并查集，来快速判断两个顶点是否属于同⼀个集合。最坏的情况可能要枚举完所有的边，此时要循环|E|次，所以这⼀步的时间复杂度为O(|E|α(V))，其中α为Ackermann函数，其增长⾮常慢，我们可以视为常数。所以Kruskal算法的时间复杂度为O(|Elog|E|)。4、实战演练 我们现在已经基本了解了Kruskal算法，让我们来⼀道题⽬练练⼿：。这是⼀道⾮常基本的最⼩⽣成树的应⽤，所以我就不做详细说明了，这⾥仅附上代码以供参考：#include #include #define MAXN 10000 + 10using namespace std;int par[MAXN], Rank[MAXN];typedef struct{ int a, b, price;}Node;Node a[MAXN];int cmp(const void*a, const void *b){ return ((Node*)a)->price - ((Node*)b)->price;}void Init(int n){ for(int i = 0; i < n; i++){ Rank[i] = 0; par[i] = i; par[i] = i; }}int find(int x){ int root = x; while(root != par[root]) root = par[root]; while(x != root){ int t = par[x]; par[x] = root; x = t; } return root;}void unite(int x, int y){ x = find(x); y = find(y); if(Rank[x] < Rank[y]){ par[x] = y; } else{ par[y] = x; if(Rank[x] == Rank[y]) Rank[x]++; }}//n为边的数量，m为村庄的数量int Kruskal(int n, int m){ int nEdge = 0, res = 0; //将边按照权值从⼩到⼤排序 qsort(a, n, sizeof(a[0]), cmp); for(int i = 0; i < n && nEdge != m - 1; i++){ //判断当前这条边的两个端点是否属于同⼀棵树 if(find(a[i].a) != find(a[i].b)){ unite(a[i].a, a[i].b); res += a[i].price; nEdge++; } } //如果加⼊边的数量⼩于m - 1,则表明该⽆向图不连通,等价于不存在最⼩⽣成树 if(nEdge < m-1) res = -1; return res;}int main(){ int n, m, ans; while(scanf("%d%d", &n, &m), n){ Init(m); for(int i = 0; i < n; i++){ scanf("%d%d%d", &a[i].a, &a[i].b, &a[i].price); //将村庄编号变为0~m-1（这个仅仅只是个⼈习惯，并⾮必要的） a[i].a--; a[i].b--; } ans = Kruskal(n, m); if(ans == -1) printf("?n"); else printf("%dn", ans); } return 0;} 当然要是觉得不够爽，那就再送⼤家⼀个⼤礼包：(这⾥包含了绝⼤多数的图论题⽬，对于每道题都有难度的注明)。

2023年8月1日发(作者：)

最⼩⽣成树之Kruskal算法 给定⼀个⽆向图，如果它任意两个顶点都联通并且是⼀棵树，那么我们就称之为⽣成树(Spanning Tree)。如果是带权值的⽆向图，那么权值之和最⼩的⽣成树，我们就称之为最⼩⽣成树(MST, Minimum Spanning Tree)。 我们由最⼩⽣成树的定义，可以延伸出⼀个修建道路的问题：把⽆向图的每个顶点看作村庄，计划修建道路使得可以在所有村庄之间通⾏。把每个村庄之间修建道路的费⽤看作权值，那么我们就可以得到⼀个求解修建道路的最⼩费⽤的问题。 常见求解最⼩⽣成树的算法有Kruskal算法和Prim算法。由于篇幅问题再此对于Prim算法，就不多做解释了。现在我们看看Kruskal算法，是怎么来求解最⼩⽣成树的问题。1、Kruskal算法描述 Kruskal算法是基于贪⼼的思想得到的。⾸先我们把所有的边按照权值先从⼩到⼤排列，接着按照顺序选取每条边，如果这条边的两个端点不属于同⼀集合，那么就将它们合并，直到所有的点都属于同⼀个集合为⽌。⾄于怎么合并到⼀个集合，那么这⾥我们就可以⽤到⼀个⼯具——-并查集(不知道的同学请移步：)。换⽽⾔之，Kruskal算法就是基于并查集的贪⼼算法。2、Kruskal算法流程 对于图G(V,E)，以下是算法描述：输⼊： 图G输出： 图G的最⼩⽣成树具体流程：(1)将图G看做⼀个森林，每个顶点为⼀棵独⽴的树(2)将所有的边加⼊集合S，即⼀开始S = E(3)从S中拿出⼀条最短的边(u,v)，如果(u,v)不在同⼀棵树内，则连接u,v合并这两棵树，同时将(u,v)加⼊⽣成树的边集E'(4)重复(3)直到所有点属于同⼀棵树，边集E'就是⼀棵最⼩⽣成树 我们⽤现在来模拟⼀下Kruskal算法，下⾯给出⼀个⽆向图B,我们使⽤Kruskal来找⽆向图B的最⼩⽣成树。

⾸先，我们将所有的边都进⾏从⼩到⼤的排序。排序之后根据贪⼼准则，我们选取最⼩边(A,D)。我们发现顶点A,D不在⼀棵树上，所以合并顶点A,D所在的树，并将边(A,D)加⼊边集E‘。 我们接着在剩下的边中查找权值最⼩的边，于是我们找到的(C,E)。我们可以发现，顶点C,E仍然不在⼀棵树上，所以我们合并顶点C，E所在的树，并将边(C,E)加⼊边集E' 不断重复上述的过程，于是我们就找到了⽆向图B的最⼩⽣成树，如下图所⽰：3、Kruskal算法的时间复杂度 Kruskal算法每次要从都要从剩余的边中选取⼀个最⼩的边。通常我们要先对边按权值从⼩到⼤排序，这⼀步的时间复杂度为为O(|Elog|E|)。Kruskal算法的实现通常使⽤并查集，来快速判断两个顶点是否属于同⼀个集合。最坏的情况可能要枚举完所有的边，此时要循环|E|次，所以这⼀步的时间复杂度为O(|E|α(V))，其中α为Ackermann函数，其增长⾮常慢，我们可以视为常数。所以Kruskal算法的时间复杂度为O(|Elog|E|)。4、实战演练 我们现在已经基本了解了Kruskal算法，让我们来⼀道题⽬练练⼿：。这是⼀道⾮常基本的最⼩⽣成树的应⽤，所以我就不做详细说明了，这⾥仅附上代码以供参考：#include #include #define MAXN 10000 + 10using namespace std;int par[MAXN], Rank[MAXN];typedef struct{ int a, b, price;}Node;Node a[MAXN];int cmp(const void*a, const void *b){ return ((Node*)a)->price - ((Node*)b)->price;}void Init(int n){ for(int i = 0; i < n; i++){ Rank[i] = 0; par[i] = i; par[i] = i; }}int find(int x){ int root = x; while(root != par[root]) root = par[root]; while(x != root){ int t = par[x]; par[x] = root; x = t; } return root;}void unite(int x, int y){ x = find(x); y = find(y); if(Rank[x] < Rank[y]){ par[x] = y; } else{ par[y] = x; if(Rank[x] == Rank[y]) Rank[x]++; }}//n为边的数量，m为村庄的数量int Kruskal(int n, int m){ int nEdge = 0, res = 0; //将边按照权值从⼩到⼤排序 qsort(a, n, sizeof(a[0]), cmp); for(int i = 0; i < n && nEdge != m - 1; i++){ //判断当前这条边的两个端点是否属于同⼀棵树 if(find(a[i].a) != find(a[i].b)){ unite(a[i].a, a[i].b); res += a[i].price; nEdge++; } } //如果加⼊边的数量⼩于m - 1,则表明该⽆向图不连通,等价于不存在最⼩⽣成树 if(nEdge < m-1) res = -1; return res;}int main(){ int n, m, ans; while(scanf("%d%d", &n, &m), n){ Init(m); for(int i = 0; i < n; i++){ scanf("%d%d%d", &a[i].a, &a[i].b, &a[i].price); //将村庄编号变为0~m-1（这个仅仅只是个⼈习惯，并⾮必要的） a[i].a--; a[i].b--; } ans = Kruskal(n, m); if(ans == -1) printf("?n"); else printf("%dn", ans); } return 0;} 当然要是觉得不够爽，那就再送⼤家⼀个⼤礼包：(这⾥包含了绝⼤多数的图论题⽬，对于每道题都有难度的注明)。