经典最小生成树prim与kruskal算法分析比较例题农民约翰被选为他们镇的镇长！他其中一个竞选承诺就是在镇上建立起互联网，并连接到所有的农场。当然，他需要你的帮助。约翰已经给他的农场安排了一条高速的网络线路，他想把这条线路共享给其他农场。为了用最小的消费，他想铺设最短的光纤去连接所有的农场。你将得到一份各农场之间连接费用的列表，你必须找出能连接所有农场并所用光纤最短的方案。输入格式InputFormat输入格式经常会以两中形式(1)采用邻接矩阵存储第一行为农场的个数，N（3<=N<=100）。接下去为一个N*N的矩阵,表示每个农场之间的距离。(农场之间的距离小于999，0路线表示无法直接到达)。(2)图采用边目录方式存储。第一行N为农场的个数,M为农场与农场之间共有M条可以搭设光纤路线。接下去的M行为中每行有3个数A，B，C。分别表示农场A到农场B的距离为B。输出格式OutputFormat输出连接所有农场并所用光纤最短的方案。(输出之后要求换行)样例输入SampleInput(1)采用邻接矩阵存储。(2)采用边目录方式存储。667030002123305020235050100341001040454020401252200010651162样例输出SampleOutput（1）采用邻接矩阵存储（2）采用边目录方式存储。1010(1)我的prim的代码采用邻接矩阵存储prim适合采用邻接矩阵存储代码如下varn,i,j,w,k,t,w1,m,min,p:longint;ch:char;lowcost,coset:array[1..100]oflongint;bo:array[1..100]ofboolean;map:array[1..100,1..100]oflongint;{邻接矩阵图}beginwhilenoteofdobeginreadln(n);ifn=0thenbreak;fori:=1tondoforj:=1tondo//初始化beginread(map[i,j]);if(i=j)or(map[i,j]=0)thenmap[i,j]:=maxlongint;//把不相连的点之间设为无穷大end;fori:=1tondobeginlowcost[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;fori:=1ton-1dobeginmin:=maxlongint;forj:=1tondoif(bo[j]=false)and(lowcost[j]<min)then//选择与集合距离最短的点beginmin:=lowcost[j];p:=j;end;writeln('(',coset[p],',',p,')');//输出上一步得到的与集合距离啊短距离的点的父亲节点和该点(即集合新选择的最短路径);m:=m+min;//把上一步得到的点到集合的距离不断累加bo[p]:=true;//把以加入的集合的点设为true,防止重判.forj:=1tondoif(bo[j]=false)and(map[p,j]<lowcost[j])then//重判集合到那一些还每被选入集合的点的距离beginlowcost[j]:=map[p,j];//重判集合到那一些还每被选入集合的点的距离coset[j]:=p;//刷新父亲节点end;end;writeln(m);end;end.(2)我的kruskal的代码采用边目录方式存储kruskal适合采用边目录方式存储。(kruskal的一般版本);在这里说明一下感染和完全感染的区别以便于理解下面的代码的注释[感染指一条边中只有一个点被感染了要么是起点,要么是始点,一边中的两点中只有一点被感染称为感染][完全感染染指一边中两点都被感染了,只有两点同时都被感染了才称为完全感染。如果该边的两点被完全感染那么这条边也就被完全感染（即false），而没有被完全感染的边或感染的边都为(true)]解析的不好不要BS我水平有限typeedge=recordx,y,c:longint;end;varn,m,i,j,mincost,min,p:longint;d:array[1..100]ofboolean;e:array[1..100]ofboolean;elist:array[1..100]ofedge;beginwhilenoteofdobeginread(n,m);fori:=1tomdoread(elist[i].x,elist[i].y,elist[i].c);fillchar(d,sizeof(d),true);//读入数据加初始化fillchar(e,sizeof(e),true);m:=0;forj:=1ton-1dobeginmin:=maxlongint;fori:=1tomdoife[i]=truethenif((d[elist[i].x]=true)xor(d[elist[i].y]=true))or(j=1)then//选择感染了的边这样可以完全避开够成环情况(但第一条边需要开绿灯)if(elist[i].c)<minthen//对被感染了的边进行判断选择其边的值最小的beginmin:=elist[i].c;p:=i;//记录该边的值,以及该边的起点和始点end;d[elist[p].x]:=false;d[elist[p].y]:=false;//把该边完全感染(即起点和始...