有效地找到所有连接子图 [英] Efficiently find all connected subgraphs

问题描述

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

Is there an efficient(*) algorithm to find all the connected (induced) subgraphs of a connected undirected vertex-labelled graph?

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

(*) I appreciate that, in the general case, any such algorithm may have O(2^n) complexity because, for a clique (Kn), there are 2^n connected subgraphs. However, the graphs I'm typically dealing with will have far fewer connected subgraphs, so I'm looking for a way to generate them without having to consider all 2^n subgraphs and throw away those that aren't connected (as in the solution to this question).

这已运行时间这是线性的解的数目（例如，它可以从图的结构直接产生的解，而不会浪费时间考虑所有的非解）的算法显然是理想的。一个额外的步骤，是多项式在节点的数量就可以了太（如pre-计算图的传递闭包 - 不，我认为会在这种情况下帮助）。

An algorithm that has running time that's linear in the number of the solutions (i.e. it can generate the solutions directly from the structure of the graph without wasting time considering all the non-solutions) would obviously be ideal. An additional step that's polynomial in the number of nodes would be fine too (e.g. pre-computing the transitive closure of the graph - not that I think that would help in this case).

另外，证明了不存在这样的解决办法，至少让我出我的痛苦。

Alternatively, a proof that there is no such solution would at least put me out of my misery.

推荐答案

在递归伪code，2 ^ N算法

In recursive pseudocode, the 2^n algorithm is

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倍的数量）。

It doesn't matter which vertex v is chosen; we even can choose differently in two sibling calls. We exploit this freedom to obtain an almost linear-time algorithm (n times the number of solutions) by pruning the recursion tree.

如果 subsetSoFar 是空的，那么选择仍然是不受约束的。否则，我们选择 v 为邻近的顶点之一 subsetSoFar 。如果没有这样的 v 的存在，我们得到 subsetSoFar 和回报，因为有这个子树没有其他的解决方案。

If subsetSoFar is empty, then the choice is still unconstrained. Otherwise, we choose v to be adjacent to one of the vertices in subsetSoFar. If no such v exists, we yield subsetSoFar and return, since there are no other solutions in this subtree.

请注意新的不变量 subsetSoFar 总是连接，这样我们就可以消除明确的连通性测试。我们做O（n），在递归树的每个节点的工作（天真地为O（n ^ 2），但我们可以保持在设定相邻顶点的增量），这是完全二叉树，其叶各得到唯一解，所以总工作是按权利（记得，内部节点的数量比叶数少一个）。

Note the new invariant that subsetSoFar is always connected, so we can eliminate the explicit connectivity test. We do O(n) work at each node of the recursion tree (naively O(n^2) but we can maintain the set of adjacent vertices incrementally), which is complete binary and whose leaves each yield exactly one solution, so the total work is as claimed (recall that the number of internal nodes is one less than the number of leaves).

在考虑新的不变量，没有断开子图产生。

On account of the new invariant, no disconnected subgraph is yielded.

每个连通子的产生。一组顶点s表示诱导连通子图，按照同意S.这是不可能S的真子集有没有邻居，S的其余部分树枝，所以S没有修剪。

Each connected subgraph is yielded. For a set of vertices S that induces a connected subgraph, follow the branches that agree with S. It's not possible for a proper subset of S to have no adjacency to the rest of S, so S is not pruned.

新的伪code是如下。 N（V）表示集邻居诉。

The new pseudocode is as follows. N(v) denotes the set of neighbors of 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相交邻居，这是我为没做为了清楚。多，如果你能够利用文字并行通过重新presenting图形作为其中每一行存储为一个或两个单词位图的邻接矩阵这种优化可能是不值得。

for graphs of max degree O(1), we can make this truly linear-time by maintaining verticesNotYetConsidered intersect neighbors, which I didn't do for the sake of clarity. This optimization probably isn't worth much if you exploit word-parallelism by representing the graph as an adjacency matrix where each row is stored as a one- or two-word bitmap.

这篇关于有效地找到所有连接子图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！