prim算法建立最小生成树

从A结点出发构造的最小生成树。Р Р (a) (b) (c)Р Р (d) (e) (f)Р Р (g) (h)Р 设计说明:(1)函数中定义一个临时数组lowcost,数组元素lowcost[v]中保存了集合中结点ui与集合V\U中结点uj的所有边中当前具有最小权值的边(u,v)。Р(2)集合U的初值为U={序号为j的结点}。Lowcost的初始值为邻接矩阵数组中第j行的值,这样初始时lowcost中就存放了从集合U中的结点j到V\U中各节点的权值。Р(3)每次从lowcost中寻找具有最小权值的边,根据lowcost的定义,这样的边其弧头结点必然为集合U中的结点,其弧尾结点必然为集合V\U中的结点,当选到这样的边(u,v)时,就保存其结点数据和权值数据到参数closevertex中,并将lowcost[v]置为-1,表示点v加入到了集合U中。Р(4)当节点v从集合V\U加入到集合U后,若存在一条边(u,v),u是集合U的结点,v是集合V\U的节点,且边(u,v)较原先lowcost[v]的权值更小,则用这样的权值修改原先lowcost[v]中相应权值。Р(5)以图(a)所示的带权图为例,调用普利姆函数时数组lowcost的动态变化过程如下所示。其中第一图表示初始结点0在集合U中,结点0到其他结点有两条边,权值分别为50和60;第二图表示结点1加入到集合U中,结点1加入集合U后,因结点1到结点3存在一条权值为65的边,该权值小于原先的无穷大,所以需要把,lowcost[3]改为65,因结点1到结点4存在一条权值为40的边,该权值小于原先的无穷大,所以需要把lowcost[4]改为40,第三图表示结点4加入到集合U后的状态,第四图表示结点3加入集合u后的状态,第五图表示结点5加入到集合U后的状态,第六图表示结点6加入到集合U后的状态,最后一图表示结点3加入到集合U后的状态。