AHU Algorithm

The AHU algorithm is used to determine whether two rooted trees are isomorphic.

Another common approach for determining tree isomorphism is Tree Hashing.

Prerequisites: Tree Basics, Tree Centroids

It is recommended to read along with the examples given in the references.

Definition of Tree Isomorphism

Rooted Tree Isomorphism

For two rooted trees \(T_1(V_1,E_1,r_1)\) and \(T_2(V_2,E_2,r_2)\), if there exists a bijection \(\varphi: V_1 \rightarrow V_2\) such that

\[ \forall u,v \in V_1,(u,v) \in E_1 \iff (\varphi(u),\varphi(v)) \in E_2 \]

and \(\varphi(r_1)=r_2\) holds, then the rooted trees \(T_1(V_1,E_1,r_1)\) and \(T_2(V_2,E_2,r_2)\) are said to be isomorphic.

Unrooted Tree Isomorphism

For two unrooted trees \(T_1(V_1,E_1)\) and \(T_2(V_2,E_2)\), if there exists a bijection \(\varphi: V_1 \rightarrow V_2\) such that

\[ \forall u,v \in V_1,(u,v) \in E_1 \iff (\varphi(u),\varphi(v)) \in E_2 \]

holds, then the unrooted trees \(T_1(V_1,E_1)\) and \(T_2(V_2,E_2)\) are said to be isomorphic.

In simple terms, if by relabeling all nodes of tree \(T_1\), tree \(T_1\) becomes exactly the same as tree \(T_2\), then the two trees are isomorphic.

Transformation of the Problem

The unrooted tree isomorphism problem can be transformed into the rooted tree isomorphism problem. The specific method is as follows:

For unrooted trees \(T_1(V_1, E_1)\) and \(T_2(V_2,E_2)\), first find all their centroids.

• If the numbers of centroids of these two unrooted trees are different, then the two trees are not isomorphic.
• If the numbers of centroids of these two unrooted trees are both \(1\), denoted as \(c_1\) and \(c_2\) respectively, then if the rooted tree \(T_1(V_1,E_1,c_1)\) and the rooted tree \(T_2(V_2,E_2,c_2)\) are isomorphic, then the unrooted trees \(T_1(V_1, E_1)\) and \(T_2(V_2,E_2)\) are isomorphic, otherwise they are not.
• If the numbers of centroids of these two unrooted trees are both \(2\), denoted as \(c_1,c'_1\) and \(c_2,c'_2\) respectively, then if the rooted tree \(T_1(V_1,E_1,c_1)\) and the rooted tree \(T_2(V_2,E_2,c_2)\) are isomorphic or the rooted tree \(T_1(V_1,E_1,c'_1)\) and \(T_2(V_2,E_2,c_2)\) are isomorphic, then the unrooted trees \(T_1(V_1, E_1)\) and \(T_2(V_2,E_2)\) are isomorphic, otherwise they are not.

Therefore, as long as the rooted tree isomorphism problem is solved, we can transform the unrooted tree isomorphism problem into a rooted tree isomorphism problem according to the above method, and then solve the unrooted tree isomorphism problem.

Assuming there is an algorithm that can solve the rooted tree isomorphism problem in \(O(\left|V\right|)\) time, then according to the above method we can also solve the unrooted tree isomorphism problem in \(O(\left|V\right|)\) time.

Naive AHU Algorithm

The naive AHU algorithm is based on bracket sequences.

Principle 1

We know that a valid bracket sequence uniquely corresponds to a rooted tree, and the bracket sequence of a tree is formed by concatenating the bracket sequences of its subtrees. If we obtain a new bracket sequence by changing the order of concatenating the subtree bracket sequences, then the tree corresponding to the new bracket sequence is isomorphic to the tree corresponding to the original bracket sequence.

Principle 2

The tree isomorphism relation is transitive. That is, if \(T_1\) is isomorphic to \(T_2\), and \(T_2\) is isomorphic to \(T_3\), then \(T_1\) is isomorphic to \(T_3\).

Corollary

Consider the recursive algorithm for computing the tree bracket sequence. When backtracking, we concatenate the bracket sequences of the subtrees. If during concatenation, we concatenate the sequences in lexicographically increasing order and denote the final result as \(NAME\).

Let the \(NAME\) of the subtree rooted at node \(r\) be the \(NAME\) of node \(r\), denoted as \(NAME(r)\). Then for rooted trees \(T_1(V_1,E_1,r_1)\) and \(T_2(V_2,E_2,r_2)\), if \(NAME(r_1)=NAME(r_2)\), then \(T_1\) and \(T_2\) are isomorphic.

Naming Algorithm

Implementation

\[ \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} \]

AHU Algorithm

Implementation

\[ \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}\\ 10 & \qquad \qquad \text{return false} \end{array} \]

