图作为一种通用的数据模型,可以表示现实世界中各种复杂的实体之间的关系,在模式识别、图像处理、社交网络等多个领域有广泛应用。图匹配的本质是计算两个图结构的相似性,现有方法在计算图结构相似性的时候通常采用过滤-验证机制。在过滤阶段,现有算法存在划分结构质量差的问题;在验证阶段,现有算法存在A*算法下界估计不紧密的问题。本文针对图匹配的方法进行研究。首先,针对过滤阶段划分结构质量差的问题,本文通过概率估计的方法提高分区质量的方法,通过对分区结构的调整得到较优的划分结构。同时,在分区过滤之后,通过回收不匹配分区再次排除不满足条件的数据图,得到可能满足编辑距离约束的候选集。其次,在基于A*的验证阶段,代价函数选取得是否合适影响着验证的效率。针对验证阶段存在下界估计不紧密的问题,本文给出一种更为紧密的下界估计算法,这保证了在验证过程中一些不满足条件的部分映射可以被尽快发现而不必要被保持到验证过程的最后阶段。同时,扩展匹配分区给出了验证的基础映射,加快了验证的进程。最后,本文基于AIDS数据集进行实验,从过滤效果、验证时间、可扩展性等方面分析对比,验证了本文所提出算法的优越性。