经典最小生成树prim与kruskal算法分析比较.doc

经典最小生成树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 70 3 0 0 0 2 1 2 33 0 5 0 2 0 2 3 50 5 0 1 0 0 3 4 10 0 1 0 4 0 4 5 40 2 0 4 0 1 2 5 22 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]:=ma