一尘不染

计算最少的运算以使两个树结构相同

algorithm

这更多是一个CS问题,但有趣的是:

假设我们有2个树状结构,其中或多或少地重组了相同的节点。你怎么会找到

  1. 任何
  2. 在某种意义上说 极小

操作顺序

  • MOVE(A, B) -将节点A移动到节点B下(带有整个子树)
  • INSERT(N, B)- 在节点B下插入 节点N
  • DELETE (A) -删除节点A(带有整个子树)

将一棵树转化为另一棵树。

显然,在某些情况下不可能进行这种转换,琐碎的操作是将带有子B的根A转换为带有子A的根B等)。在这种情况下,该算法将简单地传递“ 不可能 ” 的结果。

对于网络来说,更通用的版本是通用的,即当我们假设一个节点可以在树中出现多次(有效地具有多个“父级”)时,则禁止循环。

免责声明:这 不是 家庭作业,实际上是来自一个实际的业务问题,我想知道是否有人知道解决方案非常有趣。


阅读 175

收藏
2020-07-28

共1个答案

一尘不染

不仅有Wikipedia关于图同构的文章(如Space_C0wb0y所指出),而且还有关于图同构问题的专门文章。它有一个Solved special cases已知多项式时间解的部分。树是其中之一,它引用了以下两个引用:

2020-07-28