经典最小生成树prim与kruskal算法分析-比较-总结

例题

农民约翰被选为他们镇的镇长！他其中一个竞选承诺就是在镇上建立起互联网，并连接到所有的农场。当然，他需要你的帮助。

约翰已经给他的农场安排了一条高速的网络线路，他想把这条线路共享给其他农场。

为了用最小的消费，他想铺设最短的光纤去连接所有的农场。

你将得到一份各农场之间连接费用的列表，你必须找出能连接所有农场并所用光纤最短的方案。

输入格式 Input Format

输入格式经常会以两中形式

(1)采用邻接矩阵存储???

第一行为农场的个数，N（3<=N<=100）。

接下去为一个N*N的矩阵,表示每个农场之间的距离。(农场之间的距离小于999，0路线表示无法直接到达)。

(2)图采用边目录方式存储。

第一行N为农场的个数,M为农场与农场之间共有M条可以搭设光纤路线。

接下去的M行为中每行有3个数A，B，C。分别表示农场A到农场B的距离为C。

输出格式 Output Format

输出连接所有农场并所用光纤最短的方案。 (输出之后要求换行)

样例输入 Sample Input

?

(1)采用邻接矩阵存储。???????????????????????????????? (2)采用边目录方式存储。?????

6????????????????????????????????????????????????????????????????? ?? 6???? 7
0 3 0 0 0 2????????????????????????????????????????????????????? 1???? 2???? 3
3 0 5 0 2 0????????????????????????????????????????????????????? 2???? 3???? 5
0 5 0 1 0 0?????????????????????????????????????????????????????? 3???? 4???? 1
0 0 1 0 4 0?????????????????????????????????????????????????????? 4???? 5???? 4
0 2 0 4 0 1?????????????????????????????????????????????????????? 2???? 5???? 2
2 0 0 0 1 0?????????????????????????????????????????????????????? 6???? 5???? 1
???????????????????? ???????????????????????????????????????????????????? 1???? 6???? 2
??????????????????????????????????????????????????????????

样例输出 Sample Output

（1）采用邻接矩阵存储????????????????????????????????? （2）采用边目录方式存储。

10????????????????????????????????????????????????????????????????? 10

?

?

?

?

?

(1)我的prim的代码采用邻接矩阵存储

prim适合采用邻接矩阵存储代码如下

