生成树

首先，生成树是相对于连通图来说的。它是一个连通图的子图，而且没有环，也可以看成是一棵树。对于生成树，其所有结点的根节点都是同一个。
生成树有以下两个性质：

1. 生成树包含了图的所有结点
2. 生成树只包含图的最小数量的边

由于生成树包含了图的所有结点，且只包含最小数量的边。所有，对于一个顶点数为n的图，其生成树只包含n-1条边。

最小生成树

而最小生成树是相对于加权无向连通图的，加权即所有的边都有一个权重值，它可能代表了从结点u到结点v的代价或者成本。最小生成树是图的所有生成树中，边的权重之和最小的那个。
最小生成树对于路径规划、NP难问题的近似求解、图片分割、聚类分析都有重要的作用。
需要注意的是，最小生成树可能不唯一。在一个加权图中，如果存在权重相等的边，那么就有可能生成不同的最小生成树。但是如果每条边的权重都不同，那么生成的最小生成树就是唯一的。

MST算法

问题定义：
输入：加权无向连通图$G(V,E,W)$
输出：最小生成树$T(V,E^*,W*)$

求解策略：

1. 从一个空子图开始
2. 每次往子图添加一条边
3. 判断新的子图是否是某一最小生成树的一部分：
   1. 保证子图仍然是一棵树，没有环
   2. 边的权重足够小

Prim算法

对于图G，Tv是最小生成树的一部分结点，Sv是图中剩余结点，Sv=V-Tv。Prim算法通过不断选择Tv和Sv中两个边权重最小的结点u和v，将结点v和这条权重最小的边加入到最小生成树的结点中去。不断重复这个过程直到所有结点都加入到最小生成树中。

算法实现

算法对于输入中可能的重边，取重复边中权重最小的那条边：g[a][b] = g[b][a] = min(g[a][b], c);

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
// 创建矩阵
const int N = 5200,INF = 0x3f3f3f3f;
int vertexNum, edgeNum;

int g[N][N], dist[N];
bool st[N];
int prim() {
     // dist进行填充
    memset(dist, 0x3f, sizeof dist);
    cout << sizeof dist << endl;
    dist[1] = 0;
    int res = 0;
    // 寻找最短的边且不够成环, 即寻找未加入的且最小权值的边
    for (int i = 1; i <= vertexNum; i++) {
        int t = -1;
        for (int j = 1; j <= vertexNum; j++)
            if (!st[j] && (t == -1 || dist[j] < dist[t])) //找到一个未访问过的顶点，并且其权值最小
                t = j;
        if (dist[t] == INF) return -1;
        //表示此边加入最小生成树中，状态改为true
        st[t] = true;
        res += dist[t];
        //更新dist,更新顶点t到其他顶点的距离，如果比dist
        for (int j = 1; j <= vertexNum; j++)
            if (!st[j] && dist[j] > g[t][j])
                dist[j] = g[t][j];
    }

    return res;
}

int main() {
    //将输入值赋予vertexNum与edgeNum，表示节点数与边
    cin >> vertexNum >> edgeNum;
    // 对邻接矩阵初始化，全部赋予极大值
    memset(g, 0x3f, sizeof g);
    //依次读入edgeNum个边
    while (edgeNum--) {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = g[b][a] = min(g[a][b], c);//可能会有重边，对于重边取权重最小的边
    }

    int res = prim();
    if (res == -1) cout << "orz" << endl;
    else cout << res << endl;

    return 0;
}

运行结果

算法分析

算法读取输入中边权重的时间复杂度为$O(E)$，生成N-1条边时，每次都需要遍历所有未加入生成树的顶点，时间复杂度为$O(V^{2)$。算法总时间复杂度为$O(E+V}2)=O(V^2)$。

最小堆优化

可以使用最小堆算法来优化查找最轻边的过程，将未加入生成树的各顶点到生成树中顶点的最短距离生成一个最小堆，每次选择最小堆的根结点加入生成树中即可，然后判断加入的结点和边是否会成环即可。
原始算法使用遍历来查找一个到生成树的边权重最小的顶点，时间复杂度为$O(V)$。而取最小堆根结点时间复杂度为$O(1)$, 调整最小堆时间复杂度为$O(\log V)$。对于结点较多的稠密图，可以缩短遍历顶点的运行时间。

