用哈希解樹同構

Question

給定2棵已知根的樹，怎樣纔能有效判斷樹是否同構？我們只關心樹的形狀，而不關心節點的值。如果一棵樹可以通過重命名其節點而變成另一棵樹，那麼樹就是同構的。該算法在100％的時間內不需要是正確的，所以只要散列衝突很少，我們就可以使用散列。

編輯：找到的解決方案，從這個帖子

Answer 1

後的工作和一些幫助去除不必要的混亂，我想出了一個爲O（n log n）的解決方案，也恰好是正確的時間100％。它基於2個想法：

想法1：樹可以表示爲一個字符串列出其子樹。例如，葉子可以表示爲「L」​​。具有2片葉子的樹可以表示爲「（L），（L）」。具有2片葉子樹的樹可以表示爲「（（L），（L））」等。這種方法的問題在於大樹會導致長而重複的串，這會減慢算法下降。

想法2：字符串可以在散列表中索引。我們可以把這個字符串分配一個索引號，比如說「（（L），（L））」，而不是像「（（L），（L））」那樣。現在我們可以用「2」來引用這個子樹和所有相同的子樹，而不是使用字符串表示。字符串是散列表中的關鍵字，值是分配給這些字符串的唯一整數。

下面是從第一棵樹建設HashMap中的代碼：

我們首先應該聯繫fill(root, -1, 1)

public static int fill(int current, int previous, int height) { 
    ArrayList<Integer> subtrees = new ArrayList<>(); 
    for (int next : edges[current]) { 
     if (next == previous) continue; 
     int subtree = fill(next, current, height+1); 
     subtrees.add(subtree); 
    } 
    // We have to sort subtrees for "2,4" and "4,2" to be considered the same 
    Collections.sort(subtrees); 
    StringBuilder sb = new StringBuilder(height + "."); 
    for (Integer subtree : subtrees) { 
     sb.append(subtree +","); 
    } 
    String key = new String(sb); 
    if (map.containsKey(key)) return map.get(key); 
    int index = map.size(); // assigning next available number 
    map.put(key, index); 
    return index; 
} 

我們現在可以與樹2呼籲填補樹2（代替「邊緣」信息，保持HashMap的樣子）。如果它返回相同的整數，樹匹配。

大部分信貸http://logic.pdmi.ras.ru/~smal/files/smal_jass08_slides.pdf

Answer 2

您還可以使用大衛Matula的樹 - 整數雙向注入，它映射樹爲整數。

這是一種爲每棵樹分配一個唯一的自然數的方法。

這裏是前32種樹木的例子：

對於算法的演練，請參見練習本文檔中：http://williamsharkey.com/integer-tree-isomorphism.pdf