Kruskal算法

Kruskal算法
来自"NOCOW"
跳转到: 导航, 搜索
目录 [隐藏]
1 预备知识
2 基本思想
3 PASCAL代码
4 C语言代码
5 优化
6 算法实例
6.1 VOJP1045

[编辑] 预备知识
排序算法（必须）
并查集（非必须）
[编辑] 基本思想
假设WN=(V,{E})是一个含有n个顶点的连通网，则按照克鲁斯卡尔算法构造最小生成树的过程为：先构造一个只含n个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有n棵树的一个森林。之后，从网的边集E中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直至森林中只有一棵树，也即子图中含有n-1条边为止。</p>

[编辑] PASCAL代码
Procedure kruskal(V,E);
begin
sort(E,1,m);//将边按照权值排序
for t:=1 to m do begin
if getfather(edge[t].u)<>getfather(edge[t].v) then begin //利用并查集判断两个顶点是否在同一集合内
tot:=tot+edge[t].data;//计算权值和
union(edge[t].u,edge[t].v);//合并顶点
inc(k);//合并次数
end;
end;
if k=n-1 then 形成了一棵最小生成树
else 不存在这样的最小生成树；
end;[编辑] C语言代码
void kruskal(Vertex V,Edge E)
{
sort(E,1,m);//将边按照权值排序
for (t=1;t<=m;t++) {
if( getfather(edge[t].u)!=getfather(edge[t].v) ) { //利用并查集判断两个顶点是否在同一集合内
tot=tot+edge[t].data;//计算权值和
Union(edge[t].u,edge[t].v);//合并顶点
k++;//合并次数
}
}
if( k==n-1 ) 形成了一棵最小生成树;
else 不存在这样的最小生成树;
}[编辑] 优化
在判断两个顶点是否在同一集合内时可用并查集

代码可以如下

procedure union(x,y:longint);
begin
if r[y]<r[x] then
begin
y:=y xor x;
x:=y xor x;
y:=y xor x
end;//Matrix67式交换
//扯淡，谁说这是matrix67发明的 --[[User:Cosechy|Cosechy]] 17:00 2008年11月13日 (CST)
//问题在于，我们都是从M67大牛那里学来的——OiBLtx
//不管怎么交换，请你们保持代码整洁。--Yinger650
p[x]:=y;
if r[y]=r[x] then inc(r[x]);
end;
function find(x:longint):longint;
begin
if x<>p[x] then p[x]:=find(p[x]);
exit(p[x]);
end;
function clear:boolean;
var
i,t:longint;
begin
clear:=true;
t:=find(1);
for i:=2 to m do if find(i)<>t then exit(false);
end;
procedure solve;
var
i,k:longint;
begin
for i:=1 to n do
begin
if clear then exit;
if find(a[i].f)<>find(a[i].t) then
begin
inc(ans,a[i].c);
union(find(a[i].f),find(a[i].t));
end;
end;
end;//注： 使用前请排序[编辑] 算法实例
[编辑] VOJP1045
题目简述：
1、输入：

第一行一个正实数S:要求最小生成树中所有边的长度不大于s
第二行一个正整数n:有n个结点
接下来一共有m行，第i行有两个整数xi,yi和一个实数si，表示点xi和点yi间有一条边，边的长度为si。
输入保证xi不等于yi，两个点之间不会有两条边。
2、输出：

若存在这样的最小生成树，则输出（其中<X>代表最少的电缆线长度，保留两位小数）：
Need <X> miles of cable
否则输出：
Impossible
代码框架：
type edge=record
u,v:longint;
end;
var e:array[1..max] of edge;
rank,p,node:array[1..max] of longint;
w:array[1..max] of real;//w为边的长度（即耗费）
s,cost:real;
es,n:longint; //es为总的边数

procedure swap(n1,n2:longint);
var t:longint;
begin
t:=node[n1]; node[n1]:=node[n2]; node[n2]:=t;
end;

procedure init;
var x,y:longint;
begin
readln(s);
readln(n); es:=0;
while not(eof) do begin
read(x,y);
p[x]:=x; p[y]:=y; //并查集初始化
inc(es);
if x<y then begin
e[es].u:=x; e[es].v:=y;
end else begin
e[es].u:=y; e[es].v:=x;
end;
readln(w[es]);
node[es]:=es;
end;
qsort(1,es);//快排，node[i]为边长第i小的边的序号。程序略
end;

procedure union(x,y:longint);//并查集：合并x,y所在集合
begin
if rank[x]>rank[y] then
p[y]:=x else begin
p[x]:=y;
if rank[x]=rank[y] then inc(rank[y]);
end;
end;
function findset(x:longint):longint;//并查集：查找x所在集合的代表元素
begin
if x<>p[x] then p[x]:=findset(p[x]);
exit(p[x]);
end;

procedure main;
var i:longint;
begin
for i:=1 to n do
if p[i]=0 then begin//若点i为孤立点则无解
writeln('Impossible');
halt;
end;
for i:=1 to es do
if findset(e[node[i]].u)<>findset(e[node[i]].v) then begin
union(findset(e[node[i]].u),findset(e[node[i]].v));
inc(cost,w[node[i]]);
end;
end;

begin
init;
main;
if cost<=s then writeln('Need ',cost:0:2,' miles of cable')
else writeln('Impossible');
end.