蛤蟆的数据结构笔记之四十六普里姆算法.docxVIP

46. 蛤蟆的数据结构笔记之四十六普里姆算法 本篇名言：“手莫伸 , 伸手必被捉。 党与人民在监督 , 万目睽睽难逃脱。 汝言惧捉手不伸 , 他道不伸能自觉 , 其实想伸不敢伸 , 人民咫尺手自缩。-- 陈毅” 连通图的生成树是一个极小的连通子图，它含有图中全部的顶点，但只有足以构成一棵树的n-1条边。所谓的最小成本，就是n个顶点，用n-1条边把一个连通图连接起来，并且使得权值的和最小。构造连通网的最小代价生成树，即最小生成树（Minimum Cost Spanning Tree）。 找连通图的最小生成树，经典的有两种算法，普里姆算法和克鲁斯卡尔算法，这里介绍克里姆算法。这篇我们来看下最小生成树的另一个算法，普里姆算法。 1. 普里姆算法 1.1 Prim 算法思想 设 G=（ V,E ）是一个有 n 个顶点的连通图，用 T=(U，TE)表示要构造的最小生成树， 其中 U 为顶点集合，TE 为边的集合。则 Prim 算法的具体步骤描述入下： 1. 初始化：令 U={?}，TE={?}。从 V 中取出一个顶点u0 放入生成树的顶点集 U 中，作为第一个顶点，此时T= ({u0}) ,{φ}); 2. 从 u ∈U ， v ∈(v ? V ) 的边(u，v)中找一条代价最小的边(u*，v*)，将其放入 TE 中，并将v* 放入 U 中； 3. 重复步骤（2） ，直至 U=V 为止。此时集合 TE 中必有 n-1 条边，T 即为所要构造的最小生成树。 通俗讲法：可取图中任意一个顶点V作为生成树的根，之后若要往生成树上添加顶点W，则在顶点V和W之间必定存在一条边。并且该边的权值在所有连通顶点V和W之间的边中取值最小。 一般情况下，假设n个顶点分成两个集合：U（包含已落在生成树上的结点）和V-U（尚未落在生成树上的顶点），则在所有连通U中顶点和V-U中顶点的边中选取权值最小的边。 生成树的过程如下图1 如下图2所示为构造生成树的过程中，辅助数组中各分量值的变化情况，初始归U＝｛v1｝，加入到U集合中的节点，我们将lowcost改成0以示： 2. 代码实现 2.1 Prim函数 定义顶点个数为6个，边的数量为10条。 输入每个顶点的名字。 设置该点到任意其他一个顶点间的举例为无限大。 设置指定点之间的距离，即邻接矩阵。 进入核心代码： 将v0顶点与之有边的权值存入数组, 设置数组lowcost存放边的权值，adjvex存放顶点的序号。 Adjvex[v]为U中距离V最近的一个邻接点，及是边（v,adjvex[v]）,最小权值为lowcost[v] lowcost 保存 顶点集合内顶点到生成树外各顶点的各边上的当前最小权值。 Adjvex保存 顶点集合外各顶点距离集合内哪个顶点最近。 进入主循环，从第一个点开始： 从V0顶点开始(V0加入到最小生成树)，lowcost保存和V0其他顶点的边权值。 lowcost: 0 6 1 5 N N Adjvex: 0 0 0 0 0 0 然后找到与V0最近的点V2，权值为1.同时把lowcost[2]=0,表示V2加入到了最小生成树中。 然后依次比较所有和V0，V2的其他顶点的权值，取较小的权值值存放到lowcost数组中。 如果V2到某个点的距离比V0到某个点的距离要小，则设置Adjvex [某个点] = 2，表示那个店和V2链接着。 结束后：lowcost: 0 5 0 5 6 4 Adjvex: 0 2 0 0 2 2 然后进入下一个点，下个点是和V2点连接权值最小为4的点，该点就是V5点。同时将V5加入到最小生成树中。 然后比较V5和所有其他节点的权值与lowcost对比。发现V5到V3的距离为2，而lowcost中记载的却是5，所示将lowcost[3]=2. lowcost: 0 5 0 2 6 0 Adjvex: 0 2 0 5 2 2 然后进入V3点的循环，权值最小为2的点，该点就是V3点，同时V3加入最小生成树中。 然后比较V3和所有其他节点的权值与lowcost对比，此时剩余点到最小生成树的距离都比到V3点要小。 lowcost: 0 5 0 0 6 0 Adjvex: 0 2 0 5 2 2 接着：找到此时的lowcost最小为5，是当前最小生成树到V1的点, 同时V1加入最小生成树中。 此时： lowcost: 0 0 0 0 6 0 Adjvex: 0 2 0 5 2 2 比较V1和剩余未在最小生成树点的权值与lowcost对比（其实只剩下V4点），发现V1其实比最小生成树到剩余点V4的距离近，那么设置adjvex[4]=1，lowcost[4]=3。 lowcost: 0 0 0 0 3 0 Adjvex: 0 2 0 5 1 2 最后，找到lowc