Complexity Proof

For a rooted tree with \(n\) nodes, assuming it is chain-like, the maximum length of a node's name can be \(n\). Then the complexity of the ASSIGN-NAME algorithm is a constant multiple of \(1+2+\cdots+n\), i.e., \(\Theta(n^2)\). Consequently, the complexity of the naive AHU algorithm is \(O(n^2)\).

Optimized AHU Algorithm

The drawback of the naive AHU algorithm is that the \(NAME\) of a tree can be excessively long. We can make some optimizations regarding this point.

Principle 1

Partition the tree into levels, where the shortest distance from a node at level \(i\) to the root is \(i\). The \(NAME\) of a node at level \(i\) can be formed solely by concatenating the \(NAME\)s of nodes at level \(i+1\).

Principle 2

Within the same level, the \(NAME\) of a node can be uniquely identified by its rank within the level.

Note: Here, the ranking is relative to both trees. Suppose node \(u\) is at level \(i\). Then the rank of node \(u\) equals the number of nodes in level \(i\) of both \(T_1\) and \(T_2\) whose \(NAME\) is lexicographically smaller than \(NAME(u)\).

Corollary

We can replace the original \(NAME\) of a node with its rank within the level, and then replace the concatenation of node \(NAME\)s with appending elements to an array.

Using integers and arrays instead of strings does not affect the correctness of the algorithm and greatly reduces its complexity.

Complexity Proof

First, note that the total length of the \(NAME\)s obtained by concatenation at level \(i\) equals the sum of the degrees of nodes at level \(i\), which is the total number of nodes at level \(i+1\), denoted by \(L_i\) below. The next step of the algorithm treats these \(NAME\)s as strings (arrays), sorts them, and then replaces them with their rank within the level (i.e., remaps them to a number). The following lemma indicates the complexity of sorting \(m\) strings with total length \(L\):

1. We can use radix sort to complete the sorting in \(O(L+|\Sigma|)\) time, where \(|\Sigma|\) is the size of the character set. (There are some implementation details; see the references.)
2. We can use quicksort to complete the sorting in \(O(L \log m)\) time. The general idea of the proof is that the height of the quicksort recursion tree is \(O(\log m)\), and the complexity of naively comparing two strings of lengths \(\ell_1\) and \(\ell_2\) is \(O(\min\{\ell_1,\ell_2\})\).

In the AHU algorithm, the character set size for strings at level \(i\) is at most the number of nodes at level \(i+1\), i.e., \(L_i\), so radix sort runs in linear time. Since \(\sum_i L_i=O(n)\), summing the complexity of each level shows that if radix sort for strings is used, the total complexity of the algorithm is \(T(n)=O(n)\). Similarly, if quicksort is used to sort the strings, then \(T(n)=O(n \log n)\).

Example Problem

SPOJ-TREEISO

Problem translation: Given two unrooted trees, determine whether they are isomorphic.

Reference Code

// 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) {  // Build graph
  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) {  // Find size values
  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 if equal
  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) {  // Recursively find 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) {  // Initial processing
  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;
}

References

Most of this article is translated from the Paper and Slide. The proofs in the references are more comprehensive and rigorous; this article makes certain simplifications.

For the complexity analysis of the AHU algorithm and the linear-time radix sort algorithm for strings, refer to Section 3.2 Radix sorting and Example 3.2 in The Design and Analysis of Computer Algorithms.

---

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用