**最小生成树（Minimum Spanning Tree，MST） **是在一个给定的 无向图 G(V, E) 中求一棵树，使得这棵树拥有 G 的所有顶点，且所有的边都来自 G，并且满足整棵树的 边权和最小。

最小生成树的性质：

MST 是棵树，因此 E = V - 1，且不存在环
MST 不唯一，但是最小边权和唯一
MST 的根结点可以是无向图上的任意一个结点

求解最小生成树的两个算法：Prim 和 Kruskal，其关键都在于贪心，但是贪心的策略不一样。

Prim

Prim 采用的是 点贪心 策略。

基本思想

选择任意节点为起始点，加入 点集合V，初始化 边集合E为空
选取 集合V中的点 到 剩余节点 的 最小权值边，加入E，然后把该边连接的节点加入V
重复以上步骤，直至 集合V包括所有的节点
所求的 {V，E} 就是最小生成树

可以看出 Prim 和 Dijkstra 的思想非常相同，仅仅使用了集合 V 代替了 Dijkstra 中的起点 S。

具体实现

Prim 需要两个关键概念的实现：点集合 V、顶点 u 到集合 V 的最短距离。

集合 V 可以直接使用一个 bool 数组 vis[] 来判断顶点是否已访问
dis[] 表示从集合 V 到达顶点 vi 的最短距离，初始化时除了起点 S 的 dis[S] = 0，其于顶点都赋为 INF（一个很大的数，可以是 0x3fffffff，防止 int 溢出)

伪代码

int Prim(G) {
	dis[], vis[]初始化;
    mst = 0;
	for (循环 n 次) {
        u = 使 dis[u] 最小且未访问过的顶点标号;
        记 u 已被访问;
        mst += d[u];
        for (u 的邻居 v) {
            if (v 未访问 && 以 u 为中介使得 d[v] 更优) {
                更新 d[v];
            }
        }
	}
    return mst;
}

时间复杂度：邻接矩阵 $O(V^2)$ $O (V^{2})$ ，邻接表使用堆优化 $O(VlogV + E)$ $O (V l o g V + E)$
- 可以看出，稠密图（点少边多）使用 Prim

Kruskal

Kruskal 采用的是 边贪心 策略。

基本思路

新建图 {V,E}，V有原来图的所有顶点，而 E为空集，因而每个节点自成一个连通分量
在原图的边中选择权值最小的边
1. 若该边依附的顶点落在新建图中 不同的连通分量，则将此边加入E
2. 否则舍去此边，寻找下一条权值最小的边
以此类推，直至新建图 所有的节点在同一连通分量

具体实现

如何判断不同连通分量，以及合并不同分量？换个角度想，就是集合的查询与合并，因此可以使用并查集实现。

伪代码

int Kruskal() {
	MST 的边权和为 mst，当前边数 num;
    将所有的边排序;
    for (从小到大枚举边) {
        if (边的两个端点在不同的连通分量) {
            将边加入生成树;
            mst += 边的权值;
            num++;
            if (num == V - 1) break;
        }
    }
    return mst;
}

时间复杂度： $O(ElogE)$ $O (E l o g E)$
- 可以看出，稀疏图（点多边少）使用 Kruskal

C++

struct Edge {
    int u, v;
    int weight;

    friend bool operator<(const Edge& a, const Edge& b) {
        return a.weight < b.weight;
    }
} E[MAXE];

int father[maxn];
int find(int x) {
    int a = x;
    while (x != father[x]) x = father[x];
    while (a != father[x]) {
        int z = a;
        a = father[a];
        father[z] = x;
    }
    return x;
}

// 图的顶点数 n，图的边数 m
int Kruskal(int n, int m) {
    int mst = 0, num = 0;
    for (int i = 0; i < n; i++) father[i] = i;
    sort(E, E + m);
    for (int i = 0; i < m; ++i) {
        int faU = find(E[i].u), faV = find(E[i].v);
        if (faU != faV) {
            father[faU] = faV;
            mst += E[i].weight;
            num++;
            if (num == n - 1) return mst;
        }
    }
    return -1;
}