| 一种判定树同构的BULT算法 |
| |
| 引用本文： | 温雪莲,梁华金. 一种判定树同构的BULT算法[J]. 中山大学学报(自然科学版), 2005, 44(6): 24-28 |
| |
| 作者姓名： | 温雪莲 梁华金 |
| |
| 作者单位： | 中山大学,计算机科学系,广东,广州,510275 |
| |
| 摘 要： | 将判定两棵树的同构问题转化成"图的同构"问题和"两棵树根结点之间的对应关系"问题的判定.基于图与树的关系,提出一种自底向上分层遍历图结点(Bottom-Up Layer Traversing)的方法,简称 BULT方法,解决以上两个问题,从而得到一种线性的时间复杂度与空间复杂度的树同构判定算法,并给出了算法正确性证明.该算法很容易扩展为图同构的判定算法.
|
| 关 键 词： | 树 树同构 时间复杂度 空间复杂度 |
| 文章编号： | 0529-6579(2005)06-0024-05 |
| 收稿时间： | 2004-12-06 |
| 修稿时间： | 2004-12-06 |
A BULT Algorithm for Tree Isomorphism |
| |
| WEN Xue-lian,LIANG Hua-jin. A BULT Algorithm for Tree Isomorphism[J]. Acta Scientiarum Naturalium Universitatis Sunyatseni, 2005, 44(6): 24-28 |
| |
| Authors: | WEN Xue-lian LIANG Hua-jin |
| |
| Affiliation: | Department of Computer Science, Sun Yat-sen University, Guangzhou 510275, China |
| |
| Abstract: | Solving the tree isomorphism problem is equivalent to solve two problems: whether there exists a bi-jection between two graphs and whether the bi-jection maps on distinguished node in one graph to one distinguished node in the other graph.Based on the relation between graphs and trees,a bottom up layer traversing algorithm,BULT algorithm for short,with linear time complexity and space complexity to solve these two problems is given.And the correctness of the altgorithm is also proven in the paper.The result can be easily extended to graphs. |
| |
| Keywords: | tree tree isomorphism time complexity space complexity |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
