详细求解最小生成树的prime算法0x01。 对于prim算法3358www.Sina.com/(prim算法)，可以在加权连接图中检索最小生成树。 也就是说，这意味着由通过该算法搜索到的边的子集构成的树不仅包含连通图中的所有顶点(英语： vertex ) (graphtheory ) )，而且其所有边的权重之和也是最小的
0x02 .既然生成树和最小生成树树算法是关于最小生成树的算法，那么什么是生成树和最小生成树呢？
定义生成树：合并图中的生成树是包含图中所有普里姆算法个顶点和n条边的极小合并子图。
简单理解生成树：生成树简单地说就是从地图中生成树。 此树包含地图的所有顶点。
这里应该有几个生成树必须满足的条件：
1 .不能有封闭的部分。 因为如果合上了就不叫树了。
2 .必须包括所有顶点。
3 .满足其他树的特征。
理解最小生成树：最小生成树是指生成一个树，成本最低。 这意味着树中包含的所有边的权重和最小值。
0x03 .普利姆算法代码是经典算法，所以先看代码。
voidminSpantree_prim(graphg ) {int min，I，j，k； int adjvex[MAXSIZE]； //顶点下标int lowcost[MAXSIZE]； //保存顶点之间的边的权重lowcost[0]=0； //初始化的第一个权重值为0，a被添加到生成树adjvex[0]=0； //for(I=1； i G.numv； I ) {lowcost[i]=G.edge[0][i]； adjvex[i]=0； (for ) I=1； i G.numv； I ) {min=INTMAX； j=1； k=0； while(jg.numv ) if ) lowcost[j]！=0lowcost[j]min(min=lowcost[j] )； k=j； (j )； }printf ('边%c到%c合并在生成树n '、G.ver[adjvex[k]]、G.ver[k]中)； lowcost[k]=0； for(j=1； j G.numv； j () if ) lowcost[j]！=0g.edge [ k ] [ j ] low cost [ j ] { low cost [ j ]=g.edge [ k ] [ j ]； adjvex[j]=k； }}}}0x04 .图解代码流程下图为有向网络图。 顶点n-1分别是顶点表的ABCDEFGHI元素。
让我们来看一下代码流程演示。 代码0~8号创建了第4，5行和adjvex两个数组。 其中，3358www.Sina.com/用于保存顶点
代码lowcost分别初始化两个阵列中的adjvex，距离a顶点lowcost为http://www.Sina.com 当中的某个个数为第6，7行时，有这个下标的顶点表中的0号下标的意思是假设从a
代码lowcost[0]=0的循环表示为A和lowcost数组赋值。
此时的置为0t是顶点被纳入生成树。
此时的adjvex[0]=0都是第8~12行。
将代码lowcost、adjvex设定为lowcost以找出最小权重； 3358www.Sina.com/设置为adjvex作为下一个循环的循环变量。lowcos存储权重最小的顶点的下标。
代码[0,8,32767,32767,32767,9,32767,32767,32767]的循环位于adjvex
wcost中权值最小的值，和它对应的下标。代码第27行，输出了生成树中的第一条边，此时的k表示的是lowcost中权值最小的边对应的顶点，而adjvex[k]则表示这条边的另一个顶点，在这也就是A。
代码第28行，lowcost[k]=0，表示顶点k已加入生成树，对于locost中0的值，以后都不进行操作。
代码第29~36行，再进行一次循环，此时的k=1，那么这次循环的目的就是查找邻接矩阵中顶点B所对应的边的权值，与之前lowcost中的值比较，若有值更小，则修改lowcost中的值，并将k存入adjvex。
此时的lowcost为[0,0,16,32767,32767,9,14,32767,10]。
此时的adjvex为[0,0,1,0,0,0,1,0,1]。
第一遍大循环完成，此时的生成树如图所示（红色部分）：
我们发现一次大循环的目的就是找到一条权值最小的边加入最小生成树。
再来看第二次大循环。
由于第一次小循环的目的是找到lowcost中权值最小的值和顶点，那么再经历第一次小循环后，k应该等于值为9对于的下标，也就是5，而adjvex[5]=0，所以此次加入的边应该是A--F。
第二次小循环的目的是改变lowcost中的值，那么再经历第二次小循环，此时k=5，循环结束后，lowcost应为[0,0,16,32767,24,0,14,32767,10]，adjvex应为[0,0,1,0,5,0,1,0,1]。
此时的生成树为：
再来第三次大循环：
第一个小循环过后，找到最小权值对于的下标k为8，adjvex[8]=1，也就是说边B--I加入生成树。
第二个小循换过后，遍历k有关的边有没有比lowcost中的值小的，循环过后，lowcost应为[0,0,16,19,24,0,14,32767,0]，adjvex应为[0,0,1,8,5,0,1,0,1].
此时的生成树为：
第四次大循环：
第一次小循环结束后，k=6，adjvex[6]=1,说明边B--G加入生成树。
第二次小循换结束后，lowcost为[0,0,16,19,24,0,0,17,0]，adjvex为[0,0,1,8,5,0,1,6,1]
此时的生成树如图：
第五次大循环：
第一次小循换后，k=2，adjvex[2]=2，说明边B--C加入生成树。
第二次小循环后，lowcost为[0,0,0,19,24,0,0,17,0]，adjvex为[0,0,1,8,5,0,1,6,1]。
此时的生成树如图：
第六次大循环：
第一次小循换后，k=7，afjvex[7]=6,说明边G--H加入生成树；
第二次小循换后，lowcost为[0,0,0,14,5,0,0,0,0]，adjvex为[0,0,1,7,7,0,1,6,1]。
此时的生成树为：
第七次大循环：
第一次小循换后，k=5，adjvex[5]=7，说明边H--E加入生成树。
第二次小循换后，lowcost为[0,0,0,14,0,0,0,0,0]，adjvex为[0,0,1,7,7,0,1,6,1]。
此时的生成树为：
第八次大循环：
第一次小循换，k=3，adjvex[3]=7，说明边H--D加入生成树。
第二次小循换，lowcost全为0，生成树已完成，无意义。
此时的生成树为：
代码到此执行完毕，最小生生成树构造完成。
一个大循环里面两个小循环，时间复杂度应为 O（e)=2e*e；
0x05.原理深究 1.关于lowcost，adjvex数组到底怎么理解。lowcost是整个普里姆算法的核心部分，它的含义就是存储各边的权值，为0就代表，该下标所对应的顶点已加入生成树，不需要再考虑，这个权值应该这样理解，是对于已加入这棵生成树的顶点的所有边的最小权值，这个最小指的是和这个权值下标连成的边的最小权值。
例如，当第一次循环的时候，lowcost为[0,8,32767,32767,32767,9,32767,32767,32767]。第一个0代表第一个顶点已加入生成树，第二个8代表，第二个顶点到已加入生成树的所有顶点之中权值最小的值，那么如何知道在第二个小循换中，改变了的话，是对于第几个顶点来说的，这个时候adjvex[k]的值就是对于第几个顶点而言，比如，此时的adjvex[2]=1，代表8这个值是对于第二个顶点来说，所有已加入生成树的顶点到这个顶点的最小权值。
lowcost每次在第一次小循换中，会找出一个最小值出来，并找到对应的顶点加入生成树。这个过程实际上就是找到所有顶点权值最小里面的最小。
lowcost中每有一个为0就是有一个顶点加入了生成树，当所有顶点都加入后，lowcost中的值都为0。
adjvex是存储相关顶点的下标的，那么这个顶点下标究竟指的是什么呢？我们可以看它是什么时候改变的呢，就是在第二个小循换才开始改变的，每次改变存的是一个权值对应的下标，所以可以这样理解，这个下标其实是与lowcost相同位置的值对应的，是表示lowcost里这个权值是对于第几个顶点而言的最小值，adjvex里的这个值和lowcost里那个数据对应的下标，就是这个权值所代表的边的两个端点。
具体两个数组是何用处，可以在不断的演练上述过程中发现规律。
2.对于第二个小循换而言，为什么是找相对位置的小值。也就是说如何理解代码 if (lowcost[j] != 0 && G.edge[k][j] < lowcost[j])，为什么是以k为顶点的每个权值去和对应地方的权值比较，而不是综合比较这个顶点的所有权值里面的最小值？
这个原因其实就是lowcost中所存数据的意义，是对于每个特定顶点的权值最小值，而不是所有的最小值。
0x06.普里姆算法感悟普里姆算法就是巧妙的利用了两个数组，对每一次循环都能找到一个最小值去加入生成树。每一次循环都巧妙的找出了已加入生成树的顶点的相应边对应的权值。
巧妙利用数组的下标的意义，能够使原本复杂的代码简便不少。
对数组中的元素赋以特定的值使之含义丰富。
本章结束。