我只是想知道，就像对于两个字符串之间有编辑距离（或编辑距离）的字符串一样，图形是否有类似的东西？
我的意思是，一个标量度量，用于标识将图
G1G2我认为图形编辑距离是您正在寻找的度量。
图形编辑距离衡量将一张图转换为另一张图所需的最少图形编辑操作次数，允许的图形编辑操作包括：
然而，计算两个图之间的图编辑距离是 NP 困难的。计算此值的最有效算法是基于 A* 的算法，还有其他次优算法。
你应该看看论文图形编辑距离的调查
对于一般图来说，正如其他人在答案中提到的那样，这是一个 NP 完全问题。但对于树图，有众所周知的多项式算法。其中最著名的可能是 1989 年发表的“张莎莎”算法。
注：
编辑距离（或编辑距离）位于两个字符串之间
但是在 Graph 中你应该在至少 N 个之间进行搜索！您找到每个边和顶点的标识的位置。 您可以通过唯一索引轻松比较两个图，但是 主要问题是定义每个顶点和边的恒等性。这个问题（在两个图中找到可以变换的每个顶点和边的恒等性）非常困难，被称为同构问题（NP-Complete）。 你可以搜索同构图。
目前，最有效的精确答案是深度优先图编辑距离（DF-GED），来自用于解决模式识别问题的精确图编辑距离算法。 Python 的
networkx