Kruskal比Prim简单的多，对已知边排序，然后从排序的边中跳出N-1条最短的来就可以了，当然，如果在挑的过程中出现环，就丢掉继续找，就只这么直接。

如何判定有没有环？很简单，用并查集就可以。

比如a-b,b-c,c-a构成了环，那么a-b合并，b-c合并后，如果紧接着最小边是c-a，那么并查集的find(c,a)操作就会告诉你，c,a是同一个环内，跳过，继续。

总结一下：

(1)对已知边排序（如果用数组存顶点，那么直接用qsort()就行了，如果用vector，那么sort()就行了）

(2)从已排序的边中找出一条最小边，如果该边与当前最小生成树形成环，跳过，否则合并端点e.a，e.b，将当前边加入最小生成树内。

(3)循环。

由于挑选的过程是一个O(e)的过程，那么其实Kurskal的时间复杂度主要由其排序时间决定，O(eloge)。这也是Kruskal非常适合稀疏图的原因。

1 struct Edge 2 { 3     int a; 4     int b; 5     int weight; 6 }; 7  8 int edgeCmp(const void* ea, const void* eb) 9 {10     return reinterpret_cast
      
       (ea)->weight - reinterpret_cast
       
        (eb)->weight;11 }12 13 int N, M;14 int p[100010];15 Edge e[1000010];16 17 int find(int i) 18 {19     if (p[i] == i)20         return i;21     return p[i] = find(p[i]);22 }23 24 void merge(int i, int j)25 {26     if (find(i) != find(j))27         p[find(i)] = find(j);28 }29 30 int kruskal() 31 {32     int res=0;33     qsort(e, M, sizeof(Edge), edgeCmp);34     for (int i = 0; i < M; ++i) 35     {36         if (find(e[i].a) == find(e[i].b))37             continue;38         res += e[i].weight;39         merge(e[i].a, e[i].b);40     }41 42     return res;43 }44 45 int main()46 {47     scanf("%d%d", &N, &M);48     for (int i = 1; i <= N; ++i) p[i] = i;49     for (int i = 0; i < M; ++i)50         scanf("%d%d%d", &(e[i].a), &(e[i].b), &(e[i].weight));51 52     printf("%d\n", kruskal());53 54     return 0;55 }