这更多是一个CS问题,但有趣的是:
假设我们有2个树状结构,其中或多或少地重组了相同的节点。你怎么会找到
操作顺序
MOVE(A, B)
INSERT(N, B)
DELETE (A)
将一棵树转化为另一棵树。
显然,在某些情况下不可能进行这种转换,琐碎的操作是将带有子B的根A转换为带有子A的根B等)。在这种情况下,该算法将简单地传递“ 不可能 ” 的结果。
对于网络来说,更通用的版本是通用的,即当我们假设一个节点可以在树中出现多次(有效地具有多个“父级”)时,则禁止循环。
免责声明:这 不是 家庭作业,实际上是来自一个实际的业务问题,我想知道是否有人知道解决方案非常有趣。
不仅有Wikipedia关于图同构的文章(如Space_C0wb0y所指出),而且还有关于图同构问题的专门文章。它有一个Solved special cases已知多项式时间解的部分。树是其中之一,它引用了以下两个引用:
Solved special cases