C++ 中的 Bron Kerbosch 算法

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

感谢您的任何帮助。

Yes you should take a copy, unless you reserve space in advance so you can guarantee there is no reallocation¹. (Note that the C++ foreach implementation boils down to a bunch of iterators under the hood.)

I'd recast to an old-fashioned for loop if I were you, iterating over the vector using an std::size_t (the super-pedants² 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.

参考：

¹Iterator invalidation rules https://stackoverflow.com/questions/6438086/iterator-invalidation-rules

²C++ for-loop - size_type vs. size_t https://stackoverflow.com/questions/4849678/c-for-loop-size-type-vs-size-t