gpt4 book ai didi

algorithm - Bron-Kerbosch 算法的迭代版本?

转载 作者:塔克拉玛干 更新时间:2023-11-03 04:23:09 24 4
gpt4 key购买 nike

Bron–Kerbosch algorithm是一种列出图的所有最大派系的方法。我最近成功地实现了这个算法只是为了好玩。缺点是该算法是递归的,因此只能在小图上运行,直到堆栈溢出。

应该可以使算法完全迭代。考虑维基百科上的基本版本(无旋转)。算法的迭代版本在伪代码中是什么样子的?有描述吗?

我正在想象一个堆栈数据结构来模拟递归。我还应该有一个循环来测试 P 和 X 是否为空,但我没有看到完整的答案。

最佳答案

The recursive version is given in Wikipedia像这样:

BronKerbosch1(R, P, X):
if P and X are both empty:
report R as a maximal clique
for each vertex v in P:
BronKerbosch1(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v))
P := P \ {v}
X := X ⋃ {v}

为了模拟递归,我们只需要使用堆栈跟踪三个变量:

BronKerbosch(P):
S := empty stack
S.push({}, P, {})
while S is not empty:
R, P, X := S.pop()
if P and X are both empty:
report R as a maximal clique
if P is not empty:
v := some vertex in P
S.push(R, P \ {v}, X ⋃ {v})
S.push(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v))

关于algorithm - Bron-Kerbosch 算法的迭代版本?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/28406314/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com