新建 文本文档 (3).txt

普里姆(Prim)算法 （1）算法思想（2）较小紫边集的构造（3）候选紫边集合的修改(4）Prim算法的伪代码描述、、、、。

、普里姆(Prim)算法
（1）算法思想
    　T=(U，TE)是存放MST的集合。
　　①T的初值是({r}，￠)
　　  即最小生成树初始时只有一个红点r，没有红边。
　　②T经过n-1次如下步骤操作，最后得到一棵含n个顶点，n-1条边的最小生成树
    　⒈选择紫边集中一条轻边并扩充进T
　　⒉将轻边连接的蓝点改红点
　　⒊将轻边改红边
    　⒋修改紫边集

（2）较小紫边集的构造
    　若当前形成的T中有k个顶点，|U|=k，|V-u|=n-k，故可能的紫边数目是k(n-k)。从如此大的紫边集中选择轻边是低效的。因此，必须构造较小的紫边集。
    　对于每个蓝点v ∈V-U，从v到各红点的紫边中，只有最短的那一条才有可能是轻边。因此，只须保留所有n-k个蓝点所关联的最短紫边作为轻边的候选集即可。

（3）候选紫边集合的修改
    　当把轻边(u，v)扩充到T时，因为v由蓝变红，故对每个剩余的蓝点j，边(v，j)就由非紫边变为紫边，这条新紫边的长度可能小于蓝点j原来所关联的最短紫边的长度。因此，用长度更小的新紫边取代那些原有的最短紫边。

（4）Prim算法的伪代码描述
 PrimMST(G，T，r){
  //求图G的以r为根的MST，结果放在T=(U，TE)中
    InitCandidateSet(…)；//初始化：设置初始的轻边候选集，并置T=({r}，￠)
    for(k=0；k<n-1；k++){ //求T的n-1条树边
        (u，v)=SelectLiShtEdge(…)；//选取轻边(u，v)；
         T←T∪{(u，v)}；//扩充T，即(u，v)涂红加入TE，蓝点v并人红点集U
        ModifyCandidateSet(…)； //根据新红点v调整候选轻边集
      } 
   }

（5） 算法的执行过程
    　用PRIM算法得到最小生成树的过程【参见动画演示】


  注意：
    　若候选轻边集中的轻边不止一条，可任选其中的一条扩充到T中。
    　连通网的最小生成树不一定是惟一的，但它们的权相等。
【例】在上图(e)中，若选取的轻边是(2，4)而不是(2，1)时，则得到如图(h)所示的另一棵MST。
     
（6）算法特点
    　该算法的特点是当前形成的集合T始终是一棵树。将T中U和TE分别看作红点和红边集，V-U看作蓝点集。算法的每一步均是在连接红、蓝点集的紫边中选择一条轻边扩充进T中。MST性质保证了此边是安全的。T从任意的根r开始，并逐渐生长直至U=V，即T包含了 C中所有的顶点为止。MST性质确保此时的T是G的一棵MST。因为每次添加的边是使树中的权尽可能小，因此这是一种"贪心"的策略。
（7）算法分析
    　该算法的时间复杂度为O(n2)。与图中边数无关，该算法适合于稠密图。