最小生成树

1 简介

给定一个无向图，如果它任意两个顶点都联通并且是一棵树，那么我们就称之为生成树(Spanning Tree)。如果是带权值的无向图，那么权值之和最小的生成树，我们就称之为最小生成树(MST, Minimum Spanning Tree)。

常见求解最小生成树的算法有Kruskal算法和Prim算法，两者都是运用贪心的思路。两者区别：Prim在稠密图中比Kruskal优，在稀疏图(一般我们认为满足$E < V*(V-1)/4$)中比Kruskal劣；Prim是以更新过的节点的连边找最小值，Kruskal是直接将边排序。

注意：

1. 最小生成树可能有多个，但边的权值之和总是唯一且最小的
2. 最小生成树的边数=顶点数-1。砍掉一条则不连通，增加一条边则会出现回路
3. 如果一个连通图本身就是一棵树，则其最小生成树就是它本身
4. 只有连通图才有生成树，非连通图只有生成森林

2 Kruskal算法

Kruskal算法是基于贪心的思想得到的。首先我们把所有的边按照权值先从小到大排列，接着按照顺序选取每条边，如果这条边的两个端点不属于同一集合（两点是否连通），那么就将它们合并，直到所有的点都属于同一个集合为止（所有结点连通）。

时间复杂度：Kruskal算法每次要从都要从剩余的边中选取一个最小的边。通常我们要先对边按权值从小到大排序，这一步的时间复杂度为$O(ElogE)$。Kruskal算法的实现通常使用并查集，来快速判断两个顶点是否属于同一个集合。最坏的情况可能要枚举完所有的边，此时要循环$E$次，所以这一步的时间复杂度为O(E*α(V))，其中α为Ackermann函数，其增长非常慢，我们可以视为常数。所以Kruskal算法的时间复杂度为$O(ElogE)$。

• 参考：https://blog.csdn.net/luomingjun12315/article/details/47700237/

const int maxn = 1e5 + 5;
const int maxv = 5e5 + 5;
const int inf = 0x7fffffff;
int n, v;       // n是点数，v是边数

struct Edge {// 存储边
    int a, b, w;

    bool operator< (const Edge &W)const {
        return w < W.w;
    }
}edges[maxv];

int node[maxn];//并查集的父节点数组
int Rank[maxn];//树的高度

//初始化
void init(int n) {
    for (int i=0; i<=n; i++) {
        node[i] = i;
        Rank[i] = 1;
    }
}
//路径压缩
//查找当前元素所在树的根节点(代表元素)
int find(int x) {
    if (x == node[x])
        return x;
    return node[x] = find(node[x]);//在第一次查找时，将节点直连到根节点
}
//按秩合并
//合并x和y所在的集合
void merge(int x, int y) {
    int root_x = find(x);//找到根节点
    int root_y = find(y);
    if (root_x == root_y)//两者根节点相同
        return ;
    //判断两棵树的高度，然后在决定谁为子树
    if (Rank[root_x] < Rank[root_y])
        node[root_x] = root_y;//将x的根节点接到y的根节点下
    else {
        node[root_y] = root_x;//将y的根节点与x的根节点下
        if (Rank[root_x] == Rank[root_y])//树的高度相同
            Rank[root_x]++;//root_x树高度+1
    }
}
//判断xy是否属于一个集合
bool same(int x, int y) {
    return find(x) == find(y);
}

int kruskal() {
    sort(edges, edges + v);

    init(n);  // 初始化并查集

    int res = 0, cnt = 0;
    for (int i = 0; i < v; i ++ ) {
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;

        a = find(a), b = find(b);
        if (a != b) {// 如果两个连通块不连通，
            merge(a, b);//则将这两个连通块合并
            res += w;
            cnt ++ ;
        }
    }

    if (cnt < n - 1) return inf;//原图不连通 
    return res;
}

3 Prim算法

思想：

从某一个顶点开始构建生成树；每次将代价最小的新顶点纳入生成树，直到所有顶点都纳入为止。

时间复杂度：

最小边、权的数据结构	时间复杂度（总计）
邻接矩阵、搜索	$O(V^2)$
二叉堆、邻接表	$O((V + E) log(V)) = O(E log(V))$
斐波那契堆、邻接表	$O(E + V log(V))$

流程：

输入：一个加权连通图，其中顶点集合为$V$，边集合为$E$
输出：使用集合$Vnew$和$Enew$来描述所得到的最小生成树

从单一顶点开始，Prim算法按照以下步骤逐步扩大树中所含顶点的数目，直到遍及连通图的所有顶点。

1. 初始化：$Vnew = {x}$，其中$x$为集合$V$中的任一节点(起始点)，$Enew = \{\}$；
2. 重复下列操作，直到$Vnew = V$:
   1. 在集合$E$中选取权值最小的边$(u, v)$，其中$u$为集合$Vnew$中的元素，而$v$则是$V$中没有加入$Vnew$的顶点（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；
   2. 将$v$加入集合$Vnew$中，将$(u, v)$加入集合$Enew$中。

• 参考：https://blog.csdn.net/luomingjun12315/article/details/47859993

const int maxn = 105;
const int inf = 0x3f3f3f3f;

int n;      // n表示点数
int g[maxn][maxn]; // 邻接矩阵，存储所有边，编号从1开始 
int dist[maxn];    // 存储其他点到当前最小生成树的距离
bool st[maxn];     // 存储每个点是否已经在生成树中


// 如果图不连通，则返回INF(值是0x3f3f3f3f), 否则返回最小生成树的树边权重之和
int prim() {
    memset(dist, 0x3f, sizeof dist);

    int res = 0;
    for (int i = 0; i < n; i ++ ) {
    	//寻找代价最小的新顶点 
        int t = -1;
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
		//原图不连通 
        if (i && dist[t] == inf) return inf;
		//加点 
        if (i) res += dist[t];
        st[t] = true;
		//更新dist 
        for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]);
    }

    return res;
}

练习

1. 牛客——道路建设
2. 牛客——挖沟