algorithm - 图中的子图

Question

我有一个主图和另一个小图，假设小图可以在主图中重复为具有一定相似度的子图（不一定是相同的小图） 什么是找到它们的好算法（或 Java 库）全部？

Answer 1

我认为您正在尝试解决已知为 NP 完全的子图同构问题。这意味着，可能没有快速算法可以满足您的需求。您对相似性（而不仅仅是同构）的要求只会增加另一种复杂性。

Wikipedia 页面讨论了 Ulmann 的算法，该算法在多项式时间内（快速）解决了某些类别的图的这个问题，您可以尝试一下。