C++中的Bron-Kerbosch算法

Question

我一直在练习我的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的副本吗？（我在相关问题中看到过这个方法）

非常感谢您的帮助。

- sdgaw erzswer

---

你最终是如何解决的？你在哪里添加了这个 P 的副本？ - Miguel Duran Diaz

Answer 1

是的，除非您提前预留空间以确保没有实际重新分配¹，否则您应该取一个副本。(请注意，C++ foreach 实现在幕后归结为一堆迭代器。)

如果我是你，我会把它改写成一个老式的 for 循环，使用 std::size_t (超级严谨的人会使用 std::vector<int>::size_type) 来索引您当前感兴趣的向量元素。当读取完 P 的最后一个元素时终止。

---

参考文献：

¹迭代器失效规则

²C++ for 循环 - size_type vs. size_t

- Bathsheba

---

感谢您的深入评论，如果我理解正确，以下代码应该可以解决问题：for(std::vector<int>::size_type i = 0; i != v.size(); i++) { /* std::cout << someVector[i]; ... */ }。 - sdgaw erzswer

没问题。push_back 不会使 i 失效，即使 i 在最后一个元素上。 - Bathsheba

运行非常顺利！谢谢。 - sdgaw erzswer

@Bathsheba 为什么他要使用副本？我遇到了类似的问题，但不明白为什么需要一个副本。 - Miguel Duran Diaz