希赛教育计算机专业考研专业课辅导招生
希赛教育计算机专业考研专业课辅导视频
希赛教育计算机考研专业课在线测试系统
普里姆算法从另一个角度构造连通网的最小生成树它的基本思想是首先选取图中任意一个顶点v作为生成树的根之后继续往生成树中添加顶点w则在顶点w和顶点v之间必须有边且该边上的权值应在所有和v相邻接的边中属最小在一般情况下假设图G=(VE) 中已落在生成树上的顶点集为U则尚未落在生成树上的顶点集为VU则从 (VU) 顶点集中选取加入生成树的顶点w应满足下列条件它和生成树上的顶点之间的边上的权值是在联接这两类顶点的所有边中权值属最小
假设首先选顶点a作为生成树的根则此时只有顶点a在生成树中其余顶点bcdefg均不在生成树上联接这两类顶点的边只有(ab)(af) 和 (ag)其中以边 (ab) 的权值为最小由此应该选择边 (ab) 将顶点b加入到生成树中之后链接 {ab} 和 {cdefg} 这两个顶点集的边除了原有的(af)(ag) 之外又增加了 (bc) 和 (bg)在这四条边中权值最小的边为(bc)(权值=)自然应选边 (bc)即将顶点c加入到生成树中之后应在链接顶点集 {abc} 和 {defg} 的边集 {(af)(ag)(bg)(cd)} 中选择权值最小的边(ag)……依次类推直至所有顶点都落到生成树上为止上述构筑生成树的过程如演示所示（过程中蓝色的边为待选边红色的边为选中的边）
