图作为一种灵活且应用范围广的数据模型,可以有效表示生物医学、社交网络、模式识别等各种领域中的复杂数据。图编辑距离用于度量两个图之间的结构相似性,在解决图查询等实际应用问题时有广泛的应用场景。然而,现有的图编辑距离计算方法存在NP难的时间复杂度,因而处理效率异常低下。本文针对图编辑距离的计算问题进行研究,具体内容如下。首先,针对基本算法时间和空间代价较高的问题,提出了基于层级映射的图编辑距离计算方法。该方法根据扩展进度对大量中间结果进行层级存储,解决了当优先队列规模增大时效率急速下降的问题,加速了查找合适执行策略和扩展的过程。同时,通过加速初始阶段最优代价的生成过程,提高了图编辑距离计算的效率。其次,提出了新的基于邻接半边估计的代价函数。该函数用边抽离策略计算已遍历的实际代价,实现了对边处理过程的简化;用预存储的状态数据来分析并加速预估代价的计算。和基于层级映射的图编辑距离计算方法相结合,进一步提升了图编辑距离的计算速度。最后,本文采用与化学结构相关的真实数据集,从处理数据图的规模、映射扩展耗时、映射数量等方面进行比较,实验结果验证了本文所提出的图编辑距离计算的高效性。