有效地找到所有连接的感应子图 [英] Efficiently find all connected induced subgraphs
问题描述
，在一般情况下，任何这样的算法可能具有O（2 ^ n）复杂度，因为对于一个团（Kn），存在2 ^ n个连接的子图。然而，我通常处理的图将会有更少的连接子图，所以我正在寻找一种方法来生成它们，而不必考虑所有2 ^ n子图并丢弃那些未连接的子图（如解决方案到这个问题）。
一种算法运行时间在解决方案的数量上是线性的（即它可以直接从图的结构生成解决方案，而不会浪费时间考虑所有非解决方案）显然是理想的。在节点数量中多项式的附加步骤也可以（例如，预先计算图的传递闭包 - 并非我认为这对这种情况有帮助）。
另外，证明没有这样的解决方案至少可以让我摆脱不幸。
在递归伪代码中，2 ^ n算法是 GenerateAndTest（verticesNotYetConsidered，subsetSoFar） ：
如果verticesNotYetConsidered为空：
产生subsetSoFar如果它引发了一个连接的子图
else：
在verticesNotYetConsidered中选择一个顶点v
GenerateAndTest（verticesNotYetConsidered - {v}， subsetSoFar）
GenerateAndTest（verticesNotYetConsidered - {v}，subsetSoFar union {v}）
它选择哪个顶点v并不重要;我们甚至可以在两个兄弟电话中选择不同的方式。如果 / code>为空，那么选择仍然不受限制。否则，我们选择 每个连接的子图都被生成。对于导致连接子图的一组顶点S，遵循与S一致的分支.S的一个子集不可能与S的其余部分没有邻接关系，所以S不会被修剪。 新的伪代码如下。 Is there an efficient(*) algorithm to find all the connected (induced) subgraphs of a connected undirected vertex-labelled graph? (*) 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). 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. In recursive pseudocode, the 2^n algorithm is 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. If Note the new invariant that On account of the new invariant, no disconnected subgraph is yielded. 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. The new pseudocode is as follows. EDIT: for graphs of max degree O(1), we can make this truly linear-time by maintaining 这篇关于有效地找到所有连接的感应子图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！ subsetSoFar
v 与 subsetSoFar 中的某个顶点相邻。如果不存在这样的 v ，那么我们会得到 subsetSoFar 并返回，因为在这个子树中没有其他解决方案。请注意， subsetSoFar 总是连通的新不变量，所以我们可以消除显式连通性测试。我们在递归树的每个节点上进行O（n）工作（天真地O（n ^ 2），但我们可以递增地维护相邻顶点的集合），这是完全二元的，其叶子每个产生恰好一个解，所以总数工作就像声称的那样（回想起内部节点的数量比叶子的数量要少一个）。
由于新的不变性，没有断开连接的子图。
N（v）表示 v 的邻居集合。
GenerateConnectedSubgraphs（verticesNotYetConsidered，subsetSoFar，neighbors）：，为了清晰起见，我没有这样做。如果您通过将图形表示为邻接矩阵来利用字平行度，那么这种优化可能就不值钱了。每行存储为一个或两个字的位图。
如果subsetSoFar为空：
let candidates = verticesNotYetConsidered
else
let candidates = verticesNotYetConsidered交叉邻居
如果候选者为空：
产生subsetSoFar
else：
从候选者中选择一个顶点v
GenerateConnectedSubgraphs（verticesNotYetConsidered - {v}，
子集SoFar，
邻居）
GenerateConnectedSubgraphs（verticesNotYetConsidered - {v}，
subsetSoFar union {v}，
neighbour Union union N（v））
verticesNotYetConsidered来实现这个真正的线性时间相交邻居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})
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 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).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))
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.
