最小生成树有两个经典算法：Prim算法和Kruskal算法，Prim适合于点较少的图，对于一个节点数为N的连通图来说，其时间复杂度为O(N^2)；Kruskal适合于边较少的图，对一个边为E的连通图来说，其时间复杂度为O(ElogE)，因此要根据不同情况选择合适的算法。
这里说一下Prim算法。
Prim的具体步骤为把所有点分为两个部分：属于集合S，或不属于S，当所有点都属于S时，算法结束。
1.初始条件先将第一个点p0划到S中，然后利用p0关联的所有边更新cost[]（sost[i]表示pi与S中点相连的最短的那条边长）
2.每次从sost[]中选出最小的那一个cost[i]（i不能属于S），将i加入到S中，并利用与i相关的边更新cost[]（已加入到S中的点不用再更新）
3.反复执行第二步，直到图连通。（我们知道一个有n个节点的图，最少只需要n-1条边就可以连通了，所以第二步会执行n-1次，每次都会在图中加入一条边）
关于Kruskal请参阅：
http://www.cppblog.com/hoolee/archive/2012/08/04/186253.html下面是zoj1203的Prim算法代码：
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define MAX 1000000
#define LENN 110
typedef struct
{
double x;
double y;
}Point;
int main()
{
int i, j, k;
int N, n;
Point ps[LENN];
double mp[LENN][LENN];
double cost[LENN];
int bl[LENN];
scanf("%d", &N);
n = 0;
int gard = 0;
while(N != 0)
{
for(i = 0; i < N; i++)
scanf("%lf%lf", &ps[i].x, &ps[i].y);
for(i = 0; i < N; i++)// make map[][]
for(j = i + 1; j < N; j++)
{
double dx = ps[i].x - ps[j].x;
double dy = ps[i].y - ps[j].y;
double lent = sqrt(dx * dx + dy * dy);
mp[i][j] = mp[j][i] = lent;
}
for(i = 0; i < N; i++)
mp[i][i] = MAX;
double len = 0;
bl[0] = 1;
for(i = 1; i < N; i++)
{
cost[i] = mp[0][i];
bl[i] = 0;
}
for(i = 0; i < N - 1; i++)//prim
{
double min = MAX;
int t;
for(k = 0; k < N; k++)
if(bl[k] == 0 && cost[k] < min)
{
min = cost[k];
t = k;
}
bl[t] = 1;
len += min;
for(j = 0; j < N; j++)// update
if(bl[j] == 0 && mp[t][j] < cost[j])
cost[j] = mp[t][j];
}
if(gard++ != 0)
putchar(10);
printf("Case #%d:\n", ++n);
printf("The minimal distance is: %.2lf\n", len);
scanf("%d", &N);
}
//system("pause");
}
posted on 2012-08-06 17:46
小鼠标 阅读(3129)
评论(0) 编辑 收藏 引用 所属分类:
图论