最小生成树有两种算法：Prim和Kruskal，这里说一下Kruskal算法。
其具体算法描述为（我们假设给定的图是连通的）：
1.初始化总花费allcost=0
2.将所有边按边长len从小到大的顺序排序
3.从头到尾依次遍历个边edge[i], 如果该边关联的两个定点不属于同一个集合，则将这两个集合合并，并更新allcost。
Kruskal算法牵涉到集合操作，包括集合的建立和集合的合并，这里用并查集解决，下面简单介绍以下并查集。
并查集用森林来表示，他有以下操作：
初始化：把每个节点所在结合初始化为自身。
查找：查找元素所在的集合，即根节点
合并：将两个在不同集合的元素合并为一个集合，为了保持数的深度的平衡性，在合并之前，应判断两个集合树的深度，如果深度不同，应将深度小的合并到深度大的上面。
关于维持集合树深度的问题，还有另一种做法，就是合并集合的时候并不考虑树的深度，而是在查询的时候改变树的深度。因为没有写过，这里不多说了。下面是poj1258的代码，最直接的最小生成树。
#include<stdio.h>
#include<stdlib.h>
#define LEN 10000
typedef struct//边，包括与边相关的两个定点，以及边长
{
int f;
int t;
int len;
}Edge;
typedef struct //集合，只有根节点的深度才有意义
{
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)//找到该节点所属集合
{
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
小鼠标 阅读(1604)
评论(0) 编辑 收藏 引用 所属分类:
图论