Kruskal算法如何应用于51nod平台的最小生成树问题？

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

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

pythonclass UnionFind: def __init__(self, size): self.root=list(range(size)) self.rank=[1] * size

def find(self, x): if self.root[x] !=x: self.root[x]=self.find(self.root[x]) return self.root[x]

def union(self, x, y): rootX=self.find(x) rootY=self.find(y) if rootX !=rootY: if self.rank[rootX] > self.rank[rootY]: self.root[rootY]=rootX elif self.rank[rootX]

def kruskal(n, edges): uf=UnionFind(n) mst=[] edges.sort(key=lambda x: x[2]) # Sort edges by weight

for edge in edges: u, v, w=edge if uf.find(u) !=uf.find(v): uf.union(u, v) mst.append(edge)

return mst

Example usagen=4edges=[(0, 1, 2), (1, 2, 3), (2, 3, 1), (3, 0, 3), (0, 2, 4), (1, 3, 2)]mst=kruskal(n, edges)print(Minimum Spanning Tree:, mst)

问题：

有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; }