最小生成樹有兩種算法：Prim和Kruskal，這里說一下Kruskal算法。
其具體算法描述為（我們假設(shè)給定的圖是連通的）：
1.初始化總花費(fèi)allcost=0
2.將所有邊按邊長len從小到大的順序排序
3.從頭到尾依次遍歷個邊edge[i], 如果該邊關(guān)聯(lián)的兩個定點(diǎn)不屬于同一個集合，則將這兩個集合合并，并更新allcost。
Kruskal算法牽涉到集合操作，包括集合的建立和集合的合并，這里用并查集解決，下面簡單介紹以下并查集。
并查集用森林來表示，他有以下操作：
初始化：把每個節(jié)點(diǎn)所在結(jié)合初始化為自身。
查找：查找元素所在的集合，即根節(jié)點(diǎn)
合并：將兩個在不同集合的元素合并為一個集合，為了保持?jǐn)?shù)的深度的平衡性，在合并之前，應(yīng)判斷兩個集合樹的深度，如果深度不同，應(yīng)將深度小的合并到深度大的上面。
關(guān)于維持集合樹深度的問題，還有另一種做法，就是合并集合的時候并不考慮樹的深度，而是在查詢的時候改變樹的深度。因?yàn)闆]有寫過，這里不多說了。下面是poj1258的代碼，最直接的最小生成樹。
#include<stdio.h>
#include<stdlib.h>
#define LEN 10000
typedef struct//邊，包括與邊相關(guān)的兩個定點(diǎn)，以及邊長
{
int f;
int t;
int len;
}Edge;
typedef struct //集合，只有根節(jié)點(diǎn)的深度才有意義
{
int d;//深度
int p;//父親
}Set;
Edge egs[LEN];
Set set[110];
int cmp(const void *a, const void *b)
{
Edge *a0 = (Edge*)a;
Edge *b0 = (Edge*)b;
return a0 -> len - b0 -> len;
}
int Belong(int i)//找到該節(jié)點(diǎn)所屬集合
{
while(set[i].p != i)
i = set[i].p;
return i;
}
int main()
{
int i, j;
int N;
int len;
int count;
while(scanf("%d", &N) != EOF)
{
count = 0;
for(i = 0; i < N; i++)
for(j = 0; j < N; j++)
{
scanf("%d", &len);
if(j > i)
{
egs[count].f = i;
egs[count].t = j;
egs[count++].len = len;
}
}
for(i = 0; i < N; i++)
{
set[i].d = 0;
set[i].p = i;
}
qsort(egs, count, sizeof(Edge), cmp);
int lenall = 0;
for(i = 0; i < count; i++)//依次遍歷各邊
{
int f = egs[i].f;
int t = egs[i].t;
int fb = Belong(f);
int tb = Belong(t);
if(fb != tb)//不屬于同一個集合，合并
{
lenall += egs[i].len;
if(set[fb].d > set[tb].d)
{
set[tb].p = fb;
}
else if(set[fb].d == set[tb].d)
{
set[tb].p = fb;
set[fb].d++;
}
else
set[fb].p = tb;
}
}
printf("%d\n", lenall);
}
//system("pause");
}
posted on 2012-08-04 14:24
小鼠標(biāo) 閱讀(1632)
評論(0) 編輯 收藏 引用 所屬分類:
圖論