为了能讲明白这个算法，我们先构造图7-6-1的邻接矩阵，如图7-6-3的右图所示。
    image.png
    也就是说，现在我们已经有了一个存储结构为MGragh的G（见本书7.4节邻接矩阵）。G有9个顶点，它的arc二维数组如图7-6-3的右图所示。数组中我们用65535来代表∞。

    于是普里姆（Prim）算法代码如下，左侧数字为行号。其中INFINITY为权值极大值，不妨是65535，MAXVEX为顶点个数最大值，此处大于等于9即可。现在假设我们自己就是计算机，在调用MiniSpanTree_Prim函数，输入上述的邻接矩阵后，看看它是如何运行并打印出最小生成树的。

    1. /* Prim算法生成最小生成树 */
    2. void MiniSpanTree_Prim(MGraph G){
    4.     int min, i, j, k;
    6.     /* 保存相关顶点下标 */
    7.     int adjvex[MAXVEX];
    9.     /* 保存相关顶点间边的权值 */
    10.     int lowcost[MAXVEX];
    12.     /* 初始化第一个权值为0，即v 0 加入生成树 */
    13.     /* lowcost的值为0，在这里就是此下标的顶点已经加入生成树 */
    14.     lowcost[0] = 0;
    16.     /* 初始化第一个顶点下标为0 */
    17.     adjvex[0] = 0;
    19.     /* 循环除下标为0外的全部顶点 */
    20.     for (i = 1; i < G.numVertexes; i++){
    22.         /* 将v 0 顶点与之有边的权值存入数组 */
    23.         lowcost[i] = G.arc[0][i];
    25.         /* 初始化都为v 0 的下标 */
    26.         adjvex[i] = 0;
    27.     }
    29.     for (i = 1; i < G.numVertexes; i++){
    31.         /* 初始化最小权值为∞，通常设置为不可能的大数字如32767、65535等 */
    32.         min = INFINITY;
    34.         j = 1; k = 0;
    36.         /* 循环全部顶点 */
    37.         while (j < G.numVertexes){
    39.             /* 如果权值不为0且权值小于min */
    40.             if (lowcost[j] != 0 && lowcost[j] < min){
    42.                 /* 则让当前权值成为最小值 */
    43.                 min = lowcost[j];
    45.                 /* 将当前最小值的下标存入k */
    46.                 k = j;
    47.             }
    49.         j++;
    50.         }
    52.         /* 打印当前顶点边中权值最小边 */
    53.         printf("(%d,%d)", adjvex[k], k);
    55.         /* 将当前顶点的权值设置为0，表示此顶点已经完成任务 */
    56.         lowcost[k] = 0;
    58.         /* 循环所有顶点 */
    59.         for (j = 1; j < G.numVertexes; j++){
    61.             /* 若下标为k顶点各边权值小于此前这些顶点未被加入生成树权值 */
    62.             if (lowcost[j] != 0 && G.arc[k][j] < lowcost[j]){
    64.                 /* 将较小权值存入lowcost */
    65.                 lowcost[j] = G.arc[k][j];
    67.                 /* 将下标为k的顶点存入adjvex */
    68.                 adjvex[j] = k;
    69.             }
    70.         }
    71.     }
    72. }

    普里姆算法运行过程：

    1. 程序开始运行，我们由第4～5行，创建了两个一维数组lowcost和adjvex，长度都为顶点个数9。它们的作用我们慢慢细说。
    2. 第6～7行我们分别给这两个数组的第一个下标位赋值为0，adjvex[0]=0其实意思就是我们现在从顶点v0 开始（事实上，最小生成树从哪个顶点开始计算都无所谓，我们假定从v 0 开始），lowcost[0]=0就表示v 0 已经被纳入到最小生成树中，之后凡是lowcost数组中的值被设置为0就是表示此下标的顶点被纳入最小生成树。
    3. 第8～12行表示我们读取图7-6-3的右图邻接矩阵的第一行数据。将数值赋值lowcost数组，所以此时lowcost数组值为{0,10,65535,65535,65535,11,65535,65535,65535}，而adjvex则全部为0。此时，我们已经完成了整个初始化的工作，准备开始生成。
    4. 第13～36行，整个循环过程就是构造最小生成树的过程。
    5. 第15～16行，将min设置为了一个极大值65535，它的目的是为了之后找到一定范围内的最小权值。j是用来做顶点下标循环的变量，k是用来存储最小权值的顶点下标。
    6. 第17～25行，循环中不断修改min为当前lowcost数组中最小值，并用k保留此最小值的顶点下标。经过循环后，min=10，k=1。注意19行if判断的lowcost[j]!=0表示已经是生成树的顶点不参与最小权值的查找。
    7. 第26行，因k=1，adjvex[1]=0，所以打印结果为(0,1)，表示v 0 至v 1 边为最小生成树的第一条边。如图7-6-4所示。

    image.png

    1. 第27行，此时因k=1我们将lowcost[k]=0就是说顶点v 1 纳入到最小生成树中。此时lowcost数组值为{0,0,65535,65535,65535,11,65535,65535,65535}。
    2. 第28～35行，j循环由1至8，因k=1，查找邻接矩阵的第v 1 行的各个权值，与low-cost的对应值比较，若更小则修改low-cost值，并将k值存入adjvex数组中。因第v 1 行有18、16、12均比65535小，所以最终lowcost数组的值为：{0,0,18,65535,65535,11,16,65535,12}。adjvex数组的值为：{0,0,1,0,0,0,1,0,1}。这里第30行if判断的lowcost[j]!=0也说明v 0和v 1 已经是生成树的顶点不参与最小权值的比对了。
    3. 再次循环，由第15行到第26行，此时min=11，k=5，adjvex[5]=0。因此打印结构为(0,5)。表示v 0 至v 5 边为最小生成树的第二条边，如图7-6-5所示。

    image.png

    1. 接下来执行到36行，lowcost数组的值为：{0,0,18,65535,26,0,16,65535,12}。ad-jvex数组的值为：{0,0,1,0,5,0,1,0,1}。12．之后，相信大家也都会自己去模拟了。通过不 断的转换，构造的过程如图7-6-6中图1～图6所示。

    image.png

    有了这样的讲解，再来介绍普里姆（Prim）算法的实现定义可能就容易理解一些。

    假设N=(V,{E})是连通网，TE是N上最小生成树中边的集合。算法从U={u0 }(u0 ∈V)，TE={}开始。重复执行下述操作：在所有u∈U,v∈V-U的边(u,v)∈E中找一条代价最小的边(u 0 ,v0 )并入集合TE，同时v0 并入U，直至U=V为止。此时TE中必有n-1条边，则T=(V,{TE})为N的最小生成树。

    由算法代码中的循环嵌套可得知此算法的时间复杂度为O(n 2 )。