1、Prim算法 1、Prim算法 ■算法梗橛 ■实例 PrimMST(G,T,)(求以r为根的MST InitCandidateSet(...); 物翰化，夏始的候选轻边集，量T=(任，◆) for(k=0:k<n-1;k++){棠T的n-1条制边 (u,v卢SelectLightEdge(:遮轻边，可能不廉 TE=TEU{(u,v)); 特uy涂红加入时中，自点v加入红点衡 ModifyCandidateSet(...); 根据断红点调童操选轻边 算法终止时U=V,T=V,TE) 1、Prim算法 1、Prim算法 ■算法求精一初始化 ■存储结构 将根涂红加入红点集U,TE=中。 #define Infinity INT_MAX表示最大整数 鸡金锡高经站题药餍耀蕊接 #define n 100 typedef int AdjMatrix[njn;I邻接矩阵 因为树边为空，故将T0.-2全部用来存放候选轻边集。 typedef struct{边 void InitCandidateSet (AdjMatrix G,MST T,int r){ int i,k=0; int fromvex,tovex;起点、，点 for(=O:i长n;i计+)依次形成白点初翰的量短营边存放在士中 int len;/边长度，权值 if (i=r){ MST[n-1]; Tk.fromvex-=r;蒙边起点为红点 Tk.tovex-=i:案边赞点为白点 设邻接矩阵初值：不存在的边其权值为Infinity Tk+.len=Gr;赏边长度，钗值 1、Prim算法 1、Prim算法 算法求精一选轻边 ■算法求精一调整候选轻边集 在当前楼进是贽透，也；蒡到智腔换远 设轻边(uy)涂红后加入到制边中，Tk-2是待调整 集更好？) 的候选轻边集，则须根据新社点整Tk.-2。 void ModifyCandidateSet AdjMatrix G,MST T,int k,int v){ void SelectLightSet MST T,int k){ inti,d;h是新红点 r路读选集拉轻边 f0r(=k;i<n-1;i计+){速历摸选第 d=G小yT.tovex;T四的蜂点是白点，d是斯紫边的长盘 if (T[il.len min mi=T.len:赏边起点为红点 if(d<T问.len){u小千白点move原关联最姬紫边长度 minpos=-i:记豪当前最短黛动的位■ Til.len=d; } T问.fromvex=-V;新紫边取代T,toe原来的绿短素边 if(min=Infinity)error(“G不连通")； return minpos;:/径边为T[minpos } 22 7 1、Prim算法 „ 算法梗概 PrimMST(G,T,r) { //求以r为根的MST InitCandidateSet(…); //初始化，置初始的候选轻边集，置T＝（{r },φ） for (k=0; k<n-1; k++) { //求T的n-1条树边 (u,v)=SelectLightEdge(…); //选轻边，可能不唯一 TE＝TE∪{(u,v)}; //将(u,v)涂红加入树中，白点v加入红点集 ModifyCandidateSet(…); //根据新红点v调整候选轻边集 } } 算法终止时U＝V，T=(V,TE) 8 1、Prim算法 „实例 0 2 3 4 5 1 6 5 1 7 3 2 4 5 5 6 0 2 3 4 5 1 6 5 1 ∞ ∞ 0 2 3 4 5 1 5 5 1 4 5 0 2 3 4 5 1 5 2 1 4 5 0 2 3 4 5 1 5 2 1 4 5 0 2 3 4 5 1 5 2 1 4 3 9 1、Prim算法 „存储结构 ＃define Infinity INT_MAX //表示最大整数 ＃define n 100 typedef int AdjMatrix[n][n]; //邻接矩阵 typedef struct { //树边 int fromvex, tovex; //起点、终点 int len; //边长度，权值 } MST[n-1]; 设邻接矩阵初值：不存在的边其权值为Infinity 10 1、Prim算法 „ 算法求精－初始化 将根r涂红加入红点集U，TE＝φ。 对每个白点i (0≤i ≤n-1, i≠r ), i所关联的最短紫边（r,i） 的长度为G[r][i], 这n-1条最短紫边构成了初始的候选轻边 集。 因为树边为空，故将T[0..n-2]全部用来存放候选轻边集。 void InitCandidateSet (AdjMatrix G, MST T, int r) { int i, k=0; for (i=0; i<n; i++) //依次形成白点i初始的最短紫边存放在T[k]中 if ( i != r ) { T[k].fromvex=r; //紫边起点为红点 T[k].tovex=i; //紫边终点为白点 T[k++].len=G[r][i]; //紫边长度，权值 } } ; 11 1、Prim算法 „ 算法求精－选轻边 在当前候选轻边集 T[k..n-2] 中，选长度最短的紫边。 (Note:T[0..k-1]是红边集，T也是树，为什么针对白点构造候选 集更好？) void SelectLightSet ( MST T, int k) { int i, minpos, min=Infinity; for (i=k; i<n-1; i++) //遍历候选集找轻边 if ( T[i].len < min ) { min=T[i].len; //紫边起点为红点 minpos=i; //记录当前最短紫边的位置 } if (min==Infinity ) error( “G不连通”）; return minpos; //轻边为T[minpos] } ; 12 1、Prim算法 „ 算法求精－调整候选轻边集 设轻边（u,v）涂红后加入到树边中，T[k..n-2]是待调整 的候选轻边集，则须根据新红点v调整T[k..n-2] 。 void ModifyCandidateSet ( AdjMatrix G, MST T, int k, int v) { int i, d; //v是新红点 for (i=k; i<n-1; i++) { //遍历候选集 d=G[v][T[i].tovex]; //T[i]的终点是白点，d是新紫边的长度 if ( d<T[i].len ) {//d小于白点T[i].tovex原关联最短紫边长度 T[i].len=d; T[i].fromvex=v; //新紫边取代T[i].tovex原来的最短紫边 } } } ;