贪心算法之Kruskal

克鲁斯卡尔Kruskal算法同Prim算法一样，都是求最小生成树。Kruskal是不断的找最短边，加入集合，且不构成回路。

所以，我们可以给每个点定义一个集合，一边的起点和终点查看是否属于同一集合，如果是说明是回路，不成立，找下一条边。如果不属于同一集合，则成立，并把其中的一个集合的全部节点的集合改为另外一个集合，进行统一。

具体代码如下：

#include 
#include 

using namespace std;
#define MAXNODE 1000

int n,m;
struct Edge{
    int u;
    int v;
    int w;
} e[MAXNODE * MAXNODE];

int nodeset[MAXNODE]; //每个顶点的集合

int Kruskal(int n);

bool Merge(int u, int i);

bool comp(Edge a, Edge b){
    return a.w < b.w;
}

void Init(int n){
    for(int i=0; i < n; i++){
        nodeset[i] = i;
    }
}

int main(){
    cout<<"请输入节点数n和边数m:";
    cin>>n>>m;
    Init(n);
    cout << "请输入节点边的权值：";
    for(int i = 0; i < m; i++){
        cin>>e[i].u>>e[i].v>>e[i].w;
    }
    sort(e, e+m, comp);
    int ans = Kruskal(n);
    cout< 
同时，与Prim算法相比，因为Kruskal是按照边进行的，所以适合边少的情况，即稀疏图。而Prim是按照点进行的，比较适合稠密图。