检测树形结构之间的差异 [英] Detect differences between tree structures

问题描述

这是更多的是CS的问题，但一个有趣的：

This is more of a CS question, but an interesting one :

让我们说我们有2树形结构或多或少重组相同的节点。你会如何​​找到

Let's say we have 2 tree structures with more or less the same nodes reorganized. How would you find

1. 的任意的
2. 在某种意义上的最小的

1. any
2. in some sense minimal

操作顺序

• MOVE（A，B） - 移动节点的节点B下（与整个子树）
• 插入（N，B） - 插入一个新节点N B节点下
• 删除（A） - 删除节点A（与整个子树）

• MOVE(A, B) - moves node A under node B (with the whole subtree)
• INSERT(N, B) - inserts a new node N under node B
• DELETE (A) - deletes the node A (with the whole subtree)

这是把一种树到其他。

有可能会显然是情况下，这样的转变是不可能的，琐碎的幸福根与儿童B至根B带孩子等）。在这种情况下，算法将简单地提供一个结果的不可能的

There might obviously be cases where such transformation is not possible, trivial being root A with child B to root B with child A etc.). In such cases, the algorithm would simply deliver an result "not possible".

更壮观的版本是一个泛化的网络，即当我们假设一个节点可以在树中出现多次（实际上有多个父母），而周期是被禁止的。

Even more spectacular version is a generalization for networks, i.e. when we assume that a node can occur multiple times in the tree (effectively having multiple "parents"), while cycles are forbidden.

免责声明：这是不会一门功课，实际上它来自于一个真实的商业问题，我觉得这是很有意思的想知道是否有人会知道解决办法

Disclaimer : This is not a homework, actually it comes from a real business problem and I found it quite interesting wondering if somebody might know a solution.

推荐答案

目前不仅在图同构维基百科的文章（如Space_C0wb0y指出的），但也对的图同构问题。它有一个部分解决特殊情况下为其多项式时间的解决方案是已知的。树木就是其中之一，它列举了以下两个引用：

There is not only a Wikipedia article on graph isomorphism (as Space_C0wb0y points out) but also a dedicated article on the graph isomorphism problem. It has a section Solved special cases for which polynomial-time solutions are known. Trees is one of them and it cites the following two references:

• PJ凯利，树木同余定理太平洋数学杂志，7（1957年），第961-968
• 阿霍，阿尔弗雷德·V。; Hopcroft，约翰;乌尔曼，杰弗里·（1974年），设计和计算机算法分析，阅读，马萨诸塞州：艾迪生韦斯利

这篇关于检测树形结构之间的差异的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！