logo标签列表

Bron-Kerbosch算法用于寻找团。

algorithmgraph-theoryclique
11

请问在网络上哪里可以找到关于Bron-Kerbosch算法寻找完全子图的解释，或者能否在这里进行解释?

我知道它是在《算法457：查找无向图中所有团的算法》一书中发表的，但我找不到免费的资源来描述算法。

我不需要该算法的源代码，我需要的是它如何运作的解释。

2
Alex，我敢打赌那篇帖子被“告诉我，在网上哪里...”这样的问题所贬低。不要让别人替你完成工作，只需要请他们澄清它是如何工作的即可。 - aku
我的意思是在网上，而不是在书本上，因为我将在接下来的两周内无法访问图书馆 :( - Alex Reitbort
2
与其要求提供源代码，不如说“告诉我...是如何工作的”，并描述具体困惑的地方，这样回答（以及你问题的背景）将为将来遇到类似问题的其他人提供帮助。这里接受的答案几乎没有用处。 - SimonJ
7个回答
8
该链接已失效。 - macros
4
请问您能否将它发送到我的邮箱 joker99+bron@gmail.com？ - Alex Reitbort
2

这里有一个算法链接，我已经使用Java中的链表作为集合R、P、X进行了重写，并且它运行得非常好（根据该算法进行集合操作时，使用函数“retainAll”是一件好事）。

我建议您在重新编写算法时考虑优化问题。

2

我也在尝试理解Bron-Kerbosch算法，所以我用Python编写了自己的实现。它包括一个测试用例和一些注释。希望这可以帮到你。

class Node(object):

    def __init__(self, name):
        self.name = name
        self.neighbors = []

    def __repr__(self):
        return self.name

A = Node('A')
B = Node('B')
C = Node('C')
D = Node('D')
E = Node('E')

A.neighbors = [B, C]
B.neighbors = [A, C]
C.neighbors = [A, B, D]
D.neighbors = [C, E]
E.neighbors = [D]

all_nodes = [A, B, C, D, E]

def find_cliques(potential_clique=[], remaining_nodes=[], skip_nodes=[], depth=0):

    # To understand the flow better, uncomment this:
    # print (' ' * depth), 'potential_clique:', potential_clique, 'remaining_nodes:', remaining_nodes, 'skip_nodes:', skip_nodes

    if len(remaining_nodes) == 0 and len(skip_nodes) == 0:
        print 'This is a clique:', potential_clique
        return

    for node in remaining_nodes:

        # Try adding the node to the current potential_clique to see if we can make it work.
        new_potential_clique = potential_clique + [node]
        new_remaining_nodes = [n for n in remaining_nodes if n in node.neighbors]
        new_skip_list = [n for n in skip_nodes if n in node.neighbors]
        find_cliques(new_potential_clique, new_remaining_nodes, new_skip_list, depth + 1)

        # We're done considering this node.  If there was a way to form a clique with it, we
        # already discovered its maximal clique in the recursive call above.  So, go ahead
        # and remove it from the list of remaining nodes and add it to the skip list.
        remaining_nodes.remove(node)
        skip_nodes.append(node)

find_cliques(remaining_nodes=all_nodes)
0
我已经实现了论文中指定的两个版本。我发现，如果使用递归解决未优化的版本，可以帮助更好地理解算法。 这是第一版（未优化）的Python实现：
def bron(compsub, _not, candidates, graph, cliques):
    if len(candidates) == 0 and len(_not) == 0:
        cliques.append(tuple(compsub))
        return
    if len(candidates) == 0: return
    sel = candidates[0]
    candidates.remove(sel)
    newCandidates = removeDisconnected(candidates, sel, graph)
    newNot = removeDisconnected(_not, sel, graph)
    compsub.append(sel)
    bron(compsub, newNot, newCandidates, graph, cliques)
    compsub.remove(sel)
    _not.append(sel)
    bron(compsub, _not, candidates, graph, cliques)

然后你调用这个函数：

graph = # 2x2 boolean matrix
cliques = []
bron([], [], graph, cliques)

变量cliques将包含找到的团。

一旦你理解了这个，实现优化就很容易了。

算法的第一个版本甚至应该检查是否包含了每个候选元素的邻居元素，并在这种情况下进行回溯。 - Andreas Vinter-Hviid
0
Boost::Graph有一种优秀的Bron-Kerbosh算法实现，可以去看看。
0
我找到了2个Java实现和一个C实现。也许它可以工作，但我还需要了解它是如何工作的，源代码没有很多关于它如何工作的注释。 - Alex Reitbort
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接