一个基于DFS编码的图形匹配算法

• 来源期刊: 计算机与数字工程
• 学科: 工学
• 关键词: DFS编码 图形匹配 算法
• 年，卷（期）: 2009,（9）
• 所属期刊栏目: 专栏·Web信息系统及应用
• 页码范围: 72-75
• 页数: 4页
• 分类号: TP391.41
• 字数: 3802字
• 语种: 中文

摘要

快速有效的图形查询是图形数据库成功应用的关键.文章利用图的词典顺序,用唯一的最小DFS(深度优先搜索)编码表示每个图.根据两个图同构当且仅当它们的最小DFS编码相同这一性质,将图形匹配转化为图的最小DFS编码的比较:在判断两个标记图形是否同构时,可以先求出图的最小DFS编码,再用有效的匹配算法进行比较.