방향 지정되지 않은 그래프의 모든 크릭 찾기

Question

Undirected Graph의 모든 클릭을 나열하려면 어떻게합니까? (Bron-Kerbosch 알고리즘과 같은 모든 최대 파벌이 아님)

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; 
}