最小生成树的算法严蔚敏教材提及两种，目的都是在无向加权连通图中寻找最小生成树。两种算法主要思想均为贪心法，一个是将点加入到树中，一个是搜集边最后组合成树。
prim
prim方法首先随机定一个起点，然后遍历其他点，找到离此顶点最近的点加入到树中，再遍历其他顶点，找到离当前两个顶点中任意一个距离最近的点，按着这种添加方法，将所有点加入到树中，就完成了prim方法。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
int m,n,u,v,w;
int dis[100][100],pre[100],sl[100];
int prim(){
for(int i=2;i<=n;i++){
pre[i]=1;//pre[i]为i点所接的上一个顶点
sl[i] = dis[1][i];//sl[i]shortLine为所有顶点至当前树的距离
}
sl[1] = 0;//为0代表已经选出
pre[1] = 0;
int sum = 0;
for(int i=2;i<=n;i++){
int min = 0x3f3f3f;
int id = 0;
for(int j=2;j<=n;j++){
if((sl[j]!=0) && (min>sl[j])){
min = sl[j];
id = j;
}
}
cout<<pre[id]<<" "<<id<<" "<<min<<endl;
sum+=min;
sl[id] = 0;
for (int j=2; j<=n; j++) {
if (dis[id][j] < sl[j]) {
sl[j] = dis[id][j];
pre[j] = id;
}
}
}
return sum;
}
/*样例
5 5
1 2 1
2 3 2
3 4 3
4 5 4
1 5 3
*/
int main(int argc, const char * argv[]) {
memset(dis,0x3f3f3f,sizeof(dis));//邻接表储存图
scanf("%d%d",&n,&m);//点 边
for(int i=1;i<=m;i++){
cin>>u>>v>>w;
dis[u][v] = dis[v][u] = w;
}//构建图（从1至n）
int ans = prim();
cout<<ans<<endl;
return 0;
}
prim方法需要维护两个数组，一个数组保存着边的信息被定义为 pre[maxN] pre[i]是i节点所连的前一个顶点，当只需要求得最小生成树的权值时很明显可以把它省略掉。另一个数组 sl[maxN] 保存着的是未加入树的点与已经形成的树的距离，每加入一个新的点，新的点的sl值设为0，与新的点相连的点的sl[i]值也需要与i到新增点的距离进行判断取最小值，最后重新设置pre值。易知，当树构建完毕时，sl数组应该全为零。
#并查集
在学习下一种求最小生成树的方法之前，我们先学习一下并查集的相关知识。
并查集的主要目的就是把一个森林转化为几棵分别有共同根节点的树。要达到这个目的需要在每次加入新的边的时候自动连在根节点上，当然有些点在插入的时候没办法连在根节点上，所以在所有点插入完毕后再整体进行一次找根节点。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
using namespace std;
int pre[100];
int find(int x){
int r = x;
// 找到老大
while(pre[r] != r){
r = pre[r];
}
// 路径压缩--将一路上的点都直接连在老大身上
int j = x,k;
while(j != r){
k = pre[j];
pre[j] = r;
j = k;
}
return r;
}
void join(int a,int b){
int pa = find(a);
int pb = find(b);
if (pa != pb) {
pre[pa] = pb;
}
}
int main () {
int n,m,u,v;
scanf("%d%d",&n,&m);
// 初始化pre
for (int i=0; i<=n; i++) {
pre[i] = i;
}
for (int i=0; i<m ; i++) {
scanf("%d%d",&u,&v);
join(u,v);
}
// 再进行一次整体的查找使根最少
for (int i=1; i<=n; i++) {
find(i);
}
for (int i=1; i<=n; i++) {
printf("%d ",pre[i]);
}
return 0;
}
我最喜欢里面 路径压缩 的部分了，路径压缩 是听起来十分高大上的一个词汇，但是它实现的原理十分简单，就是从当前点找到根节点，一路上遇到的所有不符合要求的数据全部连接在根节点上。
在join中，将节点少的点的根接入节点多的点的根能减小运行时间，不过要做到这一点需要额外进行其他操作，这里就不展开讨论了。
kruskal
有了并查集的知识，再来看kruskal就眼前一亮了，kruskal算法根据边的权值大小从小权值开始加入不能组成回路的边时，就需要并查集的理念，检查即将加入的边的两个端点是否有相同的根，如果有相同的根就不能添加，换下一条边。 思路已经理清了，下面我来尝试一下。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <iostream>
using namespace std;
struct edge{
int u,v,w;
bool operator < (const edge &x) const{
return w < x.w;
};
}edge;
int pre[100];
int find(int x){
int r = x;
// 找到老大
while(pre[r] != r){
r = pre[r];
}
// 路径压缩--将一路上的点都直接连在老大身上
int j = x,k;
while(j != r){
k = pre[j];
pre[j] = r;
j = k;
}
return r;
}
bool join(int a,int b){
int pa = find(a);
int pb = find(b);
if (pa != pb) {
pre[pa] = pb;
}
else {
return false;
}
return true;
}
int main () {
int n,m,u,v,w;
struct edge e[10000];
scanf("%d%d",&n,&m);
for (int i=0; i<=n; i++) {
pre[i] = i;
}//初始化pre
for (int i=0; i<m ; i++) {
scanf("%d%d%d",&u,&v,&w);
e[i].u = u;
e[i].v = v;
e[i].w = w;
}
sort(e, e+m);
int sum = 0;
for (int i=0; i<m; i++) {
bool res = join(e[i].u, e[i].v);
if(res) {
cout<<e[i].u<<" "<<e[i].v<<endl;
sum += e[i].w;
}
}
printf("%d\n",sum);
return 0;
}
思路十分简单，创建了一个struct来储存边，输入结束后，对边进行排序，依次添加边，如果遇到相同根的边就抛去不管，直至所有边添加成功。
由此我们也可以看出，当边数比较多时，kruskal算法可就没有prim好用了。
