我只是想知道，对于我们在两个字符串之间具有 Levenshtein 距离（或编辑距离）的字符串，是否有类似的图形？
我的意思是，一个标量度量，它标识将 graph 转换为 graph 的原子操作（节点和边插入/删除）的G1数量G2。
问问题
10445 次
4 回答
21
我认为图形编辑距离是您正在寻找的衡量标准。
图形编辑距离衡量将一个图形转换为另一个图形的最小图形编辑操作数，允许的图形编辑操作包括：
- 插入/删除一个孤立的顶点
- 插入/删除边缘
- 更改顶点/边的标签（如果标记图）
然而，计算两个图之间的图编辑距离是 NP 难的。最有效的计算算法是基于 A* 的算法，还有其他次优算法。
于 2013-06-10T11:17:42.893 回答
9
你应该看一下论文图形编辑距离的调查
于 2013-09-14T14:00:14.367 回答
4
对于一般图表，正如其他人在他们的回答中提到的那样，它是一个 NP 完全问题。但是对于树形图，有众所周知的多项式算法。其中最著名的可能是 1989 年发表的“张莎莎”算法。
于 2013-05-16T16:43:20.097 回答
3
笔记：
Levenshtein 距离（或编辑距离）在两个字符串之间
但在 Graph 中，您应该至少在 N 之间搜索！您找到每个边和顶点的标识的位置。您可以通过唯一索引轻松比较两个图，但主要问题是为每个顶点和边定义身份。这个问题（在两个图中找到他们可以转换的每个顶点和边的身份）非常困难，被称为同构问题（NP-完全）。您可以搜索关于同构图。
于 2013-05-06T14:47:56.507 回答