最小生成树（贪心思想）

最小生成树是一个连通加权无向图中一棵权值最小的生成树。

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算法就是基于并查集的贪心算法。
基本思想是以边为主导地位，始终都是选择当前可用的最小权值的边，步骤如下：

1. 设一个有n个顶点的连通网络为G（V,E），最初先构造一个只有n个顶点，没有边的非连通图T（V,Ø），图中每个顶点自成一个连通分量
2. 将原图中的所有边按权值从小到大排序
3. 从权值最小的边开始，如果这条边连接的两个顶点于图T中不在同一个连通分量中，则添加这条边到图T中
4. 重复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）任意，只要这个边的加入不会使被覆盖的顶点构成回路，适用于稀疏图。