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
豪 閱讀(723)
評論(0) 編輯 收藏 引用 所屬分類:
數據結構與算法