一种判定树同构的BULT算法

摘要

将判定两棵树的同构问题转化成“图的同构”问题和“两棵树根结点之间的对应关系”问题的判定。基于图与树的关系,提出一种自底向上分层遍历图结点(Bottom_Up Layer Traversing)的方法,简称BULT方法,解决以上两个问题,从而得到一种线性的时间复杂度与空间复杂度的树同构判定算法,并给出了算法正确性证明。该算法很容易扩展为图同构的判定算法。

关键词