OI-wiki 树同构判定AHU 算法原理、优化与 C 实现深度解析【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki本篇技术指南以 OI-wiki 图论板块的 tree-ahu.md 为骨架系统讲解基于括号序与节点命名的 AHU 树同构判定算法从有根树/无根树同构的严格定义出发介绍如何借助树的重心将无根树问题转化为有根树问题再到朴素的 $O(n^2)$ 括号序命名算法以及基于层次划分与层内排名将复杂度优化至 $O(n\log n)$配合基数排序可做到 $O(n)$的完整推导。读完本文你将掌握 AHU 算法的完整证明脉络、复杂度分析方法以及仓库中tree-ahu_1.cpp参考实现含重心求解、按层排名与子树标签比较的逐段运行原理可直接应用于判断两棵无根树是否同构的竞赛题目。AHU 算法以作者 Alfred Aho 与 John Hopcroft 命名用于判断两棵有根树是否同构。除 AHU 算法外判断树同构还有一种常见做法是树哈希二者在 OI/ICPC 竞赛中均有广泛应用。阅读本文建议具备树基础与树的重心的前置知识并配合文末例题给出的参考代码与实际样例运行验证。树同构的定义有根树同构对于两棵有根树 $T_1(V_1,E_1,r_1)$ 和 $T_2(V_2,E_2,r_2)$如果存在一个双射 $\varphi: V_1 \rightarrow V_2$使得$$ \forall u,v \in V_1,(u,v) \in E_1 \iff (\varphi(u),\varphi(v)) \in E_2 $$且$\varphi(r_1)r_2$ 成立那么称有根树 $T_1(V_1,E_1,r_1)$ 和 $T_2(V_2,E_2,r_2)$ 同构。无根树同构对于两棵无根树 $T_1(V_1,E_1)$ 和 $T_2(V_2,E_2)$如果存在一个双射 $\varphi: V_1 \rightarrow V_2$使得$$ \forall u,v \in V_1,(u,v) \in E_1 \iff (\varphi(u),\varphi(v)) \in E_2 $$成立那么称无根树 $T_1(V_1,E_1)$ 和 $T_2(V_2,E_2)$ 同构。简单地说就是如果能够通过把树 $T_1$ 的所有节点重新标号使得树 $T_1$ 和树 $T_2$完全相同那么称这两棵树同构。注意有根树同构比无根树同构多了一条约束根必须对应到根。问题的转化无根树 → 有根树无根树同构问题可以转化为有根树同构问题。具体方法如下对于无根树 $T_1(V_1, E_1)$ 和 $T_2(V_2,E_2)$先分别找出它们的所有重心。如果这两棵无根树重心数量不同那么这两棵树不同构。如果这两棵无根树重心数量都为 $1$分别记为 $c_1$ 和 $c_2$那么如果有根树 $T_1(V_1,E_1,c_1)$ 和有根树 $T_2(V_2,E_2,c_2)$ 同构则无根树 $T_1(V_1, E_1)$ 和 $T_2(V_2,E_2)$ 同构反之则不同构。如果这两棵无根树重心数量都为 $2$分别记为 $c_1,c_1$ 和 $c_2,c_2$那么如果有根树 $T_1(V_1,E_1,c_1)$ 和有根树 $T_2(V_2,E_2,c_2)$ 同构或者有根树 $T_1(V_1,E_1,c_1)$ 和有根树 $T_2(V_2,E_2,c_2)$ 同构则无根树 $T_1(V_1, E_1)$ 和 $T_2(V_2,E_2)$ 同构反之则不同构。所以只要解决了有根树同构问题就可以根据上述方法把无根树同构问题转化成有根树同构问题进而解决无根树同构问题。假设有一个可以 $O(|V|)$ 解决有根树同构问题的算法那么根据上述方法我们也可以在 $O(|V|)$ 的时间内解决无根树同构问题。上述转化的正确性依赖于树的重心的核心性质详见树的重心一棵树的重心如果不唯一则恰有两个且这两个重心相邻——重心为同构映射提供了唯一的锚点而同构映射必然把一棵树的重心映到另一棵树的重心。参考实现中的重心求解仓库参考实现 tree-ahu_1.cpp 中重心通过两次 DFS 求得void dfs_size(int u, int fa) { // 找到 size 值 sz[u] 1; maxv[u] 0; for (int i head[u]; i; i e[i].nxt) { int v e[i].v; if (v fa) continue; dfs_size(v, u); sz[u] sz[v]; maxv[u] max(maxv[u], sz[v]); } } void dfs_center(int rt, int u, int fa, int id) { maxv[u] max(maxv[u], sz[rt] - sz[u]); // 「向上」的那棵子树 if (Max maxv[u]) { center[id].clear(); Max maxv[u]; } if (Max maxv[u]) center[id].push_back(u); // 如果相等就 push_back for (int i head[u]; i; i e[i].nxt) { int v e[i].v; if (v fa) continue; dfs_center(rt, v, u, id); } }dfs_size统计以每个节点为根的子树大小dfs_center再遍历一次用sz[rt] - sz[u]补上「向上」子树的大小取所有连通分量最大值即节点的重量最小的节点作为重心。由于使用Max maxv[u]的判定并push_back当树有两个重心时会全部收集到center[id]数组中——这正是转化定理所要求的找出所有重心。随后treeIsomorphism()依据重心数量分情况调用rootedTreeIsomorphism完成判定见下文。朴素的 AHU 算法朴素的 AHU 算法是基于括号序的。原理 1括号序与树的唯一对应一段合法的括号序和一棵有根树唯一对应而且一棵树的括号序是由它的子树的括号序拼接而成的。如果我们通过改变子树括号序拼接的顺序从而获得了一段新的括号序那么新括号序对应的树和原括号序对应的树同构。例如一棵根节点带有两棵子树的树其括号序既可以写为(()())也可以写为(())()的拼接次序变化按子树顺序不同拼接得到的树结构是同构的。这是因为括号序只编码了嵌套层级这一结构信息与子树的排列次序无关。原理 2同构关系的传递性树的同构关系是传递的如果 $T_1$ 和 $T_2$ 同构$T_2$ 和 $T_3$ 同构那么 $T_1$ 和 $T_3$ 同构。这是因为同构映射双射可以复合两个同构映射的复合仍是同构映射。推论字典序最小拼接得到标准名考虑求树括号序的递归算法我们在回溯时拼接子树的括号序。如果在拼接的时候将字典序小的序列先拼接并将最后的结果记为 $NAME$。将以节点 $r$ 为根的子树的 $NAME$ 作为节点 $r$ 的 $NAME$记为 $NAME(r)$那么对于有根树 $T_1(V_1,E_1,r_1)$ 和 $T_2(V_2,E_2,r_2)$如果 $NAME(r_1)NAME(r_2)$那么 $T_1$ 和 $T_2$ 同构。该推论的依据是通过将每层的子树序列按字典序排序拼接两棵同构树经过这一规范化过程必然得到完全相同的括号序反之若规范化后的括号序不同则两树不同构否则它们会规约到同一个字典序最小的括号序由原理 2 的传递性导出矛盾。命名算法对每个节点自底向上递归赋予NAME伪代码如下??? note 实现 $$ \begin{array}{ll} 1 \textbf{Input. } \text{A rooted tree }T\ 2 \textbf{Output. } \text{The name of rooted tree }T\ 3 \text{ASSIGN-NAME(u)}\ 4 \qquad \text{if } u \text{ is a leaf}\ 5 \qquad \qquad \text{NAME(} u \text{) (0)}\ 6 \qquad \text{else }\ 7 \qquad \qquad \text{for all child } v \text{ of } u\ 8 \qquad \qquad \qquad \text{ASSIGN-NAME(}v\text{)}\ 9 \qquad \text{sort the names of the children of }u\ 10 \qquad \text{concatenate the names of all children }u\text{ to temp}\ 11 \qquad \text{NAME(} u \text{) (temp)} \end{array} $$其中叶子节点的名字约定为(0)内部节点的名字是把所有儿子名字排序后拼接再在外面套上一层括号( )。注意排序是关键步骤它消除了儿子间排列次序的差异使得同构子树得到相同的名字。AHU 算法在两棵有根树上分别运行ASSIGN-NAME比较根的名字即可??? note 实现 $$ \begin{array}{ll} 1 \textbf{Input. } \text{Two rooted trees }T_1(V_1,E_1,r_1)\text{ and }T_2(V_2,E_2,r_2) \ 2 \textbf{Output. } \text{Whether these two trees are isomorphic}\ 3 \text{AHU}(T_1(V_1,E_1,r_1), T_2(V_2,E_2,r_2))\ 4 \qquad \text{ASSIGN-NAME(}r_1\text{)}\ 5 \qquad \text{ASSIGN-NAME(}r_2\text{)}\ 6 \qquad \text{if NAME}(r_1) \text{NAME}(r_2)\ 7 \qquad \qquad \text{return true}\ 8 \qquad \text{else}\ 9 \qquad \qquad \text{return false} \end{array} $$复杂度证明对于一棵有 $n$ 个节点的有根树假设它是链状的那么节点名字长度最长可以是 $n$叶子名字长度为常数逐层向上套括号后根的括号序长度为 $O(n)$。此时ASSIGN-NAME算法的复杂度是 $12\cdotsn$ 的常数倍即 $\Theta(n^2)$。由此朴素 AHU 算法的复杂度为 $O(n^2)$。直观理解链状树每层只有一个儿子名字逐层累积变长各层拼接的总字符量呈等差数列增长最终达到平方量级。这是朴素算法的主要瓶颈。优化的 AHU 算法朴素 AHU 算法的缺点是树的 $NAME$ 长度可能会过长我们可以针对这一点做优化。原理 1按层次划分对树进行层次划分第 $i$ 层的节点到根的最短距离为 $i$。位于第 $i$ 层的节点的 $NAME$ 可以只由位于第 $i1$ 层的节点的 $NAME$ 拼接得到。这打破了朴素算法中名字长度逐层累积变长的链条优化算法中第 $i$ 层的名字只涉及下一层第 $i1$ 层的名字而不再包含更深层的全部信息。原理 2层内排名唯一标识在同一层内节点的 $NAME$ 可以由其在层内的排名唯一标识。注意这里的排名是对两棵树而言的假设节点 $u$ 位于第 $i$ 层那么节点 $u$ 的排名等于所有 $T_1$ 和 $T_2$ 第 $i$ 层的节点中 $NAME$ 比 $NAME(u)$ 小的节点的个数。也就是说把两棵树同一层的所有名字放在一起排序去重后分配连续的整数编号0、1、2、…相同名字获得相同编号——这个编号就完全取代了冗长的字符串名字。推论用整数和数组替代字符串我们可以将节点原来的 $NAME$ 用其在层内的排名代替然后把原来拼接节点 $NAME$ 用向数组加入元素代替。这样用整数和数组来代替字符串既不会影响算法的正确性又极大地降低了算法的复杂度。具体而言自底向上逐层处理对于第 $i$ 层的每个节点收集其所有儿子第 $i1$ 层节点的排名构成一个整数数组对应原来拼接得到的名字将这些数组排序、去重为每个不同的数组分配一个层内排名整数第 $i$ 层的节点即用该整数排名作为其新 $NAME$供上一层使用。最终比较两棵树根节点的排名或根节点儿子数组即可判定同构。复杂度证明首先注意到第 $i$ 层由拼接得到的 $NAME$ 的总长度为第 $i$ 层节点的度数之和即第 $i1$ 层的总点数以下用 $L_i$ 表示。算法的下一步会将这些 $NAME$ 看成字符串数组并排序然后将它们替换为其在层内的排名即重新映射为一个数。以下引理表明了对总长为 $L$ 的 $m$ 个字符串排序的复杂度我们可以使用基数排序在 $O(L|\Sigma|)$ 的时间内完成排序其中 $|\Sigma|$ 为字符集的大小。有一些实现细节参见参考资料我们可以使用快速排序在 $O(L\log m)$ 的时间内完成排序。证明的大致思路为快排递归树的高度为 $O(\log m)$且暴力比较长度为 $\ell_1$ 和 $\ell_2$ 的两个字符串的复杂度为 $O(\min{\ell_1,\ell_2})$。在 AHU 算法中第 $i$ 层字符串的字符集大小最多为第 $i1$ 层的点数即 $L_i$所以基数排序的复杂度是线性的。根据 $\sum_i L_iO(n)$各层点数总和恰为总节点数而层内名字总长不超过下一层点数并将每层的复杂度相加后可以看出若使用字符串的基数排序则算法的总复杂度为 $T(n)O(n)$同理如果使用快排排序字符串那么 $T(n)O(n\log n)$。这一结论的关键在于每层的总工作量与该层下一层的点数成正比各层累加后所有层的工作量之和为 $O(n)$或 $O(n\log n)$彻底避免了朴素算法中链状树名字长度平方级增长的问题。例题与参考实现解析例题SPOJ-TREEISO题意翻译给你两棵无根树判断两棵树是否同构。??? note 参考代码cpp --8-- docs/graph/code/tree-ahu/tree-ahu_1.cpp该参考代码位于 tree-ahu_1.cpp文件头注释明确写道Tree Isomorphism, O(nlogn)且将快速排序替换为基数排序可做到 $O(n)$与上文复杂度证明完全对应。仓库中还附带了对应的测试样例 tree-ahu_1.in 与期望输出 tree-ahu_1.ans第一组树输出YES第二组输出NO可用于直接验证实现正确性。下面结合源码分段解读其运行流程。数据结构与建图constexpr int N 1e5 5; constexpr int MAXN N 1; struct Edge { int v, nxt; } e[MAXN 1]; int head[MAXN], sz[MAXN], f[MAXN], maxv[MAXN], tag[MAXN], tot, Max; vectorint center[2], L[MAXN], subtree_tags[MAXN];由于要在一组数据中同时读入两棵树节点编号为 $1\sim n$ 的属于第一棵编号为 $n1\sim 2n$ 的属于第二棵见addedge(u n, v n)因此数组规模开到 $2n$。center[0]、center[1]分别保存两棵树的所有重心L[depth]按层存放节点即上文层次划分的直接实现subtree_tags[u]存放节点 $u$ 的所有儿子排名数组即优化算法中用向数组加入元素代替拼接tag[u]是节点 $u$ 最终获得的层内排名。按层处理与排名分配dfs_height完成分层并记录父亲int dfs_height(int u, int fa, int depth) { // 递归查找 height L[depth].push_back(u); f[u] fa; int h 0; for (int i head[u]; i; i e[i].nxt) { int v e[i].v; if (v fa) continue; h max(h, dfs_height(v, u, depth 1)); } return h 1; }最底层深度最大的叶子层的排名全部置为 $0$tag[L[h][j]] 0然后自底向上逐层处理for (int i h - 1; i 0; i--) { for (int j 0; j (int)L[i 1].size(); j) { int v L[i 1][j]; subtree_tags[f[v]].push_back(tag[v]); // 用儿子排名组成数组 } sort(L[i].begin(), L[i].end(), cmp); // 按子树标签数组排序 for (int j 0, cnt 0; j (int)L[i].size(); j) { if (j subtree_tags[L[i][j]] ! subtree_tags[L[i][j - 1]]) cnt; tag[L[i][j]] cnt; // 去重后分配层内排名 } }其中比较器cmp直接比较两个节点的subtree_tags数组字典序bool cmp(int u, int v) { return subtree_tags[u] subtree_tags[v]; }。这与优化算法原理 2完全一致——排名是相对两棵树全体节点计算的两棵树同层节点混在L[i]中一起排序去重后相等数组获得相同排名。有根树同构判定与总流程bool rootedTreeIsomorphism(int rt1, int rt2) { ... int h1 dfs_height(rt1, -1, 0); int h2 dfs_height(rt2, -1, 0); if (h1 ! h2) return false; // 高度不同必不同构 ... return subtree_tags[rt1] subtree_tags[rt2]; // 比较根的标签数组 }根的高度层数不同直接返回false否则逐层完成排名后比较两棵树根节点的subtree_tags数组是否相等。由于最外层还套了一层以根为父的虚拟层实际处理到i 0时根的儿子数组已经写入subtree_tags[rt]直接比较两个根数组即可覆盖整棵树的结构信息。bool treeIsomorphism() { if (center[0].size() center[1].size()) { // 重心数量必须相同 if (rootedTreeIsomorphism(center[0][0], center[1][0])) return true; if (center[0].size() 1) return rootedTreeIsomorphism(center[0][0], center[1][1]); // 两个重心时的交叉比较 } return false; }这对应问题的转化一节中三种情形的完整落地重心数量不同 → 直接返回false由center[0].size() center[1].size()判断失败进入return false重心数量都为 $1$ → 只比较(center[0][0], center[1][0])重心数量都为 $2$ → 比较(c_1, c_2)或(c_1, c_2)即center[0][0]与center[1][0]、center[1][1]的两次尝试只要有一次同构即为同构。main中先读入测试组数 $T$每组读入 $n$ 与两棵树的 $n-1$ 条边调用treeIsomorphism()后输出YES或NOint main() { cin.tie(nullptr)-sync_with_stdio(false); int T; cin T; while (T--) { cin n; init(n); cout (treeIsomorphism() ? YES : NO) \n; } return 0; }与树哈希方案的对比作为同主题的另一常见解法树哈希 将每棵子树编码为一个哈希值如 $f(S)\left(c\sum_{x\in S} g(x)\right)\bmod m$同样可以结合重心或换根 DP 判断无根树同构。与 AHU 算法的确定性精确比较不同树哈希基于概率判定存在被构造数据卡掉的风险虽然可以通过精心设计的哈希函数降低概率AHU 算法则给出确定性结果。二者各有适用场景在实际比赛中常互为验证手段。参考资料本文大部分内容译自 Paper 和 SlideAHU 算法原始论文与配套讲义参考材料中的证明更加全面和严谨本文做了一定的简化。对 AHU 算法的复杂度分析以及字符串的线性时间基数排序算法可以参见 The Design and Analysis of Computer Algorithms 的 3.2 节 Radix sorting 及其中 Example 3.2。仓库中与本文直接相关的可继续阅读资源包括参考实现tree-ahu_1.cpp测试样例tree-ahu_1.in、tree-ahu_1.ans前置知识树基础、树的重心姊妹方案树哈希【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考