本地源文件：docs/graph__tree-ahu.md

AHU 算法

AHU 算法用于判断两棵有根树是否同构．

判断树同构外还有一种常见的做法是树哈希．

前置知识：树基础，树的重心

建议配合参考资料里给的例子观看．

树同构的定义

有根树同构

对于两棵有根树 𝑇1(𝑉1,𝐸1,𝑟1)T1(V1,E1,r1) 和 𝑇2(𝑉2,𝐸2,𝑟2)T2(V2,E2,r2)，如果存在一个双射 𝜑 :𝑉1 →𝑉2φ:V1→V2，使得

∀𝑢,𝑣∈𝑉1,(𝑢,𝑣)∈𝐸1⟺(𝜑(𝑢),𝜑(𝑣))∈𝐸2∀u,v∈V1,(u,v)∈E1⟺(φ(u),φ(v))∈E2

且 𝜑(𝑟1) =𝑟2φ(r1)=r2 成立，那么称有根树 𝑇1(𝑉1,𝐸1,𝑟1)T1(V1,E1,r1) 和 𝑇2(𝑉2,𝐸2,𝑟2)T2(V2,E2,r2) 同构．

无根树同构

对于两棵无根树 𝑇1(𝑉1,𝐸1)T1(V1,E1) 和 𝑇2(𝑉2,𝐸2)T2(V2,E2)，如果存在一个双射 𝜑 :𝑉1 →𝑉2φ:V1→V2，使得

∀𝑢,𝑣∈𝑉1,(𝑢,𝑣)∈𝐸1⟺(𝜑(𝑢),𝜑(𝑣))∈𝐸2∀u,v∈V1,(u,v)∈E1⟺(φ(u),φ(v))∈E2

成立，那么称无根树 𝑇1(𝑉1,𝐸1)T1(V1,E1) 和 𝑇2(𝑉2,𝐸2)T2(V2,E2) 同构．

简单的说就是，如果能够通过把树 𝑇1T1 的所有节点重新标号，使得树 𝑇1T1 和树 𝑇2T2 完全相同 ，那么称这两棵树同构．

问题的转化

无根树同构问题可以转化为有根树同构问题．具体方法如下：

对于无根树 𝑇1(𝑉1,𝐸1)T1(V1,E1) 和 𝑇2(𝑉2,𝐸2)T2(V2,E2)，先分别找出它们的所有重心．

如果这两棵无根树重心数量不同，那么这两棵树不同构．
如果这两颗无根树重心数量都为 11，分别记为 𝑐1c1 和 𝑐2c2，那么如果有根树 𝑇1(𝑉1,𝐸1,𝑐1)T1(V1,E1,c1) 和有根树 𝑇2(𝑉2,𝐸2,𝑐2)T2(V2,E2,c2) 同构，那么无根树 𝑇1(𝑉1,𝐸1)T1(V1,E1) 和 𝑇2(𝑉2,𝐸2)T2(V2,E2) 同构，反之则不同构．
如果这两颗无根树重心数量都为 22，分别记为 𝑐1,𝑐′1c1,c1′ 和 𝑐2,𝑐′2c2,c2′，那么如果有根树 𝑇1(𝑉1,𝐸1,𝑐1)T1(V1,E1,c1) 和有根树 𝑇2(𝑉2,𝐸2,𝑐2)T2(V2,E2,c2) 同构或者有根树 𝑇1(𝑉1,𝐸1,𝑐′1)T1(V1,E1,c1′) 和 𝑇2(𝑉2,𝐸2,𝑐2)T2(V2,E2,c2) 同构，那么无根树 𝑇1(𝑉1,𝐸1)T1(V1,E1) 和 𝑇2(𝑉2,𝐸2)T2(V2,E2) 同构，反之则不同构．

所以，只要解决了有根树同构问题，我们就可以把无根树同构问题根据上述方法转化成有根树同构的问题，进而解决无根树同构的问题．

假设有一个可以 𝑂(|𝑉|)O(|V|) 解决有根树同构问题的算法，那么根据上述方法我们也可以在 𝑂(|𝑉|)O(|V|) 的时间内解决无根树同构问题．

朴素的 AHU 算法

朴素的 AHU 算法是基于括号序的．

原理 1

