浅谈Prim（Cpp）

· · 个人记录

一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。最小生成树可以用kruskal（克鲁斯卡尔）算法或Prim（普里姆）算法求出。

本蒟蒻只会Prim，今日浅谈。

什么是最小生成树？

现在假设有一个很实际的问题：我们要在n个城市中建立一个通信网络，则连通这n个城市需要布置n-1一条通信线路，这个时候我们需要考虑如何在成本最低的情况下建立这个通信网？

于是我们就可以引入连通图来解决我们遇到的问题，n个城市就是图上的n个顶点，然后，边表示两个城市的通信线路，每条边上的权重就是我们搭建这条线路所需要的成本，所以现在我们有n个顶点的连通网可以建立不同的生成树，每一颗生成树都可以作为一个通信网，当我们构造这个连通网所花的成本最小时，搭建该连通网的生成树，就称为最小生成树。

构造最小生成树有很多算法，但是他们都是利用了最小生成树的同一种性质：MST性质（假设N=(V,{E})是一个连通网，U是顶点集V的一个非空子集，如果（u，v）是一条具有最小权值的边，其中u属于U，v属于V-U，则必定存在一颗包含边（u，v）的最小生成树），下面就介绍使用MST性质生成最小生成树的算法：普里姆算法。

算法思路：

1).输入：一个加权连通图，其中顶点集合为V，边集合为E；

2).初始化：Vnew = {x}，其中x为集合V中的任一节点（起始点），Enew = {},为空；

3).重复下列操作，直到Vnew = V：

a.在集合E中选取权值最小的边<u, v>，其中u为集合Vnew中的元素，而v不在Vnew集合当中，并且v∈V（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；

b.将v加入集合Vnew中，将<u, v>边加入集合Enew中；

4).输出：使用集合Vnew和Enew来描述所得到的最小生成树。

不多说，上代码：

const int MAXN=1010;
const int INF=100000000;
int G[MAXN][MAXN];
bool used[MAXN];
int mincost[MAXN];
int n;
int prim() {
    for (int i=1; i<=n; i++) {
        mincost[i]=INF;
        used[i]=false;
    }
    mincost[1]=0;
    int ret=0;
    while (true) {
        int v=-1;
        for (int i=1; i<=n; i++) {
            if (!used[i] && (v==-1 || mincost[i]<mincost[v])) v=i;
        }
        if (v==-1) break;
        used[v]=true;
        ret+=mincost[v];
        for (int i=1; i<=n; i++) {
            mincost[i]=min(mincost[i],G[v][i]);
        }
    }
    return ret;
}

感谢奆佬，看完本蒟蒻丑陋的代码！