子图枚举

  • Z时代
  • 2024-01-10
  • 分类：问答

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

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

回答：

该问题在该问题的公认答案中有更好的答案。它避免了@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))

以上是 子图枚举 的全部内容， 来源链接： utcz.com/qa/410584.html

回到顶部