Prim算法 (普里姆)

定义

普里姆算法（Prim算法），图论中的一种算法，可在加权连通图里搜索最小生成树。

原理

设图 G = (V,E)所有顶点的集合为V，MST中顶点的集合为T。

①  从G中选取任意顶点作为MST的根，将其添加至T。

②  循环执行下述处理直至T=V

      在连接T内顶点与V-T内顶点的边中选取权值最小的边 ( )，将其作为MST的边，并将 u 添至T。

实现

代码

 #include<bits/stdc++.h>
 using   namespace   std;
  const   int  inf= 0x3f3f3f3f  ;
  const   int  maxn= 1005  ;
  struct   node
{
    int   v,w;
  node(){}
  node(  int  a, int  b) {v=a;w= b;}
};
vector <node>  edge[maxn];
  int   n,m;
  void   prim();
  int   main()
{
    int  i, from  ,to,w;
  scanf(  "  %d%d  " ,&n,& m);
    for (i= 0 ;i<m;i++ )
  {
    scanf(  "  %d%d%d  " ,& from ,&to,& w);
    edge[  from  ].push_back(node(to,w));
    edge[to].push_back(node(  from  ,w));
  }
  prim();
  system(  "  pause  "  );
    return   0  ;
}
  void   prim()
{
    int  i,j,k,f,mmin,sum= 0 ,vis[maxn]={ 0  },dis[maxn];
  fill(dis,dis + maxn,inf);
  dis[  0 ]= 0  ;
    for (i= 0 ;i<=n;i++ )
  {
      mmin = inf;
        for (j= 0 ;j<=n;j++ )
          if (!vis[j]&&mmin> dis[j])
            mmin =dis[f= j];
      
      sum += mmin;
      vis[f] = 1  ;
        for (j= 0 ;j<edge[f].size();j++ )
      {
            if (!vis[edge[f][j].v]&&dis[edge[f][j].v]> edge[f][j].w)
            dis[edge[f][j].v] = edge[f][j].w;
        }
    }
    printf(  "  最小生成树的权值为%d  "  ,sum);
}  

挑战程序设计竞赛（第2版）

查看更多关于Prim算法 (普里姆)的详细内容...