作者热门文章
- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
我正在尝试实现 Bron-Kerbosch 算法,这是一种用于查找派系的递归算法。我设法达到了一个点,它返回了正确数量的派系,但是当我打印它们时,它们不正确 - 添加了额外的节点。我在这里遗漏了什么明显的东西吗?
我正在使用邻接表结构:
vector< list<int> > adjacency_list;
我按以下方式添加边的位置:
void graph::addEdge(int i1,int i2){
//as this is an undirected graph
adjacency_list[i1].push_back(i2);
adjacency_list[i2].push_back(i1);
}
主要算法如下:
void graph::BronKerbosch(vector<int> R, vector<int> P, vector<int> X){
if (P.empty() && X.empty()){
result_cliques.insert(R);
}
// vector <int> tmpVerts = P;
for(std::vector<int>::iterator it = P.begin(); it != P.end();) {
vector<int> intersection = {}, intersectionX = {};
int node = *it;
//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());
P.erase(it);
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";
}
}
以下图形输入的输出问题:
1 2
1 3
2 3
是,这段代码返回:
(1 2 3 )
(1 2 3 4 )
(1 2 3 4 5 )
而它应该返回(为此使用 python):
(1 2 3 )
(2 4 )
(2 5 )
非常感谢您的帮助。
最佳答案
在wikipedia page ,递归调用如下所示:
for each vertex v in P:
BronKerbosch1(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v))
...
在问题的代码中,您在递归调用之前执行了 R.push_back(node)
,但该节点将在所有后续迭代中包含在 R
中循环,这是不正确的。
即如下指令:
R.push_back(node);
BronKerbosch(R,intersection,intersectionX);
可能应该在递归调用之后紧跟一个 R.pop_back(node)
。
关于C++ 遍历 vector 拷贝,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/44005413/
我是一名优秀的程序员,十分优秀!