文档介绍:无向图的生成树就是从图的边集中选择一些边, 使得这些边构成一个连通无环图, 也就是树。如果给每一条边加一个权,所有生成树中权和最小的生成树称为最小生成树。【 Prim 算法思想】任意时刻的中间结果都是一棵树,每次花费最小的代价,用一条边把不在树中的结点加进来。【最小生成树算法实例】现有一张城市地图,图中的顶点为城市,无向边代表两个城市间的连通关系,边上的权代表公路造价。在分析了这张图后发现, 任一对城市都是连通的。现在要求用公路把所有城市联系起来,如何设计可使得工程的总造价最少? 【输入】第一行两个数 v(v<=200),e , 分别代表城市数和边数以下 e行, 每行为两个顶点和它们之间的边权 w(w<1000) 。【输出】 v-1 行, 每行为两个城市的序号, 表明这两个城市间建一条公路, 再加该公路的造价。【输入样例】 6 10 12 10 15 19 16 21 23524626 11 34645 18 46 14 56 33 【输出样例】 12 10 23524626 11 45 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 tov do if flag[k] then { 找已在集合中的顶点} for j:=1 tov do{ 求满足条件的边的最小值} if (not(flag[j])) and (w[k,j]<min) and (w[k,j]<>0) then begin min:=w[k,j