最小生成树 之prim算法.pptx

算法导论4.6最小生成树程胜计科 13-04班问题简介网络G=（V，E）是一个无向连通带权图，E中每一条边（v，w）的权为c[v][w]。如果G的一个子图G’是一棵包含G的所有顶点的树，则称G’为G的生成树。在G的所有生成树中，各边权之和最小的称为G的最小生成树。Prim算法设G=（V，E）是连通带权图，V={1,2,….n}.算法的基本思想是：首先置S={1},然后只要S是V的真子集，就做如下贪心选择：遍历满足i∈?S，j∈?V-S的点，找出c[i][j]最小的边，将顶点加入S中。此过程一直进行到S=V为止，所选取的边构成的就是G的最小生成树。void?prim(int?n,?Type **c)?{???Typelowcost[MAX];???int?clost[max];? bool s[max]; s[1]=true;?for?(i?=?2;?i?=?n;?i++)???{???lowcost[i]?=?c[1][i];???clost[i]?=?1;??s[i]=false;?}?for?(i?=?1;?i?n;?i++)???{???Type min?=? inf;?? int j=1;??for?(int k=?2;?k=?n;?k++)??{???if?(lowcost[k]??min??!s[k])??{??min?=?lowcost[k]? j=k;?}??}???cout??“j??’’?closet[j]??endl;???s[j]=true;??for?(int k=?2;?k=?n;?k++)??{???if?(c[j][k]??lowcost[j])?(!s[k])??{???lowcost[k]?=?c[j][k];? closet[k]=j;??}???}????}?初始化遍历邻近点，找出最短距离的边，输出点和边，并放入S。对于新加入S 的点，通过比较最短距离，更新lowcost数组算法过程详解算法的核心在两个数组：closet和lowcost。对于j∈?V-S，closet[j]表示点 j与所有S中点的连线中最短的连接点。而lowcost[j]的值就是c[j][closet[j]].在算法的执行过程中，先找出V-S中是lowcost值最小的点，选取边（j,closet[j]）,将j添加到S中，然后根据与新加入S的点的距离的比较，更新lowcost数组。1Example561425532436656一. 初始化在Prim算法中，最小生成树的起点设置为1.此时S={1}，由于S中只含有点1，故此时 lowcost[i]=c[1][i],Closet[i]=1:Lowcoset[1]=0, Lowcoset[2]=6,Lowcoset[3]=1, Lowcoset[4]=5,Lowcoset[5]=max, Lowcoset[6]=max,(max表示无直接连线)1423651423二.Lowcost 第一次循环 65遍历lowcost数组，找到最小值为lowcost[3]=1，所以将点 3 加入S中，选择的边为（1，3）,此时S={1,3}1142365三. 更新lowcost数组前一步将点 3 加入S，根据定义，数组lowcost和closet可能会发生改变，需要比较连接点的距离，决定是否更新数组。C[3][2]=56,更新lowcost[2]=5,closet[2]=3;C[3][3]=0;C[3][4]=5=5,不更新；C[3][5]=6max,更新lowcost[5]=6,clost[5]=3;C[3][6]=4max,更新lowcost[6]=4,c;ost[6]=3. Lowcost数组第二次循环142365由于上一步lowcost数组更新，故第二次循环，找出最小值。其中最小值为lowcost[6]=4，将点6添加到S中，此时S={1,3,6. Lowcost更新由于新加入点 6，根据定义，数组lowcost和closet可能会发生改变，需要比较连接点的距离，决定是否更新数组：C[6][2]=max ，不更新；C[6][3]=41,不更新；C[6][4]=25,更新lowcost[4]=2,closet[4]=6;C[6][5]=6=6,不更新；C[6][6]=0,不更新此类推………1111114244225333224446566551124253324651最终得到最小生成树S={1，3，6，4，2，5}12425332465时间复杂度由于算法中利用了N x N的for 循环，易知所需的时间为O(n2)END