java - 用散列解决树同构

Question

给定两棵已知根的树，我们如何有效地确定这两棵树是否同构？我们只关心树的形状，而不关心节点的值。如果一棵树可以通过重命名其节点而变成另一棵树，那么这些树是同构的。该算法不需要 100% 正确，因此只要哈希冲突很少发生，我们就可以使用哈希。

编辑:找到解决方案，删除本文中不必要的困惑

Answer 1

经过大量工作和一些帮助，我想出了一个 O(n log n) 解决方案，它也恰好 100% 正确。它基于两个想法:

想法 1: 树可以表示为列出其子树的字符串。例如，叶子可以表示为“L”​​。有 2 个叶子的树可以表示为“(L),(L)”。具有 2 个叶子的子树的树可以表示为“((L),(L))”等。这种方法的问题是大树会导致长且重复的字符串，这会减慢算法速度。

想法 2: 字符串可以在 HashMap 中建立索引。我们可以为该字符串分配一个索引号，比如 2，而不是携带像“((L),(L))”这样的子字符串。现在我们可以用“2”来引用这个子树和所有相同的子树，而不是使用字符串表示形式。字符串是 HashMap 中的键，值是分配给这些字符串的唯一整数。

以下是从第一棵树构建 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;
}

我们现在可以调用 Tree 2 的 fill (将“edges”替换为 Tree 2 信息，保持 HashMap 不变)。如果它返回相同的整数，则树匹配。

非常感谢http://logic.pdmi.ras.ru/~smal/files/smal_jass08_slides.pdf