var n,i,j,w,k,t,w1,m,min,p:longint;
ch:char;
lowcost,coset:array[1..100]of longint;
bo:array[1..100]of boolean;
map:array[1..100,1..100]of longint;????????? {邻接矩阵图}
begin
??? while not eof do
??? begin
??????? readln(n);
??????? if n=0 then break;
??????? for i:=1 to n do
????????? for j:=1 to n do??????????????????????????? //初始化
????????? begin
????????????? read(map[i,j]);
????????????? if (i=j)or(map[i,j]=0)then
???????????????? map[i,j]:=maxlongint;???????????????? //把不相连的点之间设为无穷大
????????? end;
??????? for i:=1 to n do
??????? begin
??????????? lowcost[i]:=map[1,i];
??????????? coset[i]:=1;
??????????? bo[i]:=false;
??????????? {初始化lowcost集合(即每个点到集合的最短距离)与bo数组和
??????????? coset(设这个点为A)到集合内于他连接的且最短距离的另一个点(这个点为b)
??????????? 那么coset就是记录与点A的父亲节点B(B一定要具备上述条件）}
??????? end;
??????? bo[1]:=true;
??????? m:=0;
??????? for i:=1 to n-1 do
??????? begin
??????????? min:=maxlongint;
??????????? for j:=1 to n do
????????????? if (bo[j]=false)and(lowcost[j]<min)then??????? //选择与集合距离最短的点
????????????? begin
????????????????? min:=lowcost[j];p:=j;
????????????? end;
????????????? writeln('(',coset[p],',',p,')'); //输出上一步得到的与集合距离啊短距离的点的父亲节点和该点(即集合新选择的最短路径);
????????????? m:=m+min;??????????? //把上一步得到的点到集合的距离不断累加
????????????? bo[p]:=true;?????????? //把以加入的集合的点设为true,防止重判.
????????????? for j:=1 to n do
??????????????? if (bo[j]=false)and(map[p,j]<lowcost[j])then???? //重判集合到那一些还每被选入集合的点的距离
??????????????? begin
??????????????????? lowcost[j]:=map[p,j];????? //重判集合到那一些还每被选入集合的点的距离
??????????????????? coset[j]:=p;?????????????? //刷新父亲节点
??????????????? end;
??????? end;
??????? writeln(m);
??? end;
end.

?

??

?

(2)我的kruskal的代码采用边目录方式存储

?

?

?

?

kruskal适合采用边目录方式存储。

(kruskal的一般版本);

在这里说明一下感染和完全感染的区别以便于理解下面的代码的注释

[感染指一条边中只有一个点被感染了要么是起点,要么是始点,一边中的两点中只有一点被感染称为感染]

[完全感染染指一边中两点都被感染了,只有两点同时都被感染了才称为完全感染。如果该边的两点被完全感染那么这条边也就被完全感染（即false），而没有被完全感染的边或感染的边都为(true)]

解析的不好不要BS我水平有限

type edge=record
?? x,y,c:longint;
?? end;
var n,m,i,j,mincost,min,p:longint;
d:array[1..100] of boolean;
e:array[1..100]of boolean;
elist:array[1..100] of edge;???
begin
??? while not eof do
??? begin
??????? read(n,m);
??????? for i:=1 to m do read(elist[i].x,elist[i].y,elist[i].c);
??????? fillchar(d,sizeof(d),true);???????????????????????????????????????? //读入数据加初始化
??????? fillchar(e,sizeof(e),true);
??????? m:=0;
??????? for j:=1 to n-1 do
??????? begin
??????????? min:=maxlongint;???
??????????? for i:=1 to m do
????????????? if e[i]=true then???????????????????
?????????????? if ((d[elist[i].x]=true) xor (d[elist[i].y]=true)) or (j=1) then //选择感染了的边这样可以完全避开够成环情况(但第一条边需要开绿灯)
??????????????? if (elist[i].c)<min then????? //对被感染了的边进行判断选择其边的值最小的
??????????????? begin??????????????????????????
??????????????????? min:=elist[i].c;p:=i;???? //记录该边的值,以及该边的起点和始点
??????????????? end;????????????????????????????????????????????????????????????
??????????????? d[elist[p].x]:=false; d[elist[p].y]:=false;?? //把该边完全感染(即起点和始点都被感染)
??????????????? writeln('(',elist[p].x,',',elist[p].y,')');???????? //输出新的被完全感染的边的起点和始点(既路径)
??????????????? e[p]:=false;???????????????????? //因为起点和始点都被感染所以该边也应被完全感染??????????????????????
??????????????? m:=m+min;?? //累加被完全感染的边的值
??????? end;
??? writeln(m);
??? end;
end.

?

?

(改进后的kruskal+快排的高效率版本);

type edge=record
?? x,y,c:longint;
?? end;
var n,m,i,j,mincost:longint;
d:array[1..100] of boolean;
e:array[1..100of boolean;
elist:array[1..100] of edge;
procedure qsort(ss,tt:longint);
var i,j,x:longint;
temp:edge;
begin
??? i:=ss;j:=tt;x:=elist[(i+j)div 2].c;
??? while i<=j do
??? begin
??????? while elist[i].c<x do inc(i);
??????? while elist[j].c>x do dec(j);
??????? if i<=j then
??????? begin
??????????? temp:=elist[i];
??????????? elist[i]:=elist[j];
??????????? elist[j]:=temp;
??????????? inc(i);
??????????? dec(j);
??????? end;
??? end;
??? if ss<j then qsort(ss,j);
??? if i<tt then qsort(i,tt);
end;
begin
??? while not eof do
??? begin
??????? read(n,m);
??????? for i:=1 to m do read(elist[i].x,elist[i].y,elist[i].c);
??????? qsort(1,m);
??????? fillchar(d,sizeof(d),true);
??????? fillchar(e,sizeof(e),true);
??????? mincost:=0;
??????? for j:=1 to n-1 do
??????? begin
??????????? for i:=1 to m do
????????????? if e[i]=true then
?????????????? if ((d[elist[i].x]=true) xor (d[elist[i].y]=true)) or (j=1) then
?????????????? begin
?????????????????? d[elist[i].x]:=false; d[elist[i].y]:=false;????? {高效体现在这里，和上面的那个代码比较省去了判断
?????????????????? writeln('(',elist[i].x,',',elist[i].y,')');????????????? 而表面上看感觉不出如何省时，里面切暗藏玄机。
?????????????????? e[i]:=false;?????????????????????????????????????????????? 省时在于每次选择被感染的边都是一次到位决不含糊}
?????????????????? mincost:=mincost+elist[i].c;????????????????????? //下面进行prim,kruskal算法比较会进一步说明
?????????????????? break;
?????????????? end;
??????? end;
??? writeln('tree: ','length=',mincost);
??? end;
end.

?

???????????????????????????????? 个人对prim算法与kruskal算法比较和总结

1 )Prim and Kruskal 算法的空间比较

???? 数据给的情况不同空间有所不同

??? 当点少边多的时候如1000个点500000条边这样BT的数据用prim做就要开一个1000*1000的二维数组

而用kruskal做只须开一个500000的数组，恐怖吧500000跟1000*1000比较相差一半。

?? 当点多边少的时候如1000000个点2000条边像这中BT数据就是为卡内存而存在的，如果用prim做你想开一个1000000*1000000的二维数组没门内存绝对爆挂你。而像这种情况用kruskal只须开一个2000的数组绝对赚到了。

2 )Prim and Kruskal and?? Kruskal+快排 算法的时间比较

??? prim 在跟普通的kruskal比较空间是肯定没有普通的kruskal来的好。但时间方面的话prim就比普通kruskal来的更恐怖一些，用prim时间比普通的kruskal快20倍。在这时我就想如那数据变态的很用普通的kruskal绝对超时，用prim绝对1爆的内存那就掺了。这时惟有改进prim算法从中砍内存，怎么砍，换一个超大内存的电脑，你去那找啊。拿刀砍，开玩笑。方法一放弃。方法二在改进kruskal算法从中砍时间，经过反复的折腾最后（在老师的指导下）想到了普通的kruskal在选择感染了的边的时候还要进行搜索其所有被感染了的边中值最小的边，每一次都要在此处进行重复的搜索觉的很费时，索性事先派好序。所以改进后变为kruskal+快排，结果时间跟prim相差无几，而且有省内存。这就是王道啊。。。（回头一看啊哇靠写了好长啊，各位来访的大虾小虾，大牛小牛写的不好不要BS我哦，累了休息一下ZZZZ）