这篇博客是从旧博客 WordPress 迁移过来，内容可能存在转换异常。
建议先看看前言：http://www.wutianqi.com/?p=2298
以前写过一篇最小生成树的文章，见：http://www.wutianqi.com/?p=1284
最小生成树(Minimum Spanning Tree),全称“最小权值生成树”
有两种具体的实现算法
1.Kruskal算法
2.Prim算法
两者都用到了贪心算法。
最小生成树的形成：
23.1节，此节是两种算法的基础，伪代码：
GENERIC_MST(G, w)
A <- 空集
while A does not form a spanning tree
do find an edge(u, v) that is safe for A
A <- A 并 {(u, v)}
return A
重点是每次选择出一条安全边。
要了解的概念：安全边，割，轻边
23.1定理，这里Mark一笔，定理各种纠结，看了半天还是不明白。
Kruskal算法：
思想：该算法每次从所有未使用边中，找出权值最小的边，加入到生成树中，直到加入V-1条边(V是顶点数)，构成一颗MST。
看图23-4，Kruskal的构造过程
具体实现(C/C++):
/*
* Introduction to Algorithms
* Chapter 23 --- MST.Kruskal
* Tanky Woo @ www.WuTianQi.com
* 2012.1.7
*/
#include
#include
using namespace std;
const int maxint = 999999;
typedef struct Road{
int c1, c2; // a到b
int value; // 权值
}Road;
int no;
int line;
Road road[100];
int node[101];
bool myCmp(const Road &a;, const Road &b;)
{
if(a.value < b.value)
return 1;
return 0;
}
int Find_Set(int n)
{
if(node[n] == -1)
return n;
return node[n] = Find_Set(node[n]);
}
bool Merge(int s1, int s2)
{
int r1 = Find_Set(s1);
int r2 = Find_Set(s2);
if(r1 == r2)
return 0;
if(r1 < r2)
node[r2] = r1;
else
node[r1] = r2;
return 1;
}
int main()
{
freopen("input.txt", "r", stdin);
memset(node, -1, sizeof(node));
cout << "Input the number of the node:";
cin >> no;
cout << "Input the number of the line:";
cin >> line;
cout << "Input the edge:";
for(int i=0; i> road[i].c1 >> road[i].c2 >> road[i].value;
}
sort(road, road+line, myCmp);
int sum = 0, count = 0; // sum是MST的值，count是记录已使用的点数
for(int i=0; iPrim算法：
思想：可以通过Dijkstra算法来理解，因为两者的思想非常类似，假设顶点集S，其中集合A是已经加入到生成树中的点，集合B是剩余的点，每次从连接A,B的边中找出权值最小的边，作为生成树的边。
(Dijkstra的讲解见：[http://www.wutianqi.com/?p=1890](http://www.wutianqi.com/?p=1890))
看图23-5，Prim的构造过程
具体实现(C/C++):
```cpp
/*
* Introduction to Algorithms
* Chapter 23 --- MST.Prim
* Tanky Woo @ www.WuTianQi.com
* 2012.1.7
*/
#include
using namespace std;
const int INF=1001;
int no, line;
int arcs[101][101];
int dis[101], vis[101];
int _min;
int main()
{
freopen("input.txt", "r", stdin);
cout << "Input the number of the node:";
cin >> no;
cout << "Input the number of the line:";
cin >> line;
for(int i=0; i> p >> q >> len;
if(len < arcs[p-1][q-1]) // 有重边
{
arcs[p-1][q-1] = len; // p指向q
arcs[q-1][p-1] = len; // q指向p，这样表示无向图
}
}
memset(vis, 0, sizeof(vis));
for(int i=1; i小结：
Kruskal算法和Prim算法的最大区别就是在找安全边时，对于安全边的选择不一样，不过同样都是基于贪心算法的。
Kruskal适合一维数组来管理数据，而Prim则适合用一个二维矩阵来管理边之间的关系，具体选择可以看实际数据的量。
DATE: 2012.1.7 @ Home By Tanky Woo