图匹配是衡量两个图之间相似性的过程,在模式识别,社交网络,医药学等多个领域早已广泛应用。近几十年来,研究者们提出了大量解决图匹配问题的算法。其中,图编辑距离作为解决图匹配问题最常用的方法已受到越来越多的关注。目前,对图编辑距离问题的研究主要分为近似图编辑距离和精确图编辑距离,本文针对基于近似图编辑距离的匹配算法进行研究。首先,介绍了与图相关的基本知识,以及图编辑距离的相关概念,并对相关算法及实现过程进行了简要介绍。其次,分析SFBP(Square Fast Bipartite)代价矩阵在构建过程中存在精确度缺失的问题,提出一种新的代价矩阵。通过计算目标图和源图中任意两个节点的添加、删除之和,将其与SFBP代价矩阵中的相应节点进行替换,得到新的代价矩阵。再次,对基于新的代价矩阵进行求解的图匹配算法进行改进并提出RC-Greedy算法。已有算法在使用贪婪策略选取分配节点的过程中,优先从代价矩阵的行的角度去考虑节点的大小,没有考虑节点在其所在列中的大小,存在精确度缺失问题。通过从列的角度获取次优分配节点,增加对比节点的数量,更加全面的考虑分配情况,从而得到更优的分配结果。最后,基于GREYC实验室的化学数据集和人工数据集对改进后的代价矩阵和算法进行了实验对比,验证。