子图枚举

Question

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

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

Answer 1

这个问题在公认的答案，以更好的回答这个问题。它避免了@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))