关键词: 图同构, 结点距离, 距离分层, 距离统计, Floyd算法, 时间复杂度

Abstract: To determine two graphs are isomorphic or not by the definition of graph isomorphism, at worst, the time complexity is O(N!). Against this problem, it introduces an algorithm which is based on the distance statistics of the vertices. Vertices are stratified by distance, by counting the numbers of related edges and related vertices of vertices which are isometric. The algorithm shows the difference of the vertices, and points out the vertices correspondence of two graphs. If the vertices distance array and layer related vertices array of two graphs are not one-to-one, the time complexity of the algorithm is only O(N4). If they are one-to-one, swap the sequence of the vertices in one graph which may correspond to the vertex in the other graph, avoid swapping the sequence of all vertices, in this condition, the time complexity is reduced by many times.

Key words: graph isomorphism, vertex distance, distance layering, distance statistics, Floyd algorithm, time complexity