Поиск всех кликов неориентированного графа

Question

Как я могу перечислить все клики неориентированного графа? (Не все максимальные клики, как алгоритм Брон-Кербоша)

Answer 1

Оптимальное решение такое, потому что в полном графе 2^n клик. Рассмотрим все подмножества узлов, используя рекурсивную функцию. И для каждого подмножества, если все ребра присутствуют между узлами подмножества, добавьте 1 к вашему счетчику: (Это почти псевдокод в C++)

int clique_counter = 0;
int n; //number of nodes in graph
//i imagine nodes are numbered from 1 to n

void f(int x, vector <int> &v){ //x is the current node
    if(x == n){
        bool is_clique = true;
        for(int i = 0; i < v.size(); i++){
            for(int j = i + 1; j < v.size(); j++){
                if(there is not an edge between node v[i] and v[j]) //it can't be clique
                    is_clique = false;
            }
        }
        if(is_clique == true){
            clique_counter++;
        }
        return;
    }

    //if x < n

    f(x + 1, v);

    v.push_back(x);
    f(x + 1, v);
    v.pop_back();
}


int main(){
    vector <int> v;
    f(1, v);
    cout << clique_counter << endl;

    return 0;
}