graph - 检查给定图是否是另一个图的子图的算法

Question

很难说出这里问的是什么。这个问题模棱两可、含糊不清、不完整、过于宽泛或言辞激烈，无法以目前的形式合理回答。如需帮助澄清此问题以便可以重新打开，visit the help center .




10年前关闭。




我假设我们有 2 个标记图 G 和 T，算法确定 G 是否是 T 的子图以及主图 T 和子图 G 中的相应顶点是否应该具有相同的标签

Answer 1

这个问题叫做 "subgraph isomorphism"并且它是 NP 完全的(因此可能很难)。你需要一个通用的解决方案，还是只需要一个特定的图形 G ?第二种情况要容易得多。有一些关于算法的一般信息here . Boost Graph 库中有一种算法(实际上，用于更一般的问题)的版本(参见文档 here)。