最小生成树 Minimum Spanning Tree

# 最小生成树 Minimum Spanning Tree

加权无向图的最小生成树（Minimum Spanning Tree，简称 MST）是一棵生成树，其权（所有边的权值之和）不会大于其它任何生成树的权。

一个带权连通图 G（假定每条边上的权值均大于零）可能有多棵生成树.
每棵生成树中所有边上的权值之和可能不同。
其中边上的权值之和最小的生成树称为图的最小生成树。

MST 算法有很多，但其中最知名的是 Prim 算法和 Kruskal 算法

从任何一个顶点开始作一棵单顶点 MST，再为之增加 V-1 条边，每次增加的边都是将 MST 上的一个顶点和尚未在此 MST 上的一个顶点相连接的最小边。

假设 G=(V，E) 是一个具有 n 个顶点的带权连通图，T=(U，TE) 是 G 的最小生成树，其中 U 是 T 的顶点集，TE 是 T 的边集，则由 G 构造从起始点 v 出发的最小生成树 T 的步骤如下：

初始化 U={v}。以 v 到其他顶点的所有边为候选边。
重复以下步骤 n-1 次，使得其他 n-1 个顶点被加入到 U 中：
1. 从候选边中挑选权值最小的边加入 TE（所有候选边一定是连接两个顶点集 U 和 V-U 的边），设该边在 V-U 中的顶点是 k，将顶点 k 加入 U 中。
2. 考察当前 V-U 中的所有顶点 j，修改候选边：若 (k，j) 的权值小于原来和顶点 j 关联的候选边，则用 (k，j) 取代后者作为候选边。

寻找最小边在这里使用小根堆

	struct Edge {
	int from, to, cost;
	Edge(int u, int v, int w):from(u), to(v), cost(w) {}
	};
	struct HeapNode {
	int d, u; //d 表示点 u 到 MST 的距离
	bool operator< (const HeapNode& rhs) const {
	return d > rhs.d; // 小根堆
	}
	};
	vector<Edge> edges; //edges 存所有边
	vector<int> G[MAXN]; // G [i] 是顶点 i 发出的所有边
	bool done[MAXN]; //i 是否已经加入了 MST
	int d[MAXN]; // 每个点到 MST 的最小距离
	int Prim() {
	priority_queue<HeapNode> Q;
	int ans = 0; // 总权值
	for (int i = 0; i < V; ++i) d[i] = INF; // V 是图的节点数
	d[0] = 0; // 从点 0 开始
	memset(done, 0, sizeof(done));
	Q.push((HeapNode){0, 0});
	while (!Q.empty()) {
	HeapNode x = Q.top(); Q.pop;
	int u = x.u; //u 为队头元素的序号
	if (done[u]) continue; // 已经在 MST 中就跳过
	ans += x.d; // 加上出队的队头元素到 MST 的距离
	done[u] = true;
	for (int i = 0; i < G[u].size; ++i) { // 更新最小生成树的权值
	Edge& e = edges[G[u][i]]; // 顶点 to 能修改最小距离
	if (d[e.to] > e.cost) {
	d[e.to] = e.cost;
	Q.push((HeapNode){d[e.to], e.to});
	}
	}
	}
	return ans;
	}

本段代码用邻接表来存图，输入可以使用

Prim 时间复杂度为 $O(VlogV + ElogV)$ 。在稀疏图的情况下，E 的数量通常远小于 $V^2$ ，因此可以将时间复杂度近似为 $O(ElogV)$ 。而在稠密图的情况下，E 的数量接近 $V^2$ ，时间复杂度会接近 $O(V^2logV)$ 。

以边的长度（从小到大）为顺序来处理，若一条边与前面加入到 MST 中的边未形成环，则将这样的边加入到 MST 中，增加了 V-1 条边后停止。也就是说开始是一个森林，每个顶点就是一棵独立的树，然后逐渐把这些树合并（通过一条最小边），最后形成的一棵树就是 MST。

假设 G=(V，E) 是一个具有 n 个顶点的带权连通图，T=(U，TE) 是 G 的最小生成树，则构造最小生成树的步骤如下：

如果把一棵树看成一个集合，那么对于新加入的边，要判断它的两个顶点是否已经在同一个集合了？是的话就跳过，处理下一条边；不是的话就把这条边加入到 MST，同时把该边两顶点所处的两个集合合并。这个实际就是不相交集合（Disjoint Set）的并查 (Union-Find) 操作。

	struct edge {
	int u, v, cost;
	};

	bool cmp(const edge& e1, const edge& e2) {
	return e1.cost < e2.cost;
	}

	edge es[MAX_E]; // 存储边的信息
	int par[MAX_V]; // 存储父节点

	// 初始化并查集
	void init_union_find(int V) {
	for (int i = 0; i < V; ++i) {
	par[i] = i; // 初始时每个节点的父节点是自身
	}
	}

	// 查找根节点
	int find(int x) {
	if (par[x] == x) {
	return x; // 根节点的父节点是自身
	} else {
	return par[x] = find(par[x]); // 路径压缩，将 x 的父节点设为根节点，加速后续查找
	}
	}

	// 合并集合
	void unite(int x, int y) {
	x = find(x); // 查找 x 的根节点
	y = find(y); // 查找 y 的根节点
	if (x != y) {
	par[x] = y; // 将 x 的根节点设为 y，合并两个集合
	}
	}

	// 判断两个节点是否属于同一个集合
	bool same(int x, int y) {
	return find(x) == find(y); // 若两个节点的根节点相同，则属于同一个集合
	}

	int Kruskal(int V, int E) {
	sort(es, es + E, cmp); // 按权值从小到大排序
	init_union_find(V); // 并查集初始化
	int res = 0;
	for (int i = 0; i < E; ++i) {
	edge e = es[i];
	if (!same(e.u, e.v)) { //u 和 v 不属于一个集合
	unite(e.u, e.v); // 合并 u 和 v 集合的元素
	res += e.cost;
	}
	}
	return res;
	}

Kruskal 算法的时间复杂度为 $O(ElogE + Eα(V))$ 。在稀疏图的情况下，E 的数量通常远小于 $V^2$ ，因此可以将时间复杂度近似为 $O(ElogE)$ 。而在稠密图的情况下，E 的数量接近 $V^2$ ，时间复杂度会接近 $O(Eα(V))$ 。