const
int
MAXN
=
100
;
class
UFset
{
public
:
int
parent[MAXN];
UFset();
int
Find(
int
);
void
Union(
int
,
int
);
}
;
UFset::UFset()
{
memset(parent,
-
1
,
sizeof
(parent));
}
int
UFset::Find(
int
x)
{
if
(parent[x]
<
0
)
return
x;
else
parent[x]
=
Find(parent[x]);
//
压缩路径
}
void
UFset::Union(
int
x,
int
y)
{
int
pX
=
Find(x);
int
pY
=
Find(y);
int
tmp;
if
(pX
!=
pY)
{
tmp
=
parent[pX]
+
parent[pY];
//
加权合并
if
(parent[pX]
>
parent[pY])
{
parent[pX]
=
pY;
parent[pY]
=
tmp;
}
else
{
parent[pY]
=
pX;
parent[pX]
=
tmp;
}
}
}
//
int g[MAXN][MAXN];
struct
EDGEDATA
{
int
beg, end;
int
q;
}
;
EDGEDATA e[MAXN
*
MAXN];
//
输入边信息
EDGEDATA v[MAXN];
//
返回路径
int
inorder(EDGEDATA a, EDGEDATA b)
{
return
a.q
<
b.q;
}
int
kruskal(
int
nn,
int
n)
//
nn边数, n顶点数
{
int
i;
int
k;
UFset UFS;
int
rnt
=
0
;
//
e 已按权排序
for
(i
=
0
, k
=
0
; i
<
nn; i
++
)
{
if
(UFS.Find(e[i].beg)
!=
UFS.Find(e[i].end))
{
v[k].beg
=
e[i].beg;
v[k].end
=
e[i].end;
v[k].q
=
e[i].q;
rnt
+=
e[i].q;
k
++
;
UFS.Union(e[i].beg, e[i].end);
}
if
(k
==
n
-
1
)
break
;
}
return
rnt;
}
posted on 2006-08-20 01:39
豪 阅读(716)
评论(0) 编辑 收藏 引用 所属分类:
数据结构与算法