最小生成樹有兩個經典算法：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.shnenglu.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
小鼠標 閱讀(3146)
評論(0) 編輯 收藏 引用 所屬分類:
圖論