(1.2.6.2)最小生成树--Prim算法:O(n2) 适合稠密图

时间:2022-10-01 13:54:24

最小生成树

    给定一无向带权图,顶点数是n,要使图连通只需n-1条边,若这n-1条边的权值和最小,则称有这n个顶点和n-1条边构成了图的最小生成树(minimum-cost spanning tree)。

Prim算法

    Prim算法是解决最小生成树的常用算法。它采取贪心策略,从指定的顶点开始寻找最小权值的邻接点。图G=<V,E>,初始时S={V0},把与V0相邻接,且边的权值最小的顶点加入到S。不断地把S中的顶点与V-S中顶点的最小权值边加入,直到所有顶点都已加入到S中。

算法说明

为了方便寻找最小权值的边,构建一最近边结构体CloseEdge:

[cpp]  view plain copy
  1. //最近边  
  2. typedef struct closeedge_tag  
  3. {  
  4.     int adjvex; //邻接点  
  5.     int weight; //权值  
  6. }CloseEdge;  
创建一数组CloseEdge closeedge[n];顶点u属于S,顶点v属于V-S,则closeedge[v].weight=min{weight(u,v)};closeedge[v].adjvex=u;另外设置一bool型的数组add,标记顶点i是否已加入S。结合closeedge和add即可得到当前最小权值边。每当有新的节点加入S时,则需更新closeedge。具体细节看代码。

实例

(1.2.6.2)最小生成树--Prim算法:O(n2) 适合稠密图

从V0开始

(1.2.6.2)最小生成树--Prim算法:O(n2) 适合稠密图

  1. int minTree(int n)  
  2. {  
  3.     int i,j;  
  4.     memset(v,0,sizeof(v));  
  5.     v[0]=1;  
  6.     sum=0;  
  7.     for(i=1;i<n;i++)  
  8.     {  
  9.         min=max;  
  10.         for(j=0;j<n;j++)     //在剩余定点中,找到最小路径值的定点
  11.         {  
  12.             if(!v[j]&&map[0][j]<min)  
  13.             {  
  14.                 min=map[0][j];  
  15.                 flag=j;  
  16.             }  
  17.         }  
  18.         sum+=min;  
  19.         v[flag]=1;  
  20.         for(j=0;j<n;j++)   //加入新定点后,导致连通分量到其他顶点距离变化 
  21.         {  
  22.             if(!v[j]&&map[0][j]>map[flag][j])  
  23.             {  
  24.                 map[0][j]=map[flag][j];  
  25.             }  
  26.         }  
  27.     }  
  28.     return sum;  
  29. }  



(1.2.6.2)最小生成树--Prim算法:O(n2) 适合稠密图(1.2.6.2)最小生成树--Prim算法:O(n2) 适合稠密图