PRIM算法PASCAL怎么写
作者&投稿：印背 （若有异议请与网页底部的电邮联系）
为了减少不必要的麻烦，可以不妨设图中所有边的权重都不同，这样最小生成树是唯一的
然后直接用反证法就行了
如果Prim算法得到G，而最小生成树是T
设在生成G的过程中第一次产生的不在T中的边是e，而在G中去掉e得到的两个连通分支记为V1和V2，那么e连接了V1和V2
把e加入T之后会出现环，在这个环里面V1的顶点和V2的顶点至少还被另一条边f连接（否则T本身就不连通了），由Prim算法的贪心策略可知e比f权重低，那么在T里面把f换成e可得一个总权重更小的生成树，与T的最小性矛盾
（因为最小生成树的总权重的边的权重的连续函数，对于有权重重复出现的情况可以利用连续性取极限，这样即使最小生成树不唯一仍然可以保证Prim算法生成的树具有最小权重）
按产生最小生成树边的次序
, , , ,
【输入样例】
6 10
1 2 10
1 5 19
1 6 21
2 3 5
2 4 6
2 6 11
3 4 6
4 5 18
4 6 14
5 6 33
【输出样例】
1 2 10
2 3 5
2 4 6
2 6 11
4 5 18
program prim_example;
Const
vmax=200
var
w:array[1..vmax,1..vmax]of integer;
i,j,k,v,e:integer;
procedure prim(v0:integer); {v0是开始结点}
var
flag:array[1..vmax] of boolean;
min,prevk,nextk:integer;
begin
fillchar(flag,sizeof(flag),false);
flag[v0]:=true; {先选出v0}
for i:=1 to v-1 do {一共寻找v-1条边}
begin
min:=maxint;
for k:=1 to v do
if flag[k] then {找已在集合中的顶点}
for j:=1 to v do {求满足条件的边的最小值}
if (not(flag[j])) and (w[k,j]<min) and (w[k,j]<>0)
then begin
min:=w[k,j]; {记下最小值}
nextk:=j;
prevk:=k;
end;
if min<>maxint
then begin
flag[nextk]:=true; {最小值对应顶点进入集合}
writeln(prevk,' ',nextk,‘ ',min);
end;
end;{for}
end;{prim}
begin
assign(input,'prim.in');
reset(input);
assign(output,'prim.out');
rewrite(output);
fillchar(w,sizeof(w),0);
readln(v,e);
for k:=1 to e do
begin
read(i,j);
readln(w[i,j]);
w[j,i]:=w[i,j];
end;
prim(1);
close(input);
close(output);
end.
楼上很对
爱吉金路： 最小生成树【输入样例】 6 10 1 2 10 1 5 19 1 6 21 2 3 5 2 4 6 2 6 11 3 4 6 4 5 18 4 6 14 5 6 33 【输出样例】 1 2 10 2 3 5 2 4 6 2 6 11 4 5 18 program prim_example;Const vmax=200var w:array[1..vmax,1..vmax]of integer; i,j,k,v,e:integer;procedure...
湛江市15251877351： 求最小生成树的标准程序(PASCAL语言) - ？
爱吉金路： 你是要prim还是kruskal? 两种算法适用范围不同 prim的时间复杂度是点的个数的平方 kruskal的时间复杂度是边的平方 kruskal如果用并查集优化,可以达到O(nlogn)的水平我把两种算法的核心代码都贴出来吧:procedure prim;var closest:array[1.....
湛江市15251877351： 求广度搜索理论,详细一点,谢谢(PASCAL语言)？
爱吉金路： 宽度优先搜索 BFS 宽度优先搜索算法(又称广度优先搜索)是最简便的图的搜索算法之一,这一算法也是很多重要的图的算法的原型.Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想. 已知图G=(V,E)和一...
湛江市15251877351： 什么是普利姆算法 - ？
爱吉金路： Prim算法:是图的最小生成树的一种构造算法.假设 WN=(V,{E}) 是一个含有 n 个顶点的连通网,TV 是 WN 上最小生成树中顶点的集合,TE 是最小生成树中边的集合.显然,在算法执行结束时,TV=V,而 TE 是 E 的一个子集.在算法开始执...
湛江市15251877351： 最小生成树 普里姆算法和克鲁斯卡尔算法 - ？
爱吉金路： kruskal算法的时间复杂度主要由排序方法决定,其排序算法只与带权边的个数有关,与图中顶点的个数无关,当使用时间复杂度为O(eloge)的排序算法时,克鲁斯卡算法的时间复杂度即为O(eloge),因此当带权图的顶点个数较多而边的条数较少...
湛江市15251877351： Prim算法的实现过程? - ？
爱吉金路： G=(V,E) ①初始化:读入的数据用邻接矩阵x存储,一个一维布尔型数组chosen,记录第i个节点是否已选,初始值除1外全部设为false,记录权值的变量cost赋值为0; 以下②到④循环执行v-1次(每次生成一条边,运行(点的个数减1)次后,生...
湛江市15251877351： pascal程序怎么写?？
爱吉金路： pascal语言是系统的,你要从头学习了才会啊 ⒈一个PASCAL程序分为两个部分:程序首部和程序体(或称分程序). ⒉程序首部是程序的开头部分,它包括: ⑴程序标志.用“program”来标识“这是一个PASCAL 程序”.PASCAL规定任...
湛江市15251877351： 利用Prim(普里姆)算法 构造最小生成树 程序 - ？
爱吉金路： 算法同样是解决最小生成树的问题.其算法为:在这n个点中的相通的边进行排序,然后不断地将边添加到集合中(体现了贪心的算法特点),在并入集合之前,必须检查一下这两点是不是在一个集合当中,这就用到了并查集的知识.直到边的...
湛江市15251877351： 普利姆算法 是什么？
爱吉金路： Prim算法用于求无向图的最小生成树 设图G =(V,E),其生成树的顶点集合为U. ①、把v0放入U. ②、在所有u∈U,v∈V-U的边(u,v)∈E中找一条最小权值的边,加入生成树. ③、把②找到的边的v加入U集合.如果U集合已有n个元素,则结束...
湛江市15251877351： 编写一个Pascal程序计算圆周率 - ？
爱吉金路： 给出几个程序,楼主选一个吧:var x,i,j:extended; begin x:=4; i:=3; repeat j:=i*i; x:=x*((j-1)/j); i:=i+2; until i>5E8; /*计算到i>5亿为止*/ writeln(x:0:18); /*输出计算的结果*/ writeln(PI:0:18) /*输出Pascal储存的常量结果*/ end.{$N+} var i:longint; pi,j:...
