我一直在练习C ++算法知识,并停留在标准BK实现上。该算法输出的派别太多,我似乎也不清楚原因。我将图表示为邻接表:
vector< list<int> > adjacency_list;
我的BK函数如下所示:
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";
}
}
我正在尝试实现该算法的基本版本,但是这里似乎缺少一个细节。问题出在:
for (int node : P){
我是否应该为此第一个循环使用P的副本?(我已经在相关问题中看到了这一点)
感谢您的任何帮助。
是的,除非您提前预留空间,否则您应该复印一份,这样可以保证没有重新分配1。(请注意,C ++foreach
实现归结为底层的一堆迭代器。)
for
如果您是我,我将重铸到一个老式的循环中,使用std::size_t
(超级-脚2使用a std::vector<int>::size_type
)遍历向量以索引您当前感兴趣的向量元素。在的最后一个元素P
具有被阅读。
参考文献:
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句