C++ 中的 Bron Kerbosch 算法 [英] Bron Kerbosch algorithm in c++
问题描述
我一直在练习我的 C++ 算法知识,并且卡在了标准的 BK 实现上.该算法输出太多派系,我似乎不明白为什么.我将图表示为邻接表:
I've been practicing my C++ algorithm knowledge, and got stuck on the standard BK implementation. The algorithm outputs way too many cliques, and I doesn't seem to figure out why. I represented the graph as an adjacency list:
vector< list<int> > adjacency_list;
我的 BK 函数看起来像:
My BK function looks like:
void graph::BronKerbosch(vector<int> R, vector<int> P, vector<int> X){
if (P.empty() && X.empty()){
result_cliques.insert(R);
}
for (int node : P){
vector<int> intersection = {}, intersectionX = {};
//N(P)
for (int nodeP : adjacency_list[node]){
for (int node2 : P){
if (nodeP == node2){
intersection.push_back(nodeP);
}
}
//N(X)
for (int node3 : X){
if (nodeP == node3){
intersectionX.push_back(nodeP);
}
}
}
R.push_back(node);
BronKerbosch(R,intersection,intersectionX);
P.erase(remove(P.begin(),P.end(),node),P.end());
X.push_back(node);
}
}
我称之为:
void graph::run_BronKerbosch(){
vector<int> R,P,X;
for (int i=1; i < adjacency_list.size(); i++) {
P.push_back(i);
}
BronKerbosch(R,P,X);
cout << "................\nClassic: " << result_cliques.size() << endl;
for (auto clique : result_cliques){
cout << "(";
for (int node : clique){
cout << node <<" ";
}
cout << ")\n";
}
}
我正在尝试实现算法的基本版本,但我似乎在这里遗漏了一个细节.问题出在:
I am trying to implement the basic version of the algorithm, but I seem to be missing a detail here. Is the problem in:
for (int node : P){
我应该以某种方式在第一个循环中使用 P 的副本吗?(我在相关问题中看到过这一点)
Should I somehow use a copy of P for this first loop? (I've seen this in a related issue)
感谢您的帮助.
推荐答案
是的,您应该复制一份,除非您提前预留空间以保证不会重新分配1.(请注意,C++ foreach
实现在幕后归结为一堆迭代器.)
Yes you should take a copy, unless you reserve space in advance so you can guarantee there is no reallocation1. (Note that the C++ foreach
implementation boils down to a bunch of iterators under the hood.)
如果我是你,我会改写为老式的 for
循环,使用 std::size_t
(超级学徒2 将使用 std::vector
) 来索引您当前感兴趣的向量元素.当 P<的最后一个元素时终止/code> 已阅读.
I'd recast to an old-fashioned for
loop if I were you, iterating over the vector using an std::size_t
(the super-pedants2 would use a std::vector<int>::size_type
) to index the vector element you're currently interested in. Terminate when the final element of P
has been read.
参考文献:
2C++ for-loop -size_type vs. size_t
这篇关于C++ 中的 Bron Kerbosch 算法的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!