algorithm - 一种从图中获取所有连通子图的算法，它是否正确？

Question

我尝试找到一种快速算法来获取所有连接的子图，形成子图长度受限的无向图。简单的方法，例如每个顶点的 BFS 或 DFS 都会生成大量等于子图，因此在每次算法迭代中我们都必须修剪子图集。我在俄罗斯数学论坛找到了an algorithm :

Procedure F(X,Y)
//X set of included vertices 
//Y set of forbidden vertices to construct new subgraph
1.if |X|=k, then return;
2.construct a set T[X] of vertices that adjacent to vertices from X (If X is a empty set, than T[X]=V), but not belong to the sets X,Y;
3.Y1=Y;
4.Foreach v from T[X] do:
__4.1.X1=X+v;
__4.2.show subgraph X1;
__4.3.F(X1,Y1);
__4.4.Y1=Y1+v;

Initial call F(X,Y):
X, Y = empty set;
F(X,Y); 

该算法的主要思想是使用“禁止集”，因此不需要剪枝，该算法的作者表示，它比基于剪枝等于子图的解决方案快300倍。但我还没有找到任何证据证明这个算法是正确的。

更新: 找到了更有效的解决方案here

Answer 1

这是我认为是您的原始算法的 Python 实现:

from collections import defaultdict

D=defaultdict(list)
def addedge(a,b):
    D[a].append(b)
    D[b].append(a)

addedge(1,2)
addedge(2,3)
addedge(3,4)

V=D.keys()
k=2

def F(X,Y):
    if len(X)==k:
        return
    if X:
        T = set(a for x in X for a in D[x] if a not in Y and a not in X)
    else:
        T = V
    Y1=set(Y)
    for v in T:
        X.add(v)
        print X
        F(X,Y1)
        X.remove(v)
        Y1.add(v)

print 'original method'
F(set(),set())

F 生成大小 <=k 的所有连通子图，其中子图必须包含 X 中的顶点(连通子图本身)，并且不得包含 Y 中的顶点。

我们知道，要在子图中包含另一个顶点，我们必须使用连接的顶点，这样我们就可以根据最终子图中第一个连接的顶点 v 的标识进行递归。禁止集意味着我们确保无法生成子图的第二个副本，因为该副本必须使用 v，但 v 位于禁止集中，因此无法再次使用。

因此，从表面的分析来看，该算法显得高效且正确。