1. 什么是 AHU 算法AHU 算法Aho-Hopcroft-Ullman 算法是一种用于判断两棵无根树是否同构的经典算法。该算法由 Alfred V. Aho、John E. Hopcroft 和 Jeffrey D. Ullman 三位计算机科学家在 1974 年提出是图同构问题在树结构上的一个高效解决方案。树同构问题在编译器设计、化学分子结构分析、网络拓扑匹配等领域有着广泛的应用。AHU 算法通过为树的每个节点计算一个唯一的“规范编码”Canonical Encoding使得两棵同构的树具有完全相同的编码从而可以在 O(n) 时间复杂度内完成判断。2. 算法核心思想AHU 算法的核心思想是递归地计算树的“括号表示法”并将其规范化。选定根节点对于无根树需要先确定一个“中心”作为根。通常选择树的重心Centroid或直径的中点作为根以确保编码的唯一性。递归编码从叶子节点开始为每个节点计算其子树的编码。编码规则是将子节点的编码按字典序排序后用括号包裹并拼接。规范化通过排序确保同一节点的不同子节点顺序不会影响最终编码从而得到唯一的规范形式。比较比较两棵树的根节点编码是否完全相同。若相同则两棵树同构否则不同构。3. 算法步骤详解3.1 预处理寻找树的根对于无根树 T执行以下步骤确定根计算树的所有重心。一棵树最多有两个重心。如果只有一个重心则以该重心为根。如果有两个重心则在这两个重心之间添加一个虚拟节点作为新的根原两个重心作为其子节点。3.2 递归编码函数 encode(u)定义函数encode(u)返回以节点 u 为根的子树的标准编码如果 u 是叶子节点返回()。否则对于 u 的每个子节点 v递归计算encode(v)。将所有子节点的编码放入一个列表中按字典序排序。将排序后的编码拼接成一个字符串并在其前后加上括号即( sorted_encodings.join() )。3.3 主算法def ahu_isomorphic(tree1, tree2): # 1. 构建邻接表 adj1 build_adjacency(tree1_edges) adj2 build_adjacency(tree2_edges) # 2. 寻找重心作为根 centroids1 find_centroids(adj1) centroids2 find_centroids(adj2) # 3. 为每棵树生成所有可能的根编码考虑可能有两个重心 encodings1 set() for root in centroids1: encoding encode(root, adj1, parent-1) encodings1.add(encoding) encodings2 set() for root in centroids2: encoding encode(root, adj2, parent-1) encodings2.add(encoding) # 4. 比较编码集合是否有交集 return len(encodings1 encodings2) 04. 时间复杂度与空间复杂度时间复杂度O(n)其中 n 是树的节点数。每个节点被访问一次排序子节点编码的总成本可以通过使用基数排序优化到 O(n)。空间复杂度O(n)用于存储邻接表、递归栈和编码字符串。5. 应用场景编译器设计与代码优化识别语法树的结构等价性。化学信息学判断分子结构图是否同构。网络拓扑分析比较不同网络的连接结构。数据聚类与模式识别将结构相似的数据归类。6. 总结AHU 算法是解决树同构问题的经典且高效的方法。它通过递归计算规范编码将复杂的结构比较转化为字符串比较。理解其重心定根、递归编码和字典序排序的核心步骤是掌握该算法的关键。在实际应用中需要注意处理无根树、多重心等边界情况并可根据具体场景对编码方式进行微调。