如何用Kruskal算法高效构建最小生成树，应对长尾词挑战？

本文共计944个文字，预计阅读时间需要4分钟。

问题：有n个点，m条边。求该图的最小生成树。分析：问题与上面链接里说的类似，只是解决方法变了。Kruskal算法的实现主要依赖于并查集的思想，最终的目的是把所有点加入到几个集合中。

Kruskal算法的核心思想是：从小到大排序所有的边，然后依次将边加入到最小生成树中，每次加入边之前都要检查该边是否会造成环。如果不会造成环，就将该边加入到最小生成树中，否则就丢弃该边。

具体步骤如下：

1.将所有边按权重从小到大排序。

2.创建一个并查集，用于判断两个点是否属于同一集合。

3.遍历排序后的边，对于每条边：

a. 检查这条边是否会造成环，即判断这条边连接的两个点是否属于同一集合。 b. 如果不会造成环，将该边加入到最小生成树中，并将这条边连接的两个点合并到同一集合中。

4.当最小生成树中的边数达到n-1时，算法结束。

Kruskal算法的时间复杂度主要取决于排序步骤，即O(mlogm)，其中m为边的数量。并查集的操作时间复杂度为O(logn)，其中n为点的数量。因此，总体时间复杂度为O(mlogm + nlogn)。

问题：

有n个点，m条边。求该图的最小生成树。

分析：

问题与上面链接里说的一样，只是解决方法变了。

Kruskal算法的实现主要靠并查集的思想，最终目的把所有点加入到一个几个集合里。

算法思想：

1、把存在的边按边长进行排序，从小到大。目的是从小的边开始遍历，以便找最小生成树

推荐用结构体存边，不要用邻接矩阵存关系

把n个点连接在一起，起始最少需要n-1跳变就够了。因此我们从那m条边里选出n-1条边就够了

2、遍历每一条边。应用并查集，查看每条边的两个端点之间是否相通，如果不相通，这条边就需要连接

3、重复2步骤，直到连接的边达到n-1条，就结束。最小生成树就形成了

代码

//Kruskal #include<stdio.h> #include<string.h> #include<stdlib.h> #include<algorithm> using namespace std; const int INF=5555555; struct side{ int s,t; int len; }s[55555]; int pre[1100];//并查集用的前驱数组 int n,m; bool cmp(side a,side b) { return a.len<b.len; } int find(int x) { if(pre[x]==0) return x; return pre[x]=find(pre[x]); } int main() { while(~scanf("%d%d",&n,&m)) { memset(pre,0,sizeof(pre)); for(int i=0;i<m;i++) { int s1,t,w; scanf("%d%d%d",&s1,&t,&w); s[i].s=s1; s[i].t=t; s[i].len=w; } sort(s,s+m,cmp); int sum=0; int count=0; for(int i=0;i<m && count<n-1;i++) { //记下两端点的队长 int fx=find(s[i].s); int fy=find(s[i].t); if(fx!=fy)//不在一个集合 { pre[fx]=fy; sum+=s[i].len; count++; } } printf("%d\n",sum); } return 0; }