我们知道一段合法的括号序和一棵有根树唯一对应，而且一棵树的括号序是由它的子树的括号序拼接而成的．如果我们通过改变子树括号序拼接的顺序，从而获得了一段新的括号序，那么新括号序对应的树和原括号序对应的树同构．

原理 2

树的同构关系是传递的．既如果 𝑇1T1 和 𝑇2T2 同构，𝑇2T2 和 𝑇3T3 同构，那么 𝑇1T1 和 𝑇3T3 同构．

推论

考虑求树括号序的递归算法，我们在回溯时拼接子树的括号序．如果在拼接的时候将字典序小的序列先拼接，并将最后的结果记为 𝑁𝐴𝑀𝐸NAME．

将以节点 𝑟r 为根的子树的 𝑁𝐴𝑀𝐸NAME 作为节点 𝑟r 的 𝑁𝐴𝑀𝐸NAME，记为 𝑁𝐴𝑀𝐸(𝑟)NAME(r)，那么对于有根树 𝑇1(𝑉1,𝐸1,𝑟1)T1(V1,E1,r1) 和 𝑇2(𝑉2,𝐸2,𝑟2)T2(V2,E2,r2)，如果 𝑁𝐴𝑀𝐸(𝑟1) =𝑁𝐴𝑀𝐸(𝑟2)NAME(r1)=NAME(r2)，那么 𝑇1T1 和 𝑇2T2 同构．

命名算法

实现 1𝐈𝐧𝐩𝐮𝐭. A rooted tree 𝑇2𝐎𝐮𝐭𝐩𝐮𝐭. The name of rooted tree 𝑇3ASSIGN-NAME(u)4if 𝑢 is a leaf5NAME(𝑢) = (0)6else 7for all child 𝑣 of 𝑢8ASSIGN-NAME(𝑣)9sort the names of the children of 𝑢10concatenate the names of all children 𝑢 to temp11NAME(𝑢) = (temp)1Input. A rooted tree T2Output. The name of rooted tree T3ASSIGN-NAME(u)4if u is a leaf5NAME(u) = (0)6else 7for all child v of u8ASSIGN-NAME(v)9sort the names of the children of u10concatenate the names of all children u to temp11NAME(u) = (temp)

AHU 算法

实现 1𝐈𝐧𝐩𝐮𝐭. Two rooted trees 𝑇1(𝑉1,𝐸1,𝑟1) and 𝑇2(𝑉2,𝐸2,𝑟2)2𝐎𝐮𝐭𝐩𝐮𝐭. Whether these two trees are isomorphic3AHU(𝑇1(𝑉1,𝐸1,𝑟1),𝑇2(𝑉2,𝐸2,𝑟2))4ASSIGN-NAME(𝑟1)5ASSIGN-NAME(𝑟2)6if NAME(𝑟1)=NAME(𝑟2)7return true8else10return false1Input. Two rooted trees T1(V1,E1,r1) and T2(V2,E2,r2)2Output. Whether these two trees are isomorphic3AHU(T1(V1,E1,r1),T2(V2,E2,r2))4ASSIGN-NAME(r1)5ASSIGN-NAME(r2)6if NAME(r1)=NAME(r2)7return true8else10return false

复杂度证明

对于一颗有 𝑛n 个节点的有根树，假设他是链状的，那么节点名字长度最长可以是 𝑛n，那么 ASSIGN-NAME 算法的复杂度是 1 +2 +⋯ +𝑛1+2+⋯+n 的常数倍，即 Θ(𝑛2)Θ(n2)．由此，朴素 AHU 算法的复杂度为 𝑂(𝑛2)O(n2)．

优化的 AHU 算法

朴素的 AHU 算法的缺点是树的 𝑁𝐴𝑀𝐸NAME 的长度可能会过长，我们可以针对这一点做一些优化．

原理 1

对树进行层次划分，第 𝑖i 层的节点到根的最短距离为 𝑖i．位于第 𝑖i 层的节点的 𝑁𝐴𝑀𝐸NAME 可以只由位于第 𝑖 +1i+1 层的节点的 𝑁𝐴𝑀𝐸NAME 拼接得到．

原理 2

在同一层内，节点的 𝑁𝐴𝑀𝐸NAME 可以由其在层内的排名唯一标识．

