数据结构-最小生成树

生成树

生成树是连通图的最小连通子图。所谓最小是指：若在树中任意增加一条边，则将出现一个回路；若去掉一条边，将会使之变成非连通图。按照该定义，n个顶点的连通网络的生成树有n个顶点，n-1条边。

最小生成树

设G=(V,E)是一个无向连通图,生成树上各边的权值之和称为该生成树的代价，在G的所有生成树中，代价最小的生成树称为最小生成树(minimal spanning tree)

普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法是两个利用MST性质构造最小生成树的经典算法。

MST性质

最小生成树具有MST性质:假设G=(V,E)是一个无向连通图，U是顶点集V的一个非空子集。若(u,v)是一条具有最小权值的边，其中u∈U，v∈V-U,则必存在一颗包含边(u,v)的最小生成树。

Prim算法

Prim算法的基本思想是:设G = (V,E)是一个无项联通网，令T = (U,TE)是G的最小生成树。T的初始状态为U={v₀},(v₀∈V)，TE={ },然后重复执行下述操作：在所有的u∈U，v∈V-U的边中找一条代价最小的边(u,v)并入集合TE,同时v并入U,直至U=V为止。此时TE中必有n-1条边，则T就是一颗最小生成树。Prim算法的基本思想伪代码如下:

1.初始化:U={ v₀};TE={ } ;
2.重复下述操作直到U=V：
     2.1 在E中寻找最短边(u,v),且满足u∈U,v∈V-U
     2.2 U = U +{ v }
     2.3 TE = TE +{ (u,v) }

设置一个数组shortEdge[n]表示候选最短边集，数组元素包括adjvex和lowcast两个域，分别表示候选最短边的邻接点和权值.

Prim算法用伪代码描述为:

1.初始化辅助数组shortEdge[n];
2.输出顶点v₀,将顶点0加入集合U中；
3.重复执行下列操作n-1次；
     3.1 在shortEdge[n].lowcast中选取最短边及对应的临界点编号k；
     3.2 输出顶点k和对应的权值；
     3.3 将顶点k加入集合U中；
     3.4 调整数组shortEdge[n];

Prim实现函数代码如下:

#include<bits/stdc++.h>
using namespace std;
#define inf 0x7fffffff//无穷大
#define maxn 5005
int cost[maxn][maxn],minn;
int n,m,v2[maxn],tot=1,now,ans;
bool v1[maxn];//v1为标记数组，v2为顶点到当前顶级的权值。
void getcost()
{
      scanf("%d%d",&n,&m);//读入点和边
      for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                  cost[i][j]=inf;//初始化，将全部边设为无穷大
      for(int i=1;i<=m;i++){
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);//读入起始点,目标点和位权
            if(cost[u][v]>w)//表示两个顶点是联通的.
                  cost[u][v]=cost[v][u]=w;//无向图只有一条路,双向
      }//初始化cost数组,v2表示起始点到个点的距离
      for(int i=1;i<=n;i++)
        v2[i]=cost[1][i];
    v1[1]=1;//找出与1节点相连的边并进行标记
}
int prim()
{
      while(tot<n)//最小生成树的概念,只用n-1条边就行
      {
            minn=inf;
            tot++;  //循环一个加一
            for(int i=1;i<=n;i++){
                  if(!v1[i]&&v2[i]<minn){
                        minn=v2[i];//最小值
                        now=i;//顶点编号
                  }
            }//找出与顶点联通且是最小边
            ans+=minn;//更新答案
            for(int i=1;i<=n;i++)
                  if(!v1[i]&&v2[i]>cost[now][i])//在没有标记的点中,找出一条
                        //自己到自己的距离为无穷大
                        v2[i]=cost[now][i];//更新与已知边的最短距离,不一定要1号顶点,
                        //此时v2不再表示1号顶点到个顶点的距离
            v1[now]=1;//在找出与now节点相连的边并进行标记
      }
      return ans;
}
int main()
{
      getcost();
      printf("%d",prim());
      return 0;
}

代码说明:
第一行包含两个整数N、M，表示该图共有N个结点和M条无向边。（N<=5000，M<=200000）
接下来M行每行包含三个整数Xi、Yi、Zi，表示有一条长度为Zi的无向边连接结点Xi、Yi.
输出包含一个数，即最小生成树的各边的长度之和；

输入数据
4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3

输出结果7

PS:题目来自于洛谷