ch10 课堂参考代码

ch10 最小生成树

生成树：对于 n 个结点 m 条边的无向图 G，由全部 n 个结点和其中 n - 1 条边构成的无向连通子图称为 G 的一棵生成树。

• 如果图 G 原本就不连通，则不存在生成树，只存在生成森林。

最小生成树（Minimum Spanning Tree，MST）：对于带边权的无向图 G，边的权值之和最小的生成树称为 G 的最小生成树。

求解 MST 常用 Kruskal 算法或 Prim 算法，这两种算法都基于贪心法。

• Kruskal 算法时间复杂度 $O(m\log m)$ ，适用于稀疏图。
• Prim 算法时间复杂度 $O(n^2)$ ，适用于完全图或稠密图。

模板

prim

算法流程：选取任意一个结点作为树 T，然后贪心地选取离 T 最近的那个点，并把它和对应的边加到 T 中。不断进行这个操作，就可以得到一棵最小生成树 T。

const int inf = 0x3f3f3f3f;
const int maxn = 5010;
int cost[maxn][maxn];
// 是否在 T 中
bool used[maxn];
// 点 i 与 T 相连的最短边的权值
int d[maxn];
int n;

/*
标记一个点 d[u] = 0
循环地执行：
        不在 T 中的节点与 T 相连的最短的边，拥有该边的节点 u
        最小生成树权值加上这条边
        把 u 加入 T：维护 used, d
直到 n 个点全部加入 T 中
*/
long long prim() {
    memset(d, 0x3f, sizeof(d));
    d[1] = 0;  // 希望第一步加入点 1
    long long res = 0;
    for (int i = 1; i <= n; ++i) {
        int u = -1;
        for (int v = 1; v <= n; ++v) {
            // 选不在树 T 且与 T 相连的最短边
            if (!used[v] && (u == -1 || d[v] < d[u])) u = v;
        }
        if (d[u] == inf) return -1;
        // 把点 u 加入树 T
        res += d[u];
        used[u] = 1;
        for (int v = 1; v <= n; ++v) {
            if (!used[v]) d[v] = min(d[v], cost[u][v]);
        }
    }
    return res;
}

kruskal

算法流程：每次都从剩余的边中选出一条边权最小的，并且这条边的两个端点 u 和 v 属于两个不同的连通分量（即 u 和 v 不连通），则加入该边，连接两个连通分量。

const int maxn = 100010, maxm = 100010;
struct Edge {
    int u, v, w;
    bool operator<(const Edge &n) const { return w < n.w; }
}E[maxm];
int fa[maxn], n, m;
void init() {
    for (int i = 1; i <= n; i++) fa[i] = i;
}
int find(int x) {
    if (fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}
void merge(int x, int y) {
    int rx = find(x), ry = find(y);
    fa[ry] = rx;
}
long long kru() {
	sort(E, E + m); // 边权从小到大排序
    long long res = 0;
	int cnt = n; // 记录当前连通分量的个数
    for (int i = 0; i < m; ++i) {
        Edge e = E[i];
        if (find(e.u) != find(e.v)) {
			merge(e.u, e.v);
        	--cnt, res += e.w;
		}
    }
    if (cnt > 1) return -1; // 不连通
    return res;
}
int main() {
	cin >> n >> m;
	for (int i = 0; i < m; ++i) {
		cin >> E[i].u >> E[i].v >> E[i].w;
	}
	init();
	cout << kru() << endl;
	return 0;
}

注意并查集只是维护结点的连通情况，不代表最终的 MST。如果需要将 MST 储存起来方便后面遍历这棵 MST，可以用 vector 数组（邻接表）将加入的边 e[i] 储存。

// 有边权的情况，需要储存出边的终点v和边权w
struct Edge2{
    int v, w;
};
vector<Edge2> G[N]; // G[u]储存结点u的所有出边信息（终点v和边权w）

// 选中e[i]这条边加入时，执行
G[e[i].u].push_back({e[i].v, e[i].w});
G[e[i].v].push_back({e[i].u, e[i].w});

瓶颈生成树

• 指最大的边权值最小的生成树。

• 与最小生成树的区别

  • 最小生成树目标是希望所有边权加起来最小。
  • 瓶颈生成树目标是希望边权最大的那条边权值尽量小。如果把边权理解为边的长度，就是希望最长的那条边尽量短。

• 性质： 最小生成树一定是瓶颈生成树，而瓶颈生成树不一定是最小生成树。

  反证法证明：

  设最小生成树中的最大边权为 w，如果最小生成树不是瓶颈生成树的话，则瓶颈生成树的所有边权都小于 w。

  只需删去原最小生成树中的最长边，用瓶颈生成树中的一条边来连接删去边后形成的两棵树，得到的新生成树一定比原最小生成树的权值和还要小，这样就产生了矛盾。