Kruskal算法

Kruskal算法也是实现MST的一种算法，他通过对边按照权重进行排序，不断将权重最小的边加入到生成树中。对将要加入的边进行判断，其是否会使生成树有环。如果判断结果为是则丢弃该边，并重新寻找另一条权重最小的边。

使用并查集优化

可以使用并查集算法优化寻找当前结点的根结点的过程，来判断将要加入的边是否会使最小生成树成环。其算法思路如下：

1. 对于每一个将要加入最小生成树的边，需要找该边的两个结点点的根结点。如果一样，说明已经连通，不能连接，否则说明可以加入最小生成树。
2. 对于每条加入最小生成树的结点，都设置已经在生成树顶点集合U中的顶点为父结点。如果两个点都是第一次进集合，那么随机取一个结点为父结点。
3. 对于每一次成功的连接，如果是两个家族（多条边和顶点）连接在一起，那么其中一个家族的根结点，认另外一个家族的根结点为父结点。

可见，只要根结点相同，连接起来一定成环。通过并查集算法可以简化最小生成树算法中，加入的边是否会使生成树成环的过程。

算法实现

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 5200,INF = 0x3f3f3f3f;


struct edge{
    int x,y,v; //x,y存储边的两个端点 v存储边的长度
};

struct edge edges[200005];
int n,m,weight;
int pred[5005]; //并查集操作中存储顶点i的父亲顶点pred[i]

void quicksort(int l, int r){ //快速排序，将存边的数组按边值升序排序
    int i,j,m,temp;
    i = l;
    j = r;
    m = edges[(l+r) / 2].v;
    while (i <= j){
        while (edges[i].v < m)
            i++;
        while (edges[j].v > m)
            j--;
        if (i <= j){
            edge temp=edges[i];
            edges[i]=edges[j];
            edges[j]=temp;
            i++;
            j--;
        }
    }
    if (l < j)
        quicksort(l, j);
    if (i < r)
        quicksort(i, r);
}

int search(int x){ //并查集中的寻找根顶点的操作
    if (pred[x] == x)
        return x;
    else
        return pred[x] = search(pred[x]); //一种路径压缩的手段
}

int main(){
    weight = 0;
    int n,m;
    cin >> n >> m;
    for (int i = 0; i < m; i++){
        cin >> edges[i].x >> edges[i].y >> edges[i].v; //读入边集,这里不对重边进行特殊处理
    }
    quicksort(0, m-1); //对边进行排序
    for (int i = 1; i <= n; i++)
        pred[i] = i; //对父亲顶点数组进行初始化
    for (int i = 0; i < m; i++){
        if (search(edges[i].x) == search(edges[i].y))//搜索该边的两个顶点的祖父顶点，判断是否相同
            continue; //如果该边的两个顶点已经在生成树中，则舍去这条边
        pred[search(edges[i].x)] = search(edges[i].y); //否则将这条边加入生成树（运用并查集的合并集合操作）
        weight = weight + edges[i].v; //记录最小生成树的长度
    }
    int dup=0;
    for (int i = 1; i <= n; i++)
        if(pred[i] == i)dup++; //判断祖先顶点是他本身的顶点个数
    if(dup>1){         //如果祖先顶点是他本身的顶点数大于1，说明有顶点未加入生成树，不是连通图
        cout << "orz" << endl;
        return 0;
    }
    cout << weight << endl;
    return 0;
}

运行结果：

总结

由于Kruksal算法是对边进行操作，先取出边，然后判断边的两个节点，这样的话，如果一个图结构非常的稠密，那么Kruksal算法就比较慢了，而Prim算法只是对节点进行遍历，并使用set进行标记，因此会相对于Kruksal算法，在稠密图方面好很多。因此Kruksal算法常用于稀疏图，而Prim算法常用于稠密图。