这篇博客是从旧博客 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