图中的子图
我有一个主图和另一个小图，假设小图可以在主图中作为具有一定相似度的子图重复（不一定是相同的小图） 有什么好的算法（或 Java 库）可以找到它们？
I have a main graph and another small graph, suppose that the small graph could be repeated in the main graph as a subgraph with a degree of similarity(not necessarily the same small graph)
What's a good algorithm (or Java library) to find them all?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
我认为您正在尝试解决已知为 NP 完全的 子图同构问题。这意味着，可能没有快速算法可以满足您的需求。您对相似性（而不仅仅是同构）的要求只会增加另一种复杂性。
维基百科页面讨论了乌尔曼算法，该算法可以在多项式时间内（快速）针对某些类别的图解决此问题，您可以尝试一下。
I think you are trying to solve the Subgraph Isomorphism Problem which is known to be NP-complete. That means, there is likely no fast algorithm to do what you need. Your requirement of similarity (and not only isomorphism) only adds another complexity.
The Wikipedia page talks about Ulmann's algorithm that solves this problem in polynomial time (fast) for certain classes of graphs, you might give it a try.