Prim最小生成树板子

普里姆算法可以称为“加点法”，每次迭代选择代价最小的边对应的点，加入到最小生成树中。算法从某一个顶点s开始，逐渐长大覆盖整个连通网的所有顶点。

邻接矩阵存图时间复杂度O(n^2)

1.算法过程描述

　　　给出一个无向图G=<V,E>

图的所有顶点集合为V；分成两个集合初始令集合U= {s} , V'=V−U;
在两个集合U,V'能够组成的边中，选择一条代价最小的边(u0,v0)( u0∈U,v0∈V'),加入到最小生成树中，并把v0并入到集合U中。
重复上述步骤，直到最小生成树有n-1条边或者n个顶点为止。

由于不断向集合U中加点，所以最小代价边必须同步更新；需要建立一个辅助数组lowcost,用来维护集合V'中每个顶点与集合U中最小代价边信息

2.算法实现

 #include<bits/stdc++.h>

 using namespace std;

 const int maxn= 1e4+;

 const double eps= 1e-;

 const int inf = 0x3f3f3f3f;

 const int mod =;

 typedef long long ll;

 typedef long double ld;

 int g[maxn][maxn];

 int mst[maxn];

 int lowcost[maxn];

 int n,m;

 int prim(int x)  //从x点开始扩展

 {

     int sum=;             //边权和

     for(int i=;i<=n;i++)

     {

         lowcost[i]=g[x][i];   //lowcost[i]表示以i为终点的边中最小的权值，等于-1 表示已在集合U中
　　　　　　　//mst[i]=x;           //记录路径的话 开个mst数组 mst[i]=x;表示当前集合U中到点的距离最小的点为x 即边（x,i）为候选边

     }

     lowcost[x]=-;

     for(int i=;i<=n-;i++)

     {

         int mind=inf,minid=;

         for(int j=;j<=n;j++)

         {

             if(lowcost[j]<mind&&lowcost[j]!=-)

             {

                 mind=lowcost[j];　　　　　　　　　　　　//选出最小值（要加入最小生成树的边的边权）

                 minid=j;　　　　　　　　　　　　　　　　　//记录要加入的点

             }

         }

         sum+=mind;

         lowcost[minid]=-;

         for(int i=;i<=n;i++)

         {

             if(lowcost[i]>g[minid][i])           //更新候选值

             {

                 lowcost[i]=g[minid][i];

             }

         }

     }

     return sum;                  //返回最小生成树边权值和

 }

 int main()

 {

     while(scanf("%d %d",&n,&m)!=EOF)   //n个点,m条边

     {

         for(int i=; i<=n; i++)     //赋初值

         {

             for(int j=; j<=n; j++)

                 g[i][j]=inf;

         }

         int u,v,w;

         for(int i=;i<m;i++)

         {

             scanf("%d %d %d",&u,&v,&w);

             g[u][v]=g[v][u]=w;

         }

         int sum=prim();

         printf("%d\n",sum);

     }

 }

3.简单证明prim算法

反证法：假设prim生成的不是最小生成树

1).设prim生成的树为G₀

2).假设存在G_min使得cost(G_min)<cost(G₀) 则在G_min中存在<u,v>不属于G₀

3).将<u,v>加入G₀中可得一个环，且<u,v>不是该环的最长边(这是因为<u,v>∈G_min)

4).这与prim每次生成最短边矛盾

5).故假设不成立，命题得证.

秒客网

Prim最小生成树板子

相关文章