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的副本在第一個循環？ （我在相關問題中看到過這個）

謝謝你的幫助。

Answer 1

是的，你應該採取的副本，除非事先你儲備空間，這樣可以保證沒有再分配。 （請注意，C++ foreach實施歸結到引擎蓋下一堆迭代器）。

我重鑄一個老式的for循環，如果我是你，遍歷使用std::size_t（超的矢量花生將使用vector<int>::size_type）來索引你當前感興趣的矢量元素。當P的最後一個元素被讀取時終止。

---

參考文獻：

Iterator invalidation rules

C++ for-loop - size_type vs. size_t