注意，这里的排名是对两棵树而言的，假设节点 𝑢u 位于第 𝑖i 层，那么节点 𝑢u 的排名等于所有 𝑇1T1 和 𝑇2T2 第 𝑖i 层的节点中 𝑁𝐴𝑀𝐸NAME 比 𝑁𝐴𝑀𝐸(𝑢)NAME(u) 小的节点的个数．

推论

我们可以将节点原来的 𝑁𝐴𝑀𝐸NAME 用其在层内的排名代替，然后把原来拼接节点 𝑁𝐴𝑀𝐸NAME 用向数组加入元素代替．

这样用整数和数组来代替字符串，既不会影响算法的正确性，又很大的降低了算法的复杂度．

复杂度证明

首先注意到第 𝑖i 层由拼接得到的 𝑁𝐴𝑀𝐸NAME 的总长度为第 𝑖i 层点的度数之和，即第 𝑖 +1i+1 层的总点数，以下用 𝐿𝑖Li 表示．算法的下一步会将这些 𝑁𝐴𝑀𝐸NAME 看成字符串（数组）并排序，然后将它们替换为其在层内的排名（即重新映射为一个数）．以下引理表明了对总长为 𝐿L 的 𝑚m 个字符串排序的复杂度：

我们可以使用基数排序在 𝑂(𝐿 +|Σ|)O(L+|Σ|) 的时间内完成排序，其中 |Σ||Σ| 为字符集的大小．（有一些实现细节，参见参考资料）
我们可以使用快速排序在 𝑂(𝐿log⁡𝑚)O(Llog⁡m) 的时间内完成排序．证明的大致思路为快排递归树的高度为 𝑂(log⁡𝑚)O(log⁡m)，且暴力比较长度为 ℓ1ℓ1 和 ℓ2ℓ2 的两个字符串的复杂度为 𝑂(min{ℓ1,ℓ2})O(min{ℓ1,ℓ2})．

在 AHU 算法中，第 𝑖i 层字符串的字符集大小最多为第 𝑖 +1i+1 层的点数，即 𝐿𝑖Li，所以基数排序的复杂度是线性的．根据 ∑𝑖𝐿𝑖 =𝑂(𝑛)∑iLi=O(n)，并将每层的复杂度相加后可以看出，若使用字符串的基数排序，则算法的总复杂度为 𝑇(𝑛) =𝑂(𝑛)T(n)=O(n)．同理，如果使用快排排序字符串，那么 𝑇(𝑛) =𝑂(𝑛log⁡𝑛)T(n)=O(nlog⁡n)．

例题

SPOJ-TREEISO

题意翻译：给你两颗无根树，判断两棵树是否同构．

参考代码

---|---

## 参考资料

本文大部分内容译自 [Paper](http://wwwmayr.in.tum.de/konferenzen/Jass08/courses/1/smal/Smal_Paper.pdf) 和 [Slide](https://logic.pdmi.ras.ru/~smal/files/smal_jass08_slides.pdf)．参考资料里的证明会更加全面和严谨，本文做了一定的简化．

对 AHU 算法的复杂度分析，以及字符串的线性时间基数排序算法可以参见 The Design and Analysis of Computer Algorithms 的 3.2 节 Radix sorting，以及其中的 Example 3.2．

* * *

>  __本页面最近更新： 2026/1/7 08:56:54，[更新历史](https://github.com/OI-wiki/OI-wiki/commits/master/docs/graph/tree-ahu.md)
>  __发现错误？想一起完善？[在 GitHub 上编辑此页！](https://oi-wiki.org/edit-landing/?ref=/graph/tree-ahu.md "edit.link.title")
>  __本页面贡献者：[Backl1ght](https://github.com/Backl1ght), [Ir1d](https://github.com/Ir1d), [Enter-tainer](https://github.com/Enter-tainer), [Tiphereth-A](https://github.com/Tiphereth-A), [FinParker](https://github.com/FinParker), [hqztrue](https://github.com/hqztrue), [iamtwz](https://github.com/iamtwz), [kenlig](https://github.com/kenlig), [Menci](https://github.com/Menci)
>  __本页面的全部内容在**[CC BY-SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/deed.zh) 和 [SATA](https://github.com/zTrix/sata-license)** 协议之条款下提供，附加条款亦可能应用