1

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

编辑：找到解决方案，从这篇文章中删除了不必要的混乱

4

2 回答 2

0

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

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

想法 2：可以在 hashmap 中对字符串进行索引。与其携带像“（（L），（L））”这样的子字符串，我们可以为该字符串分配一个索引号，比如说2。现在我们可以用“2”来引用这个子树和所有相同的子树，而不是使用字符串表示。字符串是哈希图中的键，值是分配给这些字符串的唯一整数。

这是从第一棵树构建哈希图的代码：

我们的第一个电话应该是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

于 2015-03-25T23:24:30.747 回答
0

您还可以使用 David Matula 的 Tree - Integer Bijection，它将树映射到整数。

这是一种为每棵树分配一个唯一的自然数的方法。

以下是前 32 棵树的示例：

1 到 32 的 Matula 树

有关算法的演练，请参阅本文档中的练习：http ://williamsharkey.com/integer-tree-isomorphism.pdf

于 2017-11-06T04:19:23.907 回答