1

假设我有二叉树 A 和 B，我想知道 A 是否是 B 的“一部分”。我不仅在谈论子树。我想知道的是 B 是否拥有 A 的所有节点和边。

我的想法是，因为树本质上是一个图，我可以将这个问题视为子图同构问题（即检查 A 是否是 B 的子图）。但根据维基百科，这是一个 NP 完全问题。

http://en.wikipedia.org/wiki/Subgraph_isomorphism_problem

我知道您可以使用 O(n) 算法检查 A 是否是 B 的子树（例如，使用前序和中序遍历将树展平为字符串并检查子字符串）。我试图对此进行一些修改，以查看是否也可以仅测试“零件”，但无济于事。这就是我卡住的地方。

除了使用子图同构之外，还有其他方法可以查看此问题吗？我认为必须有更快的方法，因为二叉树是更受限制和更简单的图形版本。

提前致谢！

编辑：我意识到，对于我的问题，即使是蛮力方法的最坏情况也只会采用 O(m * n)，这是多项式。所以我想这毕竟不是一个NP完全问题。那么我的下一个问题是，有没有比 O(m*n) 更快的算法？

4

2 回答 2

2

我将分两步解决这个问题：

  1. A查找in的根B（DFS 的任一 BFS）
  2. 使用递归算法验证它A包含在B（给出该起始节点）中，如下所示（我编造了相同的疯狂伪语言，因为您没有指定语言。我认为这应该是可以理解的，无论您的背景如何）。请注意，它a是来自A（最初是根）b的节点，并且是来自B（最初是在步骤 1 中找到的节点）的节点

function checkTrees(node a, node b) returns boolean
    if a does not exist or b does not exist then
        // base of the recursion
        return false
    else if a is different from b then
        // compare the current nodes
        return false
    else
        // check the children of a
        boolean leftFound = true
        boolean rightFound = true

        if a.left exists then
            // try to match the left child of a with
            // every possible neighbor of b
            leftFound = checkTrees(a.left, b.left)
                       or checkTrees(a.left, b.right)
                       or checkTrees(a.left, b.parent)

        if a.right exists then
            // try to match the right child of a with
            // every possible neighbor of b
            leftFound = checkTrees(a.right, b.left)
                       or checkTrees(a.right, b.right)
                       or checkTrees(a.right, b.parent)

        return leftFound and rightFound

关于运行时间：设m为 中的节点数，A为n中的节点数B。第一步的搜索需要O(n)时间。第二步的运行时间取决于我所做的一个关键假设，但这可能是错误的：我假设 的每个节点最多A等于的一个节点。如果是这样的话，第二步的运行时间是（因为你永远不可能在错误的方向上搜索太远）。所以总运行时间为.BO(m)O(m + n)

在写下我的假设时，我开始怀疑这是否过于简单化了你的情况......

于 2013-08-19T21:26:37.817 回答
0

您可以自下而上比较树，如下所示：

  • 对于树 A 中的每个叶子，识别树 B 中的相应节点。
  • 从刚刚匹配的节点开始并行遍历两棵树的根。具体来说，移动到 A 中节点的父节点，然后移动到 B 中的根节点，直到遇到 B 中的相应节点（继续）或 A 中的标记节点（见下文，如果在 B 中找到匹配项，继续，否则失败）或 B 的根（失败）
  • 标记 A 中访问过的所有节点。

你成功了，如果你没有失败;-)。

算法的主要部分运行O(e_B)——在最坏的情况下，B 中的所有边都被访问了恒定的次数。O(n_A * log n_B)如果对 B 个顶点进行排序，则叶节点匹配将运行， O(n_A * log n_A + n_B * log n_B + n) = O(n_B * log n_B)（对每个节点集进行排序，此后对结果进行线性扫描），否则。

编辑：重新阅读您的问题，上述步骤 2 更容易，至于 A、B 中的匹配节点，它们的父节点也必须匹配（否则边缘集之间会出现不匹配）。当然，对最坏情况的运行时间没有影响。

于 2013-08-20T11:16:53.660 回答