python - 在 python 中实现 Bron–Kerbosch 算法

Question

对于一个大学项目，我正在尝试实现 Bron–Kerbosch algorithm ，即列出给定图中的所有最大团。

我正在尝试实现第一个算法(不旋转)，但我的代码在 Wikipedia's example 上测试后并没有给出所有答案。 ，到目前为止我的代码是:

# 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 阅读更多相关信息.