【解雨臣的算法课】插播课：Kruskal 生成树与同构树——把分散的机关连成一体
“墓里的机关，单个看没什么，连起来就是杀阵。你得知道怎么把它们连起来最省力，还得认出来是不是同一个机关阵。”
——解雨臣
一、前言
胖子：“不是说好讲最短路吗？怎么插进来个生成树？”
我：“因为你昨天在墓里乱踩机关，把地板踩塌了。要是你懂最小生成树，就知道怎么走最安全。”
黑瞎子：“那同构树呢？”
我：“黑爷，你上次把两个墓室的机关阵认反了，差点放出血尸。”
两人：“……学，我们学！”
这节课临时插播，讲两个重要的树相关算法：
- Kruskal 最小生成树：怎么用最少的代价把所有机关连起来
- 树的同构：怎么判断两个机关阵是不是同一个
二、什么是生成树？
2.1 基本概念
生成树：在一个无向连通图中，取 n-1 条边，使得所有 n 个点连通，且没有环。
最小生成树（MST）：边权之和最小的生成树。
原图（5个点，7条边） 最小生成树（4条边，总权值最小）
1 3 1 3
/ \ / \ / \ /
2---4---5 6 2---4---5
\ / \
7 7
2.2 为什么需要最小生成树？
| 场景 | 应用 |
|---|---|
| 铺设电缆 | 用最少的线连接所有村庄 |
| 修路 | 用最短的路连通所有城市 |
| 机关阵 | 用最少的能量连接所有机关 |
三、Kruskal 算法
3.1 算法思想
解雨臣说：“Kruskal 就像相亲——每次都选最合适的，直到所有人都配对。”
贪心策略：
- 把所有边按权值从小到大排序
- 从小到大依次考虑每条边
- 如果这条边连接的两个点还没有连通，就选它
- 如果已经连通，就跳过（否则会形成环）
关键：如何快速判断两个点是否连通？
→ 并查集！
3.2 并查集复习
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int n;
int fa[N];
void init ()
{
for (int i = 1; i <= n; i++)
{
fa[i] = i;
}
}
int find (int x)
{
if (fa[x] != x)
{
fa[x] = find (fa[x]);
}
return fa[x];
}
void unite (int x, int y)
{
int rx = find (x);
int ry = find (y);
if (rx != ry)
{
fa[rx] = ry;
}
}
3.3 Kruskal 代码实现
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
const int M = 200010;
int n;
int m;
int fa[N];
struct Edge
{
int u;
int v;
int w;
} e[M];
bool cmp (Edge a, Edge b)
{
return a.w < b.w;
}
int find (int x)
{
if (fa[x] != x)
{
fa[x] = find (fa[x]);
}
return fa[x];
}
int main ()
{
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
cin >> e[i].u >> e[i].v >> e[i].w;
}
sort (e + 1, e + m + 1, cmp);
for (int i = 1; i <= n; i++)
{
fa[i] = i;
}
int ans = 0;
int cnt = 0;
for (int i = 1; i <= m; i++)
{
int u = e[i].u;
int v = e[i].v;
int w = e[i].w;
if (find (u) != find (v))
{
fa[find (u)] = find (v);
ans += w;
cnt++;
}
}
if (cnt == n - 1)
{
cout << ans << endl;
}
else
{
cout << "orz" << endl;
}
return 0;
}
3.4 复杂度分析
- 排序：O(m \log m)
- 并查集操作：O(m \alpha(n))，近似 O(m)
- 总复杂度：O(m \log m)
四、经典例题：解雨臣铺电缆
题目背景
解家要在 n 个墓室之间铺设电缆，每个墓室是一个点。
已知 m 条可能的线路，每条线路有造价 w_i。
问：用最少的钱把所有墓室连通，最少需要多少钱？
故事版
胖子：“这不就是修路吗？我选最便宜的线路！”
我：“你选最便宜的，万一形成环了呢？”
胖子：“啥是环？”
我：“就是……你从A到B再到C再回到A，兜了一圈，浪费钱。”
黑瞎子：“Kruskal 就是专门治你这个毛病的。”
代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1005;
const int M = 10005;
int n;
int m;
int fa[N];
struct Edge
{
int u;
int v;
int w;
} e[M];
bool cmp (Edge a, Edge b)
{
return a.w < b.w;
}
int find (int x)
{
if (fa[x] != x)
{
fa[x] = find (fa[x]);
}
return fa[x];
}
int main ()
{
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
cin >> e[i].u >> e[i].v >> e[i].w;
}
sort (e + 1, e + m + 1, cmp);
for (int i = 1; i <= n; i++)
{
fa[i] = i;
}
int ans = 0;
int cnt = 0;
for (int i = 1; i <= m; i++)
{
int u = e[i].u;
int v = e[i].v;
int w = e[i].w;
if (find (u) != find (v))
{
fa[find (u)] = find (v);
ans += w;
cnt++;
}
}
if (cnt == n - 1)
{
cout << ans << endl;
}
else
{
cout << "不可能连通" << endl;
}
return 0;
}
五、什么是树的同构？
5.1 问题引入
我：“胖子，你记不记得上次我们进的墓室，机关阵长什么样？”
胖子：“记得！中间一个大的，周围一圈小的。”
我：“那这次这个呢？”
胖子：“也是中间一个大的，周围一圈小的啊！”
我：“那它们是不是同一个机关阵？”
胖子：“这……长得像就是吧？”
问题：两个树，形状看起来一样吗？
定义：如果两棵树可以通过重新标记节点变成完全一样，就称它们是同构的。
5.2 例子
树A： 树B：
1 5
/ \ / \
2 3 6 7
/ \ / \
4 5 8 9
这两棵树是同构的（结构一样，只是编号不同）
树C： 树D：
1 1
/ \ / \
2 3 2 3
/ \ / \
4 5 4 5
/ \
6 6
这两棵树不同构（一个在左边多一层，一个在右边）
六、树的同构判定——树哈希
6.1 算法思想
解雨臣说：“给每个节点算一个‘指纹’，如果两棵树根节点的指纹一样，就是同构的。”
核心：给树分配一个哈希值，同构的树哈希值相同。
6.2 哈希公式
对于节点 u，设它的子节点为 v_1, v_2, \ldots, v_k，子节点的哈希值为 h(v_i)。
常用的哈希公式：
$$h(u) = 1 + \sum_{i=1}^k \text{hash}(h(v_i))$$
其中 \text{hash}(x) 是一个顺序无关的函数，比如：
$$h(u) = 1 + \sum_{i=1}^k p^{h(v_i)} \quad \text{或} \quad h(u) = \prod_{i=1}^k (p + h(v_i))$$
为了与顺序无关，我们通常：
- 对子节点的哈希值排序
- 然后按顺序组合
6.3 树哈希代码
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
const int MOD = 1e9 + 7;
const int P = 131;
int n;
vector <int> g[N];
int dfs (int u, int fa)
{
vector <int> ch;
for (int v : g[u])
{
if (v == fa)
{
continue;
}
ch.push_back (dfs (v, u));
}
sort (ch.begin (), ch.end ());
int h = 1;
for (int x : ch)
{
h = (1LL * h * P + x) % MOD;
}
return h;
}
int main ()
{
cin >> n;
for (int i = 1; i < n; i++)
{
int u;
int v;
cin >> u >> v;
g[u].push_back (v);
g[v].push_back (u);
}
int root = 1;
int h = dfs (root, 0);
cout << h << endl;
return 0;
}
6.4 无根树的同构
对于无根树，我们需要考虑所有可能的根。
方法一：找到树的重心（最多两个），以重心为根计算哈希。
方法二：用AHU算法——对树进行规范化编码。
6.5 找重心
int n;
int sz[N];
int mx[N];
int root;
vector <int> g[N];
void dfs_size (int u, int fa)
{
sz[u] = 1;
mx[u] = 0;
for (int v : g[u])
{
if (v == fa)
{
continue;
}
dfs_size (v, u);
sz[u] += sz[v];
mx[u] = max (mx[u], sz[v]);
}
mx[u] = max (mx[u], n - sz[u]);
if (mx[u] < mx[root])
{
root = u;
}
}
七、经典例题：解雨臣的机关阵
题目背景
解雨臣在两个墓室里各发现了一个机关阵，每个机关阵是一个树形结构（节点是机关，边是能量线）。
他想知道：这两个机关阵是不是同一个？（即是否同构）
代码实现
#include<bits/stdc++.h>
using namespace std;
const int N = 105;
const int MOD = 1e9 + 7;
const int P = 131;
int n1;
int n2;
vector <int> g1[N];
vector <int> g2[N];
int sz[N];
int mx[N];
int root;
void dfs_size (vector <int> g[], int u, int fa, int n)
{
sz[u] = 1;
mx[u] = 0;
for (int v : g[u])
{
if (v == fa)
{
continue;
}
dfs_size (g, v, u, n);
sz[u] += sz[v];
mx[u] = max (mx[u], sz[v]);
}
mx[u] = max (mx[u], n - sz[u]);
if (mx[u] < mx[root])
{
root = u;
}
}
int find_center (vector <int> g[], int n)
{
root = 1;
mx[0] = n;
dfs_size (g, 1, 0, n);
return root;
}
int dfs_hash (vector <int> g[], int u, int fa)
{
vector <int> ch;
for (int v : g[u])
{
if (v == fa)
{
continue;
}
ch.push_back (dfs_hash (g, v, u));
}
sort (ch.begin (), ch.end ());
int h = 1;
for (int x : ch)
{
h = (1LL * h * P + x) % MOD;
}
return h;
}
bool isomorphic ()
{
if (n1 != n2)
{
return false;
}
int r1 = find_center (g1, n1);
int r2 = find_center (g2, n2);
vector <int> h1;
vector <int> h2;
h1.push_back (dfs_hash (g1, r1, 0));
for (int v : g1[r1])
{
if (mx[v] == mx[r1])
{
h1.push_back (dfs_hash (g1, v, 0));
}
}
h2.push_back (dfs_hash (g2, r2, 0));
for (int v : g2[r2])
{
if (mx[v] == mx[r2])
{
h2.push_back (dfs_hash (g2, v, 0));
}
}
for (int a : h1)
{
for (int b : h2)
{
if (a == b)
{
return true;
}
}
}
return false;
}
int main ()
{
cin >> n1;
for (int i = 1; i < n1; i++)
{
int u;
int v;
cin >> u >> v;
g1[u].push_back (v);
g1[v].push_back (u);
}
cin >> n2;
for (int i = 1; i < n2; i++)
{
int u;
int v;
cin >> u >> v;
g2[u].push_back (v);
g2[v].push_back (u);
}
if (isomorphic ())
{
cout << "同一个机关阵" << endl;
}
else
{
cout << "不同的机关阵" << endl;
}
return 0;
}
八、解雨臣踩过的坑
坑1：Kruskal 忘记判断连通性
if (cnt == n - 1)
{
// 连通
}
else
{
// 不连通，无法生成树
}
解家箴言：选完边后检查一下，cnt 是否等于 n-1。
坑2：并查集路径压缩写错
// 错误
int find (int x)
{
if (fa[x] != x)
{
return find (fa[x]);
}
return fa[x];
}
// 正确
int find (int x)
{
if (fa[x] != x)
{
fa[x] = find (fa[x]);
}
return fa[x];
}
解家箴言：路径压缩要赋值回去！
坑3：树哈希没排序
// 错误：直接按子节点顺序组合
int h = 1;
for (int v : g[u])
{
h = (h * P + dfs (v, u)) % MOD;
}
// 正确：排序后再组合
sort (ch.begin (), ch.end ());
for (int x : ch)
{
h = (h * P + x) % MOD;
}
解家箴言：顺序不影响同构，所以要排序。
坑4：无根树只考虑一个根
// 错误：只以1为根
int h1 = dfs_hash (g1, 1, 0);
int h2 = dfs_hash (g2, 1, 0);
// 正确：考虑重心
int r1 = find_center (g1, n1);
int r2 = find_center (g2, n2);
解家箴言：无根树要以重心为根。
九、课后习题（解家的考验）
基础题
-
最小生成树模板：给定 n 个点 m 条边的无向图，求 MST 的权值和。
-
解雨臣的局域网：有 n 台电脑，m 条网线，每条网线有带宽。问用最少的网线把所有电脑连起来，最大带宽是多少？（提示：最大生成树）
进阶题
-
解雨臣的电缆升级：现有 n 个墓室已经用电缆连通了。现在要升级，每条电缆的升级费用不同。问升级后仍然连通，且费用最小的方案。
-
树的同构判定：给两棵树，判断它们是否同构。
挑战题
-
解雨臣的三棵机关树：给三棵树，判断它们是否两两同构。
-
解雨臣的森林：有 n 个墓室，m 条能量线（可能不连通）。现在要添加最少的能量线，使得所有墓室连通，并且添加的能量线总长度最小。问最小总长度是多少？
十、下集预告
“生成树是把分散的东西连起来，同构树是认出长得一样的东西。下节课我们讲最短路——怎么从起点最快到终点。”
——解雨臣
胖子：“那我下节课是不是就能找到出口了？”
我：“前提是你先别乱跑。”
黑瞎子：“他乱跑也没事，反正也跑不远。”
胖子：“……”
下节课：最短路算法——Dijkstra、Bellman-Ford、Floyd
下课。
（本系列课程由解雨臣独家赞助，信友队论坛首发。转载需注明出处。）
