在python中实现Bron-Kerbosch算法

Question

对于大学项目,我正在尝试实施Bron-Kerbosch算法,即列出给定图形中的所有最大派系.

我正在尝试实现第一个算法(没有透视),但我的代码在维基百科的例子上测试后没有产生所有答案,到目前为止,我的代码是:

# dealing with a graph as list of lists 
graph = [[0,1,0,0,1,0],[1,0,1,0,1,0],[0,1,0,1,0,0],[0,0,1,0,1,1],[1,1,0,1,0,0],[0,0,0,1,0,0]]


#function determines the neighbors of a given vertex
def N(vertex):
    c = 0
    l = []
    for i in graph[vertex]:
        if i is 1 :
         l.append(c)
        c+=1   
    return l 

#the Bron-Kerbosch recursive algorithm
def bronk(r,p,x):
    if len(p) == 0 and len(x) == 0:
        print r
        return
    for vertex in p:
        r_new = r[::]
        r_new.append(vertex)
        p_new = [val for val in p if val in N(vertex)] # p intersects N(vertex)
        x_new = [val for val in x if val in N(vertex)] # x intersects N(vertex)
        bronk(r_new,p_new,x_new)
        p.remove(vertex)
        x.append(vertex)


    bronk([], [0,1,2,3,4,5], [])

任何帮助,为什么我只得到答案的一部分？

Answer 1

Python正在变得混乱,因为您正在修改它迭代的列表.

更改

for vertex in p:

至

for vertex in p[:]:

这将导致它迭代p的副本.

您可以在http://effbot.org/zone/python-list.htm上阅读更多相关信息.

Answer 2

正如@VaughnCato正确地指出错误正在迭代P[:].我认为值得注意的是,你可以"产生"这个结果,而不是打印,如下所示(在这个重构的代码中):

def bronk2(R, P, X, g):
    if not any((P, X)):
        yield R
    for v in P[:]:
        R_v = R + [v]
        P_v = [v1 for v1 in P if v1 in N(v, g)]
        X_v = [v1 for v1 in X if v1 in N(v, g)]
        for r in bronk2(R_v, P_v, X_v, g):
            yield r
        P.remove(v)
        X.append(v)
def N(v, g):
    return [i for i, n_v in enumerate(g[v]) if n_v]

In [99]: list(bronk2([], range(6), [], graph))
Out[99]: [[0, 1, 4], [1, 2], [2, 3], [3, 4], [3, 5]]

如果有人在将来寻找Bron-Kerbosch算法实现...