編輯兩個圖之間的距離

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