0

我实现了 BK 算法 ( https://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm ) <- 在 C++ 中没有旋转版本，但没有按预期工作。代码是：

void UndirectedGraph::clique(vector<string> R, vector<string> P, vector<string> X) {
    // Revisa si están vacíos, lo que implicaría que hay un clique
    if (P.empty() && X.empty()){
        cout << "Clique found!" << endl;
        for (const auto& it: R)
            cout << it << " " << endl;
    }
    // Crea una copia de P para evitar problemas en el iterador
    vector<string> pCopy(P);
    for (const auto& v: pCopy){
        vector<string> unionSet;
        vector<string> intersectionSetPNv;
        vector<string> intersectionSetXNv;
        vector<string> neighborsP;
        vector<string> vVector = {v};
        // Obtiene los vecinos de P
        for (const auto& neighbors: users[v]) neighborsP.push_back(neighbors);
        // Obtiene la unión de R y U
        set_union(R.begin(), R.end(), vVector.begin(), vVector.end(), back_inserter(unionSet));
        // Obtiene intersección P y N(v)
        set_intersection(P.begin(), P.end(), neighborsP.begin(), neighborsP.end(), back_inserter(intersectionSetPNv));
        set_intersection(X.begin(), X.end(), neighborsP.begin(), neighborsP.end(), back_inserter(intersectionSetXNv));
        clique(unionSet, intersectionSetPNv, intersectionSetXNv);
        vector<string> PminusV;
        vector<string> XunionV;
        // Obtiene P - {v} y N u {v}
        set_difference(P.begin(), P.end(), vVector.begin(), vVector.end(), inserter(PminusV, PminusV.begin()));
        set_union(X.begin(), X.end(), vVector.begin(), vVector.end(), back_inserter(XunionV));

        P = vector<string> (PminusV);
        X = vector<string> (XunionV);
    }
}

预期产出集团：ABC

AE

CBDF

ED

实际输出派系：ABC

AE

CBDF

CDF <- 这不应该存在

ED

一个相关的问题在这里：Bron Kerbosch algorithm in c++ 解决方案是使用 P 的副本（我正在这样做，虽然我不完全理解为什么需要它）。我测试它的图表是这样的：

在此处输入图像描述

注意： users 被定义为 a: map<string, vector<string>>，所以 users[v] 实际上是一个包含 v 所有邻居的向量。

完整的类实现： https ://pastebin.com/dRXrC0Rf

声明类后重现输出的代码： https ://pastebin.com/vV6ppunF

4

0 回答 0