Bonjour,
Je dois trouver toutes les cliques maximales dans un graphe générer aléatoirement.
Je fais la matrice d'adjacence, puis je lance mon algo de BronKerbosch :
vector<int> intersect(vector<int> A, vector<int> B){
vector<int> I;
for(int i = 0; i<A.size(); i++){
for(int j = 0; i<B.size(); i++){
if(A[i]==B[j]) I.push_back(A[i]);
}
}
return I;
}
vector<int> suppr(vector<int> A, int b){
for(int i = 0; i<A.size(); i++){
if(A[i]==b) A.erase(A.begin()+i);
}
return A;
}
vector<int> getV(int v){
vector<int> V;
for(int i = 0; i<n; i++){
if(M_adj[v][i]==1) V.push_back(i);
}
return V;
}
void BronKerboschWithoutPivot(vector<int> R, vector<int> P, vector<int> X){
if((P.size() == 0) && (X.size() == 0) && (R.size()>1)){
printf("Clique maximale :");
for (int i=0; i<R.size(); i++){ printf(" %d ", R[i]); }
printf("\n");
return;
}
vector<int> P1;
for(int i = 0; i < P.size(); i++){ P1.push_back(P[i]);}
for(int i = 0; i < P.size(); i++){
int v = P[i];
vector<int> V = getV(v);
R.push_back(v);
BronKerboschWithoutPivot(R,intersect(P1,V),intersect(X,V));
R = suppr(R,v);
P1 = suppr(P1,v);
X.push_back(v);
}
}
Cependant, cela me rend pas le résulat attendu et je ne trouve pas mon erreur.
J'ai trouvé mon erreur : j'avais fait un copié-collé d'un for() et j'ai oublié de modifié la variable dans toutes la conditions, resultat, je me retrouvé avec for(int j = 0; i<...; i++)