普里算法是合并顶点的算法，与边的数量无关，因此适用于稠密图。
构建最小生成树必须具有以下两个特征：
1、尽量选择最小权重的边缘，且不得有电路
2、n个顶点只选择n-1条边。
预算法是从最小生成树(简称MST )的性质导出的。
假设N=(V,E)是一个连通图，U是顶点集V的一个非空子集。若(u,v)是一条具有组小权值的边，其中uU，v V-U,则必存在一颗包含(u,v)的最小生成树。
假设3358www.Sina.com/n=(v，e )时的连通图，TE是n上最小生成树中的边的集合。
1、u={uo}(uov )，TE={}。
2、寻找所有uU，vV-U的边(u，v ) e中权重最小的边) uo，vo )编入集合TE，同时将vo编入u。
3、重复2直到U=V。
此时，如果TE中一定有n-1条边，则t=(v，TE )成为n的最小生成树。
图解如下。
(1)图中有6个顶点v1-v6，各边的边权值在图中； 运行prim算法时，首先选择任意顶点作为起始点。 当然，选择v1作为起点。 那么，现在，将u集合作为当前找到的最小生成树内的顶点，将TE集合作为找到的边。 当前状态如下所示。
U={v1}； TE={}；
)2)现在，寻找一个顶点在u集合内，另一个顶点在V-U集合内的最小权重。 如下图所示，在红线相交的线上寻找最小值。
如从附图中明显的，如果边v1-v3的权重最小为1，则如果在u集合中添加v3并在TE中添加(v1，v3 )，则状态如下。
U={v1，v3}； te={(V1，v3 )；
)3)继续寻找，当前状态为U={v1，v3}； te={(V1，v3 )； 在与红线相交的边缘上查找最小值。
如果发现最小权重为(v3，v6 )=4，并将v6添加到u集合并向TE集合添加最小边，则添加后的状态为：
U={v1，v3，v6}； te={(V1，v3 )，(v3，v6 ) }； 像这样循环直到找到所有顶点。
)4)下面的图片显示了所有的搜索过程。
目前，普利姆算法的思路已经明确，但下一个需要解决的问题是如何实现普利姆算法：
prime算法的实现：实现prime算法需要记录每个顶点是否已经嵌入到u中，也需要记录u和V-U中最小边的顶点和权值，所以在下面设定数据类型解决了上述所有问题。
struct{ int adjvex； //最小边位于u中的顶点int lowcost； //最小边权重(}closedge[MVNum]； closedge[i-1]是从V-U的顶点vi到u的最小权重的边缘，两个域：adjvex是边缘在u上的顶点，lowcost是边缘的权重。
显然，closed ge [ I-1 ].low cost (u=min { cost (u，vi )|uU}。 在此，cost ) u，v )表示边) u，v )的权重。
其次，如何才能判断一个顶点是否已经编入u的问题也需要解决。 这里使用巧妙的方法，假设接下来将vi这个顶点编入u，命令： closedge[vi].lowcost=0； 由此，可以将vi间接表示为嵌入到u中。
这样的数据结构存储最小边的权重和最小边的两个顶点。
prim算法步骤： 1，首先将初始化顶点u添加到u中，针对每个剩馀的顶点vi，经由closedge[i]初始化到u边的信息。
2、n-1次循环，进行以下步骤：
从各组边closedge中选择最小边closedge[k]，输出该边，将k编入u，更新剩下各组的最小边信息closedge[j]，对V-U的边增加k到j的边，新边的权重为closedge[j]
算法：注：这里的代码不是直接复制就能实现的。 里面的算法不是代码实现。 然后基于邻接矩阵实现。
voidminiSpantree_prim(graphg，VerTexType u ) intk=locatevex ) g，u )； for(intI=0； iG.vexnum； I ) if ) I！=k ) { closed ge [ I ].low cost=g.arcs [ k ] [ I ]； //初始化为到剩下的顶点的k的权重的closedge[i].adjvex=k； } closedge[k].lowcost=0；//将k点编入u。 //----- -初始化结束，进行n----1个循环，确定n----1边----- for (inti=1； iG.vexnum； I ) { int min=MaxInt； //将所选择的最小边的min初始化为极大值for (intj=0； jG.vexnum； j ) if(closedge[j].lowcost！=0U(closedge[j].lowcostmin(//顶点I未并入u ) (closedge[j].lowcost！=0)且权重当前最小的min min=closedge[j].lowcost； //更新当前最小权重k=I//记录v-u中当前最低权重边的顶点下标} //此路径coutg.vexs [ closed ge [ k ].adjvex ].name '---' g./closedge[k].lowcost=0； 将//k编入u//更新当前从u到V-U的顶点的路径for(intj=0； jG.vexnum； j () if ) g.arcs [ k ] [ j ] closed ge [ j ].low cost ) closed ge [ j ].low cost=g.arcs [ k ] [ j ]； closedge[j].adjvex=k； } } }}
总结：
普里姆算法分为两个部分：
1、初始化：将从开始顶点u到V-U的closedge[i]初始化为从u到其馀顶点边的信息，经由u编入u
2、运行n-1循环。 首先，找出当前从u到V-U的最小权重值的边缘，在V-U的顶点将边缘编入u，更新从u到V-U的顶点的路径
此算法结束后，closedge[]