查找无向图的所有派系 [英] Finding All Cliques of an Undirected Graph

问题描述

如何列出无向图的所有派系? (并非所有最大派系都像Bron-Kerbosch算法一样)

How can I list all cliques of an Undirected Graph ? (Not all maximal cliques, like the Bron-Kerbosch algorithm)

推荐答案

最优解决方案是这样的，因为在一个完整的图中有2 ^ n个团.考虑使用递归函数的所有节点子集.对于每个子集，如果子集的节点之间都存在所有边，则将1加到您的计数器中:(这几乎是C ++中的伪代码)

The optimal solution is like this because in a complete graph there are 2^n cliques. Consider all subsets of nodes using a recursive function. And for each subset if all the edges are present between nodes of the subset, add 1 to your counter: (This is almost a pseudocode in 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;
}

这篇关于查找无向图的所有派系的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！