在递归伪代码中，2 ^ n算法为

GenerateAndTest(verticesNotYetConsidered, subsetSoFar):
    if verticesNotYetConsidered is empty:
        yield subsetSoFar if it induces a connected subgraph
    else:
        choose a vertex v in verticesNotYetConsidered
        GenerateAndTest(verticesNotYetConsidered - {v}, subsetSoFar)
        GenerateAndTest(verticesNotYetConsidered - {v}, subsetSoFar union {v})

选择哪个顶点v无关紧要；我们甚至可以在两个同级通话中选择不同的选项。通过修剪递归树，我们利用这种自由来获得近似线性时间的算法（解数的n倍）。

如果subsetSoFar为空，则选择仍然不受限制。否则，我们选择v与中的一个顶点相邻subsetSoFar。如果不v存在这种情况，我们将屈服subsetSoFar并返回，因为此子树中没有其他解决方案。

请注意subsetSoFar始终保持连接的新不变式，因此我们可以消除显式连接性测试。我们在递归树的每个节点上执行O（n）工作（天真的O（n ^
2），但是我们可以递增地维护相邻顶点的集合），它是完全二元的，并且每个叶子的叶子都给出一个唯一的解，因此总和按照要求进行工作（回想一下，内部节点的数量比叶子的数量少一）。

由于存在新的不变性，因此不会产生任何断开的子图。

产生每个连接的子图。对于诱发连接子图的一组顶点S，遵循与S一致的分支。S的适当子集与S的其余部分不相邻是不可能的，因此S不会被修剪。

新的伪代码如下。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))

编辑：对于最大度为O（1）的图，我们可以通过保持来实现真正的线性时间，verticesNotYetConsidered intersectneighbors为清楚起见，我没有这样做。如果您通过将图表示为邻接矩阵（每一行存储为一个或两个单词的位图）来利用单词并行性，则此优化可能不值一提。