AHU 算法
AHU 算法用於判斷兩棵有根樹是否同構。
判斷樹同構外還有一種常見的做法是 樹哈希 。
前置知識：樹基礎 ，樹的重心
建議配合參考資料裏給的例子觀看。
樹同構的定義
有根樹同構
對於兩棵有根樹 \(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(\left|V\right|)\) 解決有根樹同構問題的算法，那麼根據上述方法我們也可以在 \(O(\left|V\right|)\) 的時間內解決無根樹同構問題。
樸素的 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\) 同構。
命名算法
實現
\[
\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 算法
實現
\[
\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}
\]
複雜度證明
對於一顆有 \(n\) 個節點的有根樹，假設他是鏈狀的，那麼節點名字長度最長可以是 \(n\) ，那麼 ASSIGN-NAME 算法的複雜度是 \(1+2+\cdots+n\) 的常數倍，即 \(\Theta(n^2)\) 。由此，樸素 AHU 算法的複雜度為 \(O(n^2)\) 。
優化的 AHU 算法
樸素的 AHU 算法的缺點是樹的 \(NAME\) 的長度可能會過長，我們可以針對這一點做一些優化。
原理 1
對樹進行層次劃分，第 \(i\) 層的節點到根的最短距離為 \(i\) 。位於第 \(i\) 層的節點的 \(NAME\) 可以 只 由位於第 \(i+1\) 層的節點的 \(NAME\) 拼接得到。
原理 2
在同一層內，節點的 \(NAME\) 可以由其在層內的排名唯一標識。
注意 ，這裏的排名是對兩棵樹而言的，假設節點 \(u\) 位於第 \(i\) 層，那麼節點 \(u\) 的排名等於所有 \(T_1\) 和 \(T_2\) 第 \(i\) 層的節點中 \(NAME\) 比 \(NAME(u)\) 小的節點的個數。
推論
我們可以將節點原來的 \(NAME\) 用其在層內的排名代替，然後把原來拼接節點 \(NAME\) 用向數組加入元素代替。
這樣用整數和數組來代替字符串，既不會影響算法的正確性，又很大的降低了算法的複雜度。
複雜度證明
首先注意到第 \(i\) 層由拼接得到的 \(NAME\) 的總長度為第 \(i\) 層點的度數之和，即第 \(i+1\) 層的總點數，以下用 \(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\) 層字符串的字符集大小最多為第 \(i+1\) 層的點數，即 \(L_i\) ，所以基數排序的複雜度是線性的。根據 \(\sum_i L_i=O(n)\) ，並將每層的複雜度相加後可以看出，若使用字符串的基數排序，則算法的總複雜度為 \(T(n)=O(n)\) 。同理，如果使用快排排序字符串，那麼 \(T(n)=O(n \log n)\) 。
例題
SPOJ-TREEISO
題意翻譯：給你兩顆無根樹，判斷兩棵樹是否同構。
參考代碼
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133 // Tree Isomorphism, O(nlogn)
// replace quick sort with radix sort ==> O(n)
// Author: _Backl1ght
#include <bits/stdc++.h>
using namespace std ;
typedef long long ll ;
const int N = 1e5 + 5 ;
const 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 ++ ) {
scanf ( "%d %d" , & 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 ++ ) {
scanf ( "%d %d" , & 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 () {
int T ;
scanf ( "%d" , & T );
while ( T -- ) {
scanf ( "%d" , & n );
init ( n );
puts ( treeIsomorphism () ? "YES" : "NO" );
}
return 0 ;
}
參考資料
本文大部分內容譯自 Paper 和 Slide 。參考資料裏的證明會更加全面和嚴謹，本文做了一定的簡化。
對 AHU 算法的複雜度分析，以及字符串的線性時間基數排序算法可以參見 The Design and Analysis of Computer Algorithms 的 3.2 節 Radix sorting，以及其中的 Example 3.2。
更新历史 在 GitHub 上编辑此页！ Backl1ght CC BY-SA 4.0 和 SATA