编辑两个图之间的距离

Question

我只是想知道，如果字符串在两个字符串之间有Levenshtein距离（或编辑距离），是否有类似的图？

我的意思是一个标量度量，用于标识将图形G1转换为图形G2的原子操作数（节点和边的插入/删除）。

Answer 1

注：

的Levenshtein距离（或编辑距离）是两个字符串

之间但在图形，你应该至少N之间的搜索！您可以找到每个边和顶点的标识。 您可以很容易地通过唯一索引来比较两个图形，但是 主要问题是定义每个顶点和边的标识。这个问题（找到两个图中每个顶点和边的标识，它们可以转换）非常困难，称为同构问题（NP-Complete）。 您可以搜索同构图。

Answer 2

对于一般图，它是一个NP完全问题，正如其他人在他们的答案中提到的那样。但是对于树图，存在众所周知的多项式算法。可能是他们最着名的是1989年发表的“张沙沙”算法。

Answer 3

我认为图形编辑距离是您要查找的度量。

图形编辑距离度量图形编辑操作的最小数量，以一个图形变换到另一个，并且允许的图形编辑操作包括：

• 插入/删除的分离的顶点
• 插入/删除的边缘
• 更改顶点/边的标签（如果标记的曲线图）

然而，计算两个图之间的图形编辑距离是NP难题。用于计算的最有效的算法是基于A *的算法，并且还有其他次优算法。

Answer 4

你应该看看纸A survey of graph edit distance