2023年8月1日发(作者：)
克鲁斯卡尔
最小生成树—克鲁斯卡尔算法
克鲁斯卡其尔算法的时间复杂度为O（eloge）(e为网中边的数目)，因此它相对于普里姆算法而言，适合于求边稀疏的网的最小生成树。
克鲁斯卡尔算法从另一途径求网的最小生成树。假设连通网N=（V，{E}），则令最小生成树的初始状态为只有n个顶点而无边的非连通图T=（V，{∮}），图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。依次类推，直至T中所有顶点都在同一连通分量上为止。
例如图为依照克鲁斯卡尔算法构造一棵最小生成树的过程。代价分别为1，2，3，4的四条边由于满足上述条件，则先后被加入到T中，代价为5的两条边（1，4）和（3，4）被舍去。因为它们依附的两顶点在同一连通分量上，它们若加入T中，则会使T中产生回路，而下一条代价（=5）最小的边（2，3）联结两个连通分量，则可加入T。因此，构造成一棵最小生成树。
上述算法至多对 e条边各扫描一次，假若以“堆”来存放网中的边，则每次选择最小代价的边仅需O（loge）的时间（第一次需O（e））。又生成树T的每个连通分量可看成是一个等价类，则构造T加入新的过程类似于求等价类的过程，由此可以以“树与等价类”中介绍的 mfsettp 类型来描述T，使构造T的过程仅需用O（eloge）的时间，由此，克鲁斯卡尔算法的时间复杂度为O（eloge）。
①
6 5
1
④
② 5 5
③
3
6 4 2
6
⑥
⑤
①
①
①
1
1
④
②
④
②
1
④
②
③
③
3
③
2
2
⑥⑤
⑥⑤
⑥⑤
①
①
1
④
1
②
5
④
②
③
③
3
3
4 2
4 2
⑥⑤
⑥⑤
.3-1. 克鲁斯卡尔
program kruskal;
label 10;
const max=6;
s:ax] of byte=((0,6,1,5,0,0),
(0,0,5,0,3,0),
(0,0,0,5,6,4),
(0,0,0,0,0,2),
(0,0,0,0,0,6),
(0,0,0,0,0,0));
var p:array[1..(max*(max-1) div 2),0..2] of byte; 存所有边数（存权、两端点）
f:ax] of integer; 生成树邻接表
q:ax,1..2] of integer; 生成树链表
i,j,l,m,n,zs:integer;
begin
for i:=1 to max do q[i,2]:=0; 链表指针清零
l:=0;
for i:=1 to max do 找出所有边
for j:=1 to max do
if s[i,j]<>0 then
begin
l:=l+1;p[l,0]:=s[i,j];p[l,1]:=i;p[l,2]:=j
end;
for i:=1 to l-1 do 边按权升序排序
for j:=i+1 to l do
if p[i,0]>p[j,0] then
begin
zs:=p[i,0];p[i,0]:=p[j,0];p[j,0]:=zs;
zs:=p[i,1];p[i,1]:=p[j,1];p[j,1]:=zs;
zs:=p[i,2];p[i,2]:=p[j,2];p[j,2]:=zs;
end;
f[p[1,1],p[1,2]]:=p[1,0]; 第一条边加入生成树邻接表
q[p[1,1],1]:=p[1,1];q[p[1,1],2]:=-p[1,1];端点加入链表，根节点链指针为负
q[p[1,2],1]:=p[1,2];q[p[1,2],2]:=p[1,1];
i:=1;j:=0; I：所选边的序号，j：当前要选的边数
repeat
i:=i+1;m:=p[i,1];n:=p[i,2]; 取当前选中边的两端点序号
repeat 分别查找两端点的根
if m>0 then m:=q[m,2]
until m<=0;
.3-2. 克鲁斯卡尔
repeat
if n>0 then n:=q[n,2]
until n<=0;
if (m<0) and (m=n) then goto 10; 若为同一根，则重选
f[p[i,1],p[i,2]]:=p[i,0]; 当前边加入生成树邻接表
if m=n then 当前边两端点均不在树中，则新建一棵树
begin
q[p[i,1],1]:=p[i,1];q[p[i,1],2]:=-p[i,1];
q[p[i,2],1]:=p[i,2];q[p[i,2],2]:=p[i,1]
end;
if (m<0) and (n=0) then 若一端点在某棵树中，则加入
begin
q[p[i,2],1]:=p[i,2];q[p[i,2],2]:=p[i,1]
end;
if (n<0) and (m=0) then 若另一端点在某棵树中，则加入
begin
q[p[i,1],1]:=p[i,1];q[p[i,1],2]:=p[i,2];
end;
if (m<0) and (n<0) then q[-n,2]:=-m; 边接两棵树
j:=j+1;
10:until j>max-1;
for i:=1 to max do 输出生成树邻接表
begin
for j:=1 to max do write(f[i,j]);
writeln;
end;
end.
.3-3.
2023年8月1日发(作者：)
克鲁斯卡尔
最小生成树—克鲁斯卡尔算法
克鲁斯卡其尔算法的时间复杂度为O（eloge）(e为网中边的数目)，因此它相对于普里姆算法而言，适合于求边稀疏的网的最小生成树。
克鲁斯卡尔算法从另一途径求网的最小生成树。假设连通网N=（V，{E}），则令最小生成树的初始状态为只有n个顶点而无边的非连通图T=（V，{∮}），图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。依次类推，直至T中所有顶点都在同一连通分量上为止。
例如图为依照克鲁斯卡尔算法构造一棵最小生成树的过程。代价分别为1，2，3，4的四条边由于满足上述条件，则先后被加入到T中，代价为5的两条边（1，4）和（3，4）被舍去。因为它们依附的两顶点在同一连通分量上，它们若加入T中，则会使T中产生回路，而下一条代价（=5）最小的边（2，3）联结两个连通分量，则可加入T。因此，构造成一棵最小生成树。
上述算法至多对 e条边各扫描一次，假若以“堆”来存放网中的边，则每次选择最小代价的边仅需O（loge）的时间（第一次需O（e））。又生成树T的每个连通分量可看成是一个等价类，则构造T加入新的过程类似于求等价类的过程，由此可以以“树与等价类”中介绍的 mfsettp 类型来描述T，使构造T的过程仅需用O（eloge）的时间，由此，克鲁斯卡尔算法的时间复杂度为O（eloge）。
①
6 5
1
④
② 5 5
③
3
6 4 2
6
⑥
⑤
①
①
①
1
1
④
②
④
②
1
④
②
③
③
3
③
2
2
⑥⑤
⑥⑤
⑥⑤
①
①
1
④
1
②
5
④
②
③
③
3
3
4 2
4 2
⑥⑤
⑥⑤
.3-1. 克鲁斯卡尔
program kruskal;
label 10;
const max=6;
s:ax] of byte=((0,6,1,5,0,0),
(0,0,5,0,3,0),
(0,0,0,5,6,4),
(0,0,0,0,0,2),
(0,0,0,0,0,6),
(0,0,0,0,0,0));
var p:array[1..(max*(max-1) div 2),0..2] of byte; 存所有边数（存权、两端点）
f:ax] of integer; 生成树邻接表
q:ax,1..2] of integer; 生成树链表
i,j,l,m,n,zs:integer;
begin
for i:=1 to max do q[i,2]:=0; 链表指针清零
l:=0;
for i:=1 to max do 找出所有边
for j:=1 to max do
if s[i,j]<>0 then
begin
l:=l+1;p[l,0]:=s[i,j];p[l,1]:=i;p[l,2]:=j
end;
for i:=1 to l-1 do 边按权升序排序
for j:=i+1 to l do
if p[i,0]>p[j,0] then
begin
zs:=p[i,0];p[i,0]:=p[j,0];p[j,0]:=zs;
zs:=p[i,1];p[i,1]:=p[j,1];p[j,1]:=zs;
zs:=p[i,2];p[i,2]:=p[j,2];p[j,2]:=zs;
end;
f[p[1,1],p[1,2]]:=p[1,0]; 第一条边加入生成树邻接表
q[p[1,1],1]:=p[1,1];q[p[1,1],2]:=-p[1,1];端点加入链表，根节点链指针为负
q[p[1,2],1]:=p[1,2];q[p[1,2],2]:=p[1,1];
i:=1;j:=0; I：所选边的序号，j：当前要选的边数
repeat
i:=i+1;m:=p[i,1];n:=p[i,2]; 取当前选中边的两端点序号
repeat 分别查找两端点的根
if m>0 then m:=q[m,2]
until m<=0;
.3-2. 克鲁斯卡尔
repeat
if n>0 then n:=q[n,2]
until n<=0;
if (m<0) and (m=n) then goto 10; 若为同一根，则重选
f[p[i,1],p[i,2]]:=p[i,0]; 当前边加入生成树邻接表
if m=n then 当前边两端点均不在树中，则新建一棵树
begin
q[p[i,1],1]:=p[i,1];q[p[i,1],2]:=-p[i,1];
q[p[i,2],1]:=p[i,2];q[p[i,2],2]:=p[i,1]
end;
if (m<0) and (n=0) then 若一端点在某棵树中，则加入
begin
q[p[i,2],1]:=p[i,2];q[p[i,2],2]:=p[i,1]
end;
if (n<0) and (m=0) then 若另一端点在某棵树中，则加入
begin
q[p[i,1],1]:=p[i,1];q[p[i,1],2]:=p[i,2];
end;
if (m<0) and (n<0) then q[-n,2]:=-m; 边接两棵树
j:=j+1;
10:until j>max-1;
for i:=1 to max do 输出生成树邻接表
begin
for j:=1 to max do write(f[i,j]);
writeln;
end;
end.
.3-3.
发布评论