圖中的子圖

Question

我有一個主圖和另一個小圖，假設小圖可以在主圖中作爲具有相似度的子圖重複（不一定是同一個小圖） 什麼是好算法（或Java庫）找到它們全部？

Answer 1

我想你正試圖解決Subgraph Isomorphism Problem這是已知是NP完成。這意味着，可能沒有快速的算法來做你需要的。您對相似性的要求（不僅是同構）只會增加另一個複雜性。

維基百科頁面討論了烏爾曼的算法，該算法可以在多項式時間（快速）中解決某些類圖的這個問題，您可以嘗試一下。