算法导论——Prim

今天来跟大家说一说**最小生成树中的Prim** 首先，**最小生成树是什么呢？**~~能吃吗？是男的还是女的？~~ 最小生成树是指**在一个图V中，它的子集E包含所有节点（联通）且其权值之和最小**，则称该子集为最小生成树 下面解释一下**Prim算法的思路：** 在一棵树中，首先取出一个节点加入**集合V**，剩下的节点在**集合U**中。 每次寻找**与V中某节点相连的且另一端不在集合V中的代价最小边**，并将其另一端加入集合V。 当集合U为空时，最小生成树建立完毕，建树代价为各边权值之和。 （注：**此处加入集合V即意味着离开集合U**） 那么，**代码该怎么写呢？**~~我就不告诉你~~ 非常简单，所以直接上了： ```cpp #include<cstdio> int f[6000][6000],f1[6000],n,m,x,y,z; bool visit[6000]; void prim() { int s=0,ans=0; while(s<n) { int minn=1<<30,to=0; s++; for(int i=1;i<=n;i++) if(!visit[i]&&f1[i]<minn) { minn=f1[i]; to=i; } if(minn!=1<<30)ans+=minn; for(int i=1;i<=n;i++) if(f1[i]>f[to][i]&&!visit[i]) f1[i]=f[to][i]; visit[to]=1; } printf("%d",ans); } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) f[i][j]=1<<30; for(int i=1;i<=m;i++) { scanf("%d%d%d",&x,&y,&z); if(f[x][y]>z)f[y][x]=f[x][y]=z; } for(int i=1;i<=n;i++)f1[i]=f[1][i]; visit[1]=1; prim(); } ``` 所输出的值即为**建立最小生成树的总花费（权值之和）** 可以看出时间复杂度为$O \left ( n^2 \right )$，而Kruskal则是$O \left ( E \log_2 E \right )$（N为点数，E为边数），显然，Prim适合稠密图，Kruskal适合稀疏图 我个人比较喜欢Prim，因为个人认为Prim的适用范围较广（毕竟稠密图） 而且，一般情况下N大了的话，会很恶心，所以Prim就比较好了