两个图之间的编辑距离

Question

22

我在想，对于字符串，我们有字符串的Levenshtein距离（或编辑距离），那么对于图形是否有类似的东西呢？

我的意思是，是否有一种标量度量方法来确定将一个图G1转换为另一个图G2所需的原子操作数（节点和边缘插入/删除）。

- linello

4个回答

10

您应该查看这篇论文《图形编辑距离调查》，请点击这里。

- J.-E. Pin

4

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

- Shafaet

3

注意：

编辑距离（又称Levenshtein距离）是指两个字符串之间的距离。

但是在图形中，您需要搜索至少N!个位置，以找到每个边缘和顶点的标识。您可以轻松比较两个图表的唯一索引，但主要问题是为每个顶点和边缘定义标识。这个问题（查找两个图表中每个顶点和边缘的标识，使它们能够转换）非常困难，并被称为同构问题（NP完全）。您可以查询同构图。

- amin k

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jason · Accepted Answer

我认为图编辑距离是您正在寻找的度量标准。

图编辑距离测量将一个图形转换成另一个图形所需的最小图编辑操作次数，允许的图编辑操作包括：

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