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