AHU 算法

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

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

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

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

树同构的定义

有根树同构

对于两棵有根树和，如果存在一个双射，使得

且成立，那么称有根树和同构。

无根树同构

对于两棵无根树和，如果存在一个双射，使得

成立，那么称无根树和同构。

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

问题的转化

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

对于无根树和，先分别找出它们的所有重心。

如果这两棵无根树重心数量不同，那么这两棵树不同构。
如果这两颗无根树重心数量都为，分别记为和，那么如果有根树和有根树同构，那么无根树和同构，反之则不同构。
如果这两颗无根树重心数量都为，分别记为和，那么如果有根树和有根树同构或者有根树和同构，那么无根树和同构，反之则不同构。

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

假设有一个可以解决有根树同构问题的算法，那么根据上述方法我们也可以在的时间内解决无根树同构问题。

朴素的 AHU 算法

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

原理 1

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

原理 2

树的同构关系是传递的。既如果和同构，和同构，那么和同构。

推论

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

将以节点为根的子树的作为节点的，记为，那么对于有根树和，如果，那么和同构。

命名算法

实现

AHU 算法

实现

复杂度证明

对于一颗有个节点的有根树，假设他是链状的，那么节点名字长度最长可以是，那么 ASSIGN-NAME 算法的复杂度是的常数倍，即。由此，朴素 AHU 算法的复杂度为。

优化的 AHU 算法

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

原理 1

对树进行层次划分，第层的节点到根的最短距离为。位于第层的节点的可以只由位于第层的节点的拼接得到。

原理 2

在同一层内，节点的可以由其在层内的排名唯一标识。

注意，这里的排名是对两棵树而言的，假设节点位于第层，那么节点的排名等于所有和第层的节点中比小的节点的个数。

推论

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

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

复杂度证明

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

我们可以使用基数排序在的时间内完成排序，其中为字符集的大小。（有一些实现细节，参见参考资料）
我们可以使用快速排序在的时间内完成排序。证明的大致思路为快排递归树的高度为，且暴力比较长度为和的两个字符串的复杂度为。

在 AHU 算法中，第层字符串的字符集大小最多为第层的点数，即，所以基数排序的复杂度是线性的。根据，并将每层的复杂度相加后可以看出，若使用字符串的基数排序，则算法的总复杂度为。同理，如果使用快排排序字符串，那么。

例题

SPOJ-TREEISO

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

参考代码

// Tree Isomorphism, O(nlogn)
// replace quick sort with radix sort ==> O(n)
// Author: _Backl1ght
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
constexpr int N = 1e5 + 5;
constexpr int MAXN = N << 1;

int n;

struct Edge {
  int v, nxt;
} e[MAXN << 1];

int head[MAXN], sz[MAXN], f[MAXN], maxv[MAXN], tag[MAXN], tot, Max;
vector<int> center[2], L[MAXN], subtree_tags[MAXN];

void addedge(int u, int v) {  // 建图
  e[tot].v = v;
  e[tot].nxt = head[u];
  head[u] = tot++;
  e[tot].v = u;
  e[tot].nxt = head[v];
  head[v] = tot++;
}

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);
  }
}

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;
}

void init(int n) {  // 一开始的处理
  for (int i = 1; i <= 2 * n; i++) head[i] = 0;
  tot = 1;
  center[0].clear();
  center[1].clear();

  int u, v;
  for (int i = 1; i <= n - 1; i++) {
    cin >> u >> v;
    addedge(u, v);
  }
  dfs_size(1, -1);
  Max = n;
  dfs_center(1, 1, -1, 0);

  for (int i = 1; i <= n - 1; i++) {
    cin >> u >> v;
    addedge(u + n, v + n);
  }
  dfs_size(1 + n, -1);
  Max = n;
  dfs_center(1 + n, 1 + n, -1, 1);
}

bool cmp(int u, int v) { return subtree_tags[u] < subtree_tags[v]; }

bool rootedTreeIsomorphism(int rt1, int rt2) {
  for (int i = 0; i <= 2 * n + 1; i++) L[i].clear(), subtree_tags[i].clear();
  int h1 = dfs_height(rt1, -1, 0);
  int h2 = dfs_height(rt2, -1, 0);
  if (h1 != h2) return false;
  int h = h1 - 1;
  for (int j = 0; j < (int)L[h].size(); j++) 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;
    }
  }
  return subtree_tags[rt1] == subtree_tags[rt2];
}

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;
}

int 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;
}

参考资料

本文大部分内容译自 Paper 和 Slide。参考资料里的证明会更加全面和严谨，本文做了一定的简化。

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

最后更新: 2024年12月11日
创建日期: 2020年3月19日