最小生成树是一个连通加权无向图中一棵权值最小的生成树。
Prim算法思想：
设图G顶点集合为U，首先任意选择图G中的一点作为起始点a，将该点加入集合V，再从集合U-V中找到另一点b使得点b到V中任意一点的权值最小，此时将b点也加入集合V；以此类推，现在的集合V={a，b}，再从集合U-V中找到另一点c使得点c到V中任意一点的权值最小，此时将c点加入集合V，直至所有顶点全部被加入V，此时就构建出了一棵MST（Minimum Spanning Tree，最小生成树）。因为有N个顶点，所以该MST就有N-1条边，每一次向集合V中加入一个点，就意味着找到一条MST的边。
代码实现：
//最小生成树
int map[N][N]; //存i到j的路径
int vis[N]; //存该节点是否已经选取过了
int dist[N]; //树到其它各个节点的距离
int prim()
{
int sum =0;
for(int i=0;i<n;i++)
dist[i]= map[0][i];
vis[0]=true;
for(int i=1;i<=n-1;i++) //找n-1条边
{
int minn=INT_MAX;
int index=0;
for(int j=0;j<n;j++) //找当前树到其它节点的最短路径加入树
{
if(vis[j]==false&&dist[j]<minn)
{
minn=dist[j];
index=j;
}
}
sum+=minn;
vis[index]=true;
for(int j=0;j<n;j++) //更新树到树外其它节点的最小距离
{
if(vis[j]==false&&dist[j]>map[index][j])
dist[j]=map[index][j];
}
}
return sum;
}
时间复杂度：O(n^2)
Kruskal算法思想：
Kruskal算法是基于贪心的思想得到的。首先我们把所有的边按照权值先从小到大排列，接着按照顺序选取每条边，如果这条边的两个端点不属于同一集合，那么就将它们合并，直到所有的点都属于同一个集合为止。至于怎么合并到一个集合，需要使用并查集。换而言之，Kruskal算法就是基于并查集的贪心算法。
基本思想是以边为主导地位，始终都是选择当前可用的最小权值的边，步骤如下：
- 设一个有n个顶点的连通网络为G（V,E），最初先构造一个只有n个顶点，没有边的非连通图T（V,Ø），图中每个顶点自成一个连通分量
- 将原图中的所有边按权值从小到大排序
- 从权值最小的边开始，如果这条边连接的两个顶点于图T中不在同一个连通分量中，则添加这条边到图T中
- 重复3，直至T中所有顶点在同一个连通分量中为止
代码实现：
#include <iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
#define maxn 110; //最多点个数
int fa[110]; //并查集存根节点
int n, m; //顶点个数， 边数
struct Edge{
int x, y;
int val;
}edge[5000];
bool cmp(Edge a, Edge b)
{
return a.val < b.val;
}
int findfa(int x) //寻找所在树的根节点，判断是否在同一个连同分量的依据
{
if(fa[x] != x)
fa[x] = findfa(fa[x]);
return fa[x];
//return fa[x] == x ? x : (fa[x] = findfa(fa[x]));
}
int Union(int x, int y) //并查集合并两棵树
{
fa[findfa(x)] = findfa(y);
}
int Kruskal()
{
int cnt = 0;
long sum = 0;
for(int i=1; i<=n; i++) //顶点的编号为[1..n]
fa[i] = i;
sort(edge, edge+m, cmp); //把边从小到大排序，m为边的数目
for(int i=0; i<m; i++)
{
int fx = findfa(edge[i].x);
int fy = findfa(edge[i].y);
if(fx != fy)
{
Union(fx, fy);
cnt++;
sum += edge[i].val;
if(cnt >= n-1) break; //n-1条边均加入同一个集合中
}
}
return sum;
}
int main()
{
cin>>n>>m;
for(int i=0; i<m; i++)
cin>>edge[i].x>>edge[i].y>>edge[i].val;
cout<<Kruskal()<<endl;
return 0;
}
/*
5 7
1 2 3
1 5 1
2 5 4
2 3 5
3 4 2
3 5 6
4 5 7
*/
时间复杂度： O(E*logE)
Kruskal算法每次要从都要从剩余的边中选取一个最小的边。通常我们要先对边按权值从小到大排序，这一步的时间复杂度为为O(ElogE)。Kruskal算法的实现通常使用并查集，来快速判断两个顶点是否属于同一个集合。最坏的情况可能要枚举完所有的边，此时要循环E次，所以这一步的时间复杂度为O(Eα(V))，其中α为Ackermann函数，其增长非常慢，我们可以视为常数。所以Kruskal算法的时间复杂度为O(ElogE)。
总结：
Prim和Kruskal的贪心策略是一样的，都是选取耗费最小的边：
- 对于Prim, 其选取的边（u,v）必有一个顶点已经被覆盖，另一个顶点未被覆盖，适用于稠密图。
- 对于Kruskal, 其选取的边（u,v）任意，只要这个边的加入不会使被覆盖的顶点构成回路，适用于稀疏图。
