经典最小生成树prim与kruskal算法分析比较
更新时间:2023-10-27 04:36:01 阅读量: 综合文库 文档下载
经典最小生成树prim与kruskal算法分析比较 例题
农民约翰被选为他们镇的镇长!他其中一个竞选承诺就是在镇上建立起互联网,并连接到所有的农场。当然,他需要你的帮助。
约翰已经给他的农场安排了一条高速的网络线路,他想把这条线路共享给其他农场。
为了用最小的消费,他想铺设最短的光纤去连接所有的农场。
你将得到一份各农场之间连接费用的列表,你必须找出能连接所有农场并所用光纤最短的方案。
输入格式 Input Format 输入格式经常会以两中形式 (1)采用邻接矩阵存储
第一行为农场的个数,N(3<=N<=100)。
接下去为一个N*N的矩阵,表示每个农场之间的距离。(农场之间的距离小于999,0路线表示无法直接到达)。 (2)图采用边目录方式存储。
第一行N为农场的个数,M为农场与农场之间共有M条可以搭设光纤路线。
接下去的M行为中每行有3个数A,B,C。分别表示农场A到农场B的距离为B。 输出格式 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] 集合距离最短的点 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]:=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) 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 temp:=elist[i]; elist[i]:=elist[j]; elist[j]:=temp; inc(i); dec(j); end; end; if ss 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相差无几,而且有省内存。这就是王道啊。。。
正在阅读:
经典最小生成树prim与kruskal算法分析比较10-27
三年级(2)一班一品主题方案06-09
模糊控制论文03-21
实习报告-2019纪念抗战胜利暑期专题优秀社会实践报告范文 精品12-07
八年级语文上册第一单元3“飞天”凌空跳水姑娘吕伟夺魁记导学案04-08
世界地理知识点总结04-26
技师论文 - 凯美瑞2AZ型发动机结构及故障检修 - 图文04-27
GAT848-2009 爆破作业单位民用爆炸物品储存库安全评价导则05-29
学前教育学学科概述11-24
- 多层物业服务方案
- (审判实务)习惯法与少数民族地区民间纠纷解决问题(孙 潋)
- 人教版新课标六年级下册语文全册教案
- 词语打卡
- photoshop实习报告
- 钢结构设计原理综合测试2
- 2014年期末练习题
- 高中数学中的逆向思维解题方法探讨
- 名师原创 全国通用2014-2015学年高二寒假作业 政治(一)Word版
- 北航《建筑结构检测鉴定与加固》在线作业三
- XX县卫生监督所工程建设项目可行性研究报告
- 小学四年级观察作文经典评语
- 浅谈110KV变电站电气一次设计-程泉焱(1)
- 安全员考试题库
- 国家电网公司变电运维管理规定(试行)
- 义务教育课程标准稿征求意见提纲
- 教学秘书面试技巧
- 钢结构工程施工组织设计
- 水利工程概论论文
- 09届九年级数学第四次模拟试卷
- 算法
- 最小
- 生成
- kruskal
- 比较
- 经典
- 分析
- prim
- 新东方四六级考前串讲讲义
- 税务会计第三次任务
- 幼儿园安全应急预案
- 软件工程实习周记
- 一基于共词分析的中国战略人力资源 管理研究的热点探析
- 企业涉外会计习题集(本科)东财
- 妙西资料
- 2DMove中文操作手册 - 图文
- 三位数加三位数说课稿
- 商场促销活动分析
- 2016年高考一轮复习:人教版教材文言文基础知识梳理文言文知识梳理
- 江西省南昌市2017届高三第二次模拟考试数学(文)试卷及答案
- 厨房日常管理规定
- 贵州省2018年6月普通高中学业水平考试模拟试卷(数学)
- LNG储罐防火间距
- 浒墅关镇社区家长学校工作台帐(模板) - 图文
- 遥感技术在生态环境评价中的应用分析
- 社会安全感现状和原因调查分析 最终稿
- 襄阳市汽车零配件零售公司名录2018版659家 - 图文
- 客户关系管理资源教学参考项目四