普里姆（Prim）算法
普里姆（Prim）算法
普里姆（Prim）算法思想
普里姆（Prim）算法是一某个顶点为起点，逐步找各顶点最小权值的边来构建最小生成树。
换一种说法：
从任意一顶点 v0 开始选择其最近顶点 v1 构成树 T1，再连接与 T1 最近顶点 v2 构成树 T2， 如此重复直到所有顶点均在所构成树中为止。
举例
下面一张无向网图
我们以V0为根结点，找到与V0相邻的结点中权值最小的V6
再从当前树中找到权值最小的是V1所有结点同理可得
代码部分
实现思路
- 1、声明两个数组adjvex（用于保存邻接顶点下标）、lowcost（用于记录当前生成树到生育定点的【最小权值】）
- 2、设根结点为0【注：如果是要求从u结点开始，则在方法参数中有u，初始化时0改为u即可】（adjvex [0] =0, lowcost= G->adj[循环的 i ] [0]）
关于0点： - 3、循环套两个循环（循环1、循环2），总共循环N-1次，N为结点数
- 循环1：找出lowcost[ j ]中最小的权值给min，下标给k
- 结点放入树中，对应的lowcost设为0
- 循环2：生成树加入了新的结点，从下标k开始更新lowcost数组值