大话数据结构--Prim算法

7.5.4Prim算法

普里姆算法在找最小生成树时，将顶点分为两类，一类是在查找的过程中已经包含在生成树中的顶点（假设为 A 类），剩下的为另一类（假设为 B 类）。

对于给定的连通网，起始状态全部顶点都归为 B 类。在找最小生成树时，选定任意一个顶点作为起始点，并将之从 B 类移至 A 类；然后找出 B 类中到 A 类中的顶点之间权值最小的顶点，将之从 B 类移至 A 类，如此重复，直到 B 类中没有顶点为止。所走过的顶点和边就是该连通图的最小生成树。

假如从顶点 出发，顶点 的权值分别为3、4，所以对于顶点 来说，到顶点 的权值最小，将顶点 加入到生成树中：

继续分析与顶点 和   相邻的所有顶点（包括   ），其中权值最小的为 ， 将   添加到生成树当中：

继续分析与顶点 和   相邻的所有顶点中权值最小的顶点，发现为 ，则添加到生成树当中。

继续分析与生成树中已添加顶点相邻的顶点中权值最小的顶点，发现为 ，则添加到生成树中：

重复上面的过程，直到生成树中包含图中的所有顶点，我们直接看接下来的添加过程：

此时算法结束，我们找出了图中的最小生成树。

讲的真好!!!

搬运的视频，可以关注下这个，讲数据结构讲的真的好!

Prim算法执行过程。

Prim算法代码实现

// Prim算法生成最小生成树
 void MiniSpanTree_Prim(MGraph G)
 {
  int min, i, j, k;
  int adjvex[MAXVEX];  // 保存相关顶点下标
  int lowcost[MAXVEX]; // 保存相关顶点间边的权值
  lowcost[0] = 0;   // V0作为最小生成树的根开始遍历，权值为0(0,3,*,*,*,4,*,*,*)
  adjvex[0] = 0;   // V0第一个加入
  // 初始化操作
  for( i=1; i < G.numVertexes; i++ )
  {
   lowcost[i] = G.arc[0][i]; // 将邻接矩阵第0行所有权值先加入数组
   adjvex[i] = 0;    // 初始化全部先为V0的下标
  }
  // 真正构造最小生成树的过程
  for( i=1; i < G.numVertexes; i++ )
  {
   min = INFINITY;  // 初始化最小权值为65535等不可能数值
   j = 1;
   k = 0;
   // 遍历全部顶点
   while( j < G.numVertexes )
   {
    // 找出lowcost数组已存储的最小权值
    if( lowcost[j]!=0 && lowcost[j] < min )
    {
     min = lowcost[j];
     k = j;  // 将发现的最小权值的下标存入k，以待使用。
    }
    j++;
   }
   //K的取值依次为：1,5,8,2,6,7,4,3
   // 打印当前顶点边中权值最小的边
   printf("(%d,%d)", adjvex[k], k);(0,1)
   lowcost[k] = 0;  // 将当前顶点的权值设置为0，表示此顶点已经完成任务，进行下一个顶点的遍历(0,0,*,*,*,4,*,*,*)
   // 邻接矩阵k行逐个遍历全部顶点(k=1,)
   for( j=1; j < G.numVertexes; j++ )
   {
    if( lowcost[j]!=0 && G.arc[k][j] < lowcost[j] )
    {
     lowcost[j] = G.arc[k][j];
     adjvex[j] = k; 
    }
   }
  }
 }

时间复杂度分析

上面的代码中，当 i == 1的时候，内层的 while 与 for 循环中 j 的取值范围是从 1 到 n-1，内循环一共计算了 2(n-1) 次，其中n为图中的顶点个数；

当 i == 2 的时候，内层循环还是一共计算 2(n-1) 次；

以此类推......

i 取最大值 n -1，内层循环还是一共计算 2(n-1) 次；

所以，整体的执行次数就是 (n-1) * 2(n-1)，Prim算法的复杂度是 级别的。