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

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

A DFS Code Based on Algorithm for Graph Pattern Matching

Fast and efficient graph query is the key to successful application of graph database.In this paper,we use a lexicographic order among graphs to map each graph to a unique minimum DFS code as its canonical label.Two graphs are isomorphism if and only if they have the same minimum DFS code.According to this relationship,we can compare the minimum DFS codes of graphs to see-if they are isomorphism.In order to determining whether the two graphs are isomorphism,we first obtain the minimum DFS code,and then use ...