有效地找到所有连接的诱导子图(Efficiently find all connected indu

是否有一个有效的（*）算法来找到所有的连接（感应）无向连通顶点标记图形的子图？

（*）予理解的是，在一般情况下，任何这样的算法可以具有O（2 ^ n）的复杂性，因为，对于派（KN），有2 ^ n的连接子图。不过，我通常处理图形将有少得多的连通子，所以我在寻找一种方式来产生，而不必考虑所有2 ^ N子图，扔掉那些没有连接（如解决这个问题）。

已运行的时间是在解决方案的数量直线（即它可以从图的结构直接生成解决方案，而浪费时间考虑所有非解决方案）的算法显然是理想的。这是多项式的额外步骤中的节点的数量将被罚款过（例如预先计算图的传递闭包 - 不，我认为会在这种情况下帮助）。

或者，证明没有这样的解决方案将至少把我从我的痛苦。

在递归的伪代码中，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 intersect neighbors ，我没有为清楚起见做。这种优化可能是不值得多，如果你是代表该图中，其中每一行被存储为一个或两个词的位图的邻接矩阵利用字并行。