最小生成树（Prim + Kruskal）

Prim算法　

　　构造过程：

　　　　1）任选一个点，以这个点开始，寻找该点可以访问的所有的边；

　　　　2）在可以访问的所有边中找到最小边，这个边必须有一个点还没有访问过（防止出现回路），将还没有访问的点加入集合，并记录添加的边；（加点法）

　　　　3）寻找当前集合可以访问的所有边，重复2过程，直到没有新的点可以加入，即成功构造出最小生成树。

Kruskal算法

　　构造过程：

　　　　1）初始状态是所有点独立的一个图，并没有边相连；

　　　　2）在边集中选择权值最小的最短边，如果这条边依附的顶点在图中的不同连通分量上（不形成回路），就将这条边加进去，否则舍去这条边继续选择下一条最短边；

　　　　3）重复2过程，直到构造出最小生成树。

通过一道简单例题来看看具体代码如何实现：

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1233

Prime写法：

 1 #include<iostream>
 2 #include<cstring>
 3 using namespace std;
 4 const int INF = 0x3f3f3f3f;
 5 int n, ans;
 6 int edge[110][110];
 7 int dis[110];    //顶点i到最小生成树顶点集合的最短距离
 8 int vis[110];
 9 void prime()
10 {
11     ans = 0;
12     for(int i = 1; i <= n; i++)
13         dis[i] = edge[1][i];
14     dis[1] = 0;
15     vis[1] = 1;
16     for(int k = 2; k <= n; k++)
17     {
18         int minn = INF;    //需要加入的边权
19         int pos;    //要加入的顶点序号
20         for(int i = 1; i <= n; i++)
21         {
22             if(!vis[i] && dis[i] < minn)
23             {
24                 minn = dis[i];
25                 pos = i;
26             }
27         }
28         if(minn == INF)    //不是连通图
29             break;
30         vis[pos] = 1;
31         ans += minn;
32         for(int i = 1; i <= n; i++)
33         {
34             if(!vis[i] && dis[i] > edge[pos][i])
35             {
36                 dis[i] = edge[pos][i];
37             }
38         }
39     }
40 }
41 
42 int main()
43 {
44     int s, e, w;
45     while(cin >> n && n)
46     {
47         memset(vis, 0, sizeof(vis));
48         int m = n * (n - 1) / 2;
49         for(int i = 1; i <= m; i++)
50         {
51             cin >> s >> e >> w;
52             edge[s][e] = edge[e][s] = w;    //无向图
53         }
54         prime();
55         cout << ans << endl;
56     }
57     return 0;
58 }

kruskal写法：

 1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 const int maxn = 1e4 + 10;
 5 int n, m, ans;
 6 int far[maxn];
 7 struct node
 8 {
 9     int s, e, w;
10 } edge[maxn];
11 bool cmp(node a, node b)
12 {
13     return a.w < b.w;
14 }
15 int find(int x)
16 {
17     return (far[x] == x) ? far[x] : (far[x] = find(far[x]));
18 }
19 void unite(int x, int y)
20 {
21     int xx = find(x);
22     int yy = find(y);
23     if(xx != yy)
24         far[yy] = xx;
25 }
26 void kruskal()
27 {
28     ans = 0;
29     sort(edge, edge + m, cmp);
30     for(int i = 0; i <= n; i++)
31         far[i] = i;
32     for(int i = 0; i < m; i++)
33     {
34         int xx = find(edge[i].s);
35         int yy = find(edge[i].e);
36         if(xx != yy)
37         {
38             unite(edge[i].s, edge[i].e);
39             ans += edge[i].w;
40         }
41     }
42 }
43 int main()
44 {
45     while(cin >> n && n)
46     {
47         m = n * (n - 1) / 2;
48         for(int i = 0; i < m; i++)
49         {
50             cin >> edge[i].s >> edge[i].e >> edge[i].w;
51         }
52         kruskal();
53         cout << ans << endl;
54     }
55     return 0;
56 }