algorithm - 子图枚举

Question

什么是枚举父图的所有子图的有效算法。在我的特定情况下，父图是一个分子图，因此它将被连接并且通常包含少于 100 个顶点。

编辑:我只对连接的子图感兴趣。

Answer 1

这个问题在this question的接受答案中有更好的答案.它避免了在@ninjagecko 的回答中标记为“您填写上述功能”的计算复杂步骤。它可以有效地处理具有多个环的化合物。

有关完整详细信息，请参阅链接的问题，但这里是摘要。 (N(v) 表示顶点 v 的邻居集合。在“选择顶点”步骤中，您可以选择任意顶点。)

GenerateConnectedSubgraphs(verticesNotYetConsidered, subsetSoFar, neighbors):
    if subsetSoFar is empty:
        let candidates = verticesNotYetConsidered
    else
        let candidates = verticesNotYetConsidered intersect neighbors
    if candidates is empty:
        yield subsetSoFar
    else:
        choose a vertex v from candidates
        GenerateConnectedSubgraphs(verticesNotYetConsidered - {v},
                                   subsetSoFar,
                                   neighbors)
        GenerateConnectedSubgraphs(verticesNotYetConsidered - {v},
                                   subsetSoFar union {v},
                                   neighbors union N(v))