參考資料：
Bron-Kerbosch算法視頻介紹
極大團(tuán)算法
不確定圖上求極大團(tuán)算法
不確定圖上的枚舉算法研究

我們這里是把不確定圖當(dāng)確定圖（也就是普通的圖）碉京，來處理的，并沒由考慮邊上的概率褒侧。之所以是用的不確定圖王浴，主要是因?yàn)槲易罱芯康氖遣淮_定圖拥知，把不確定圖的數(shù)據(jù)結(jié)構(gòu)換成確定圖的坞笙，也是一樣的岩饼。

不確定圖：
不確定圖就是指邊或者頂點(diǎn)信息中帶有不確定性的圖，這種不確定性通常是通過給邊賦予權(quán)值來量化薛夜。用一個(gè)三元組 G=(V, E, β)表示一個(gè)不確定圖籍茧，其中 β 表示邊的權(quán)值，0< β <1梯澜，代表邊存在的概率寞冯。

不確定圖

如圖所示不確定圖中，每一條邊都擁有權(quán)值，用來表示該邊在實(shí)際應(yīng)用中存在的概率吮龄，所以它是一個(gè)不確定圖檬某。
1，圖的存儲(chǔ)結(jié)構(gòu)用什么好螟蝙？
確定為鄰接vector存儲(chǔ)結(jié)構(gòu)，因?yàn)関ector作為STL中的類民傻，封裝了很多函數(shù)胰默，用起來很方便。
2漓踢，運(yùn)行時(shí)遇到錯(cuò)誤：vector subscript out of range牵署？
應(yīng)該是有vector沒有分配足夠的空間，但是卻用了它的下標(biāo)喧半。

在我的上一篇文章里面用的思想主要是：設(shè)定關(guān)鍵點(diǎn) pivot vertex u奴迅，只對(duì)關(guān)鍵點(diǎn)u自身和u的非鄰居結(jié)點(diǎn)進(jìn)行查找。偽代碼如下：

Bron-Kerbosch Algorithm
R={}   //已確定的極大團(tuán)頂點(diǎn)的集合
P={v}  //未處理頂點(diǎn)集挺据，初始狀態(tài)是所有結(jié)點(diǎn)
X={}   //已搜過的并且屬于某個(gè)極大團(tuán)的頂點(diǎn)集合

BronKerbosch(R, P, X):
   if P and X are both empty:
       report R as a maximal clique
   choose a pivot vertex u in P ? X   //選取pivot結(jié)點(diǎn)u
   for each vertex v in P \ N(u):   
       BronKerbosch1(R ? {v}, P ? N(v), X ? N(v))
       P := P \ {v}
       X := X ? {v}

在這個(gè)方法里的思想是：按照?qǐng)D頂點(diǎn)編號(hào)升序地往頂點(diǎn)集合 C 中添加頂點(diǎn)取具。例如，如果當(dāng)前的頂點(diǎn)集合 C={1扁耐，3暇检，4}，則當(dāng)前頂點(diǎn)集合 C 中的最大頂點(diǎn)編號(hào)為 4婉称，那么在擴(kuò)展當(dāng)前頂點(diǎn)集合 C 的過程中不需要考慮加入頂點(diǎn) 2块仆，因?yàn)轫旤c(diǎn)集合{1，2王暗，3悔据，4}會(huì)在處理頂點(diǎn) 1 時(shí)按照頂點(diǎn)編號(hào)順序 2，3俗壹，4 依次添加而得到科汗。當(dāng)然添加進(jìn)入的頂點(diǎn)，必須是在C中所有頂點(diǎn)的公共鄰居結(jié)點(diǎn)集合中策肝，也就是集合P（some集合）中肛捍。

下邊是頭文件，大部分和上次一樣之众，只有BasicFunctions.h會(huì)有所不同：

Vertex_Value.h
#pragma once
#include <iostream>
using namespace std;
//這個(gè)相當(dāng)于臨接表中的邊界點(diǎn)
class Vertex_Value
{
public:
    Vertex_Value(void);
    ~Vertex_Value(void);
    Vertex_Value(int x, float y);

public:
    int vertex;  //鄰接表中邊結(jié)點(diǎn)的編號(hào)
    float val;    //結(jié)點(diǎn)之間的概率
};

node.h
#pragma once
#include "Vertex_Value.h"
#include <vector>
using namespace std;
//相當(dāng)于頭結(jié)點(diǎn)
class node
{
    //public:
    //  node(void);空參的構(gòu)造方法拙毫，以及析構(gòu)函數(shù)可以不用寫，系統(tǒng)會(huì)自動(dòng)實(shí)現(xiàn)
    //  ~node(void);
public:
    int vertex;    //頭節(jié)點(diǎn)的結(jié)點(diǎn)編號(hào)
    vector<Vertex_Value> vec;  //這里用vector動(dòng)態(tài)數(shù)組來放邊結(jié)點(diǎn)棺禾，Vertex_Value表示邊結(jié)點(diǎn)缀蹄，其中有結(jié)點(diǎn)編號(hào)，以及邊上的概率
};

UDG.h
#pragma once
#include "node.h"

class UDG
{
    //public:
    //  UDG(void);
    //  ~UDG(void);
public:
    int vernum, arcnum;//結(jié)點(diǎn)數(shù)目和邊的數(shù)目
    node *AdjVector;//是鄰接vector的形式 一個(gè)數(shù)組名字叫AdjVector,數(shù)組里面存放的是node形式的的數(shù)據(jù)
};

ReadFile.h
#pragma once
#include "UDG.h"

#define path "F:\\c++_code\\test1.txt"http://文件路徑
//讀取文件
class ReadFile
{
public:
    ReadFile(void);
    ~ReadFile(void);
    void CreateUdg(UDG &g); //讀取文件后，構(gòu)建出不確定圖出來
};

BasicFunctions.h里面的函數(shù)會(huì)和以前有所不同：

BasicFunctions.h
#pragma once
#include <vector>
#include "UDG.h"
#include "Vertex_Value.h"
using namespace std;

#define $ 0.1 //概率閾值缺前，這里我把圖當(dāng)作是確定的蛀醉，所以不考慮概率。
class BasicFunctions
{
public:
    BasicFunctions(void);
    ~BasicFunctions(void);

    void Bron_Kerbosch(const UDG g);//把不確定圖作為確定圖來看待衅码，得到所有的極大團(tuán)子圖

    bool IfConnect(int u, int v, UDG g);  //判斷在圖g中拯刁，結(jié)點(diǎn)u和結(jié)點(diǎn)v是否連接

    void Enum_Deterministic(vector <int> all, vector <int> some, vector <int> none, UDG g);//用在Bron_Kerbosch算法中，枚舉圖中的極大團(tuán)

    vector<int> GenerateSome(vector <int> all, vector <int> some, UDG g);//用在Enum_Deterministic中逝段，更新其中的some集合
    
    vector<int> GenerateNone(vector <int> all, vector <int> none, UDG g);//用在Enum_Deterministic中垛玻，更新其中的none集合

    int MaxC(vector<int> C);//找當(dāng)前團(tuán)C中的最大頂點(diǎn)編號(hào)
    
    vector<int> AdjVertex(int m, UDG g);//找到圖g中，m結(jié)點(diǎn)的所有鄰接點(diǎn)

    vector<int> mixede(vector<int> A, vector<int> B);//求兩個(gè)vector的交集

    bool isbelongto(int m, vector<int> S1);//檢測(cè)m頂點(diǎn)是否屬于S1奶躯；

};

下面是cpp文件

Vertex_Value.cpp
#include "Vertex_Value.h"
Vertex_Value::Vertex_Value(void)
{
}

Vertex_Value::~Vertex_Value(void)
{
}
Vertex_Value::Vertex_Value(int x, float y)
{
    vertex = x;
    val = y;
}

ReadFile.cpp
#include "ReadFile.h"
#include <fstream>
#include <iostream>
using namespace std;

ReadFile::ReadFile(void)
{
}

ReadFile::~ReadFile(void)
{
}
void ReadFile::CreateUdg(UDG &g)
{
    ifstream infile(path);      //讀取path里面的文本
    cout << "開始讀入文件帚桩！" << endl;
    infile >> g.vernum >> g.arcnum;   //infile在這里就類似cin操作，cin是讀取鍵盤輸入嘹黔，而infile是讀取文件輸入 >> 操作返回的是左操作數(shù)账嚎，也就是給g.vernum和g.arcnum賦值了
    cout << "頂點(diǎn)個(gè)數(shù)和邊數(shù)為：" << endl;
    cout << g.vernum << ' ' << g.arcnum << endl;
    g.AdjVector = new node[g.vernum + 1];//0號(hào)不存結(jié)點(diǎn)，能儲(chǔ)存g.vernum個(gè)結(jié)點(diǎn)的數(shù)組AdjVector儡蔓，g.AdjVector[0]中不存放數(shù)據(jù)
    cout << "開始讀入邊郭蕉，建立鄰接vector！" << endl;
    int i;
    for (i = 0; i < g.arcnum; i++)
    {
        int head, tail;
        float val;
        infile >> head >> tail >> val;  //文本里讀取文件到空格結(jié)束浙值，循環(huán)結(jié)束以后進(jìn)入到下一行
        g.AdjVector[head].vertex = head;   //這樣可以完成順序存放恳不，這樣g.AdjVector[1]中，存放的是頭節(jié)點(diǎn)為1的結(jié)點(diǎn)开呐，其他結(jié)點(diǎn)也都是對(duì)應(yīng)的
        Vertex_Value temp;
        temp.vertex = tail;
        temp.val = val;
        g.AdjVector[head].vec.push_back(temp);
    }
}

#include<algorithm>
#include <iterator> 
#include "UDG.h"
#include "BasicFunctions.h"



BasicFunctions::BasicFunctions(void)
{
}

BasicFunctions::~BasicFunctions(void)
{
}



//***********************************************************************
//判斷在圖g中結(jié)點(diǎn)u和結(jié)點(diǎn)v是否相連
bool BasicFunctions::IfConnect(int u, int v, UDG g)
{
    int i;
    unsigned int j;
    for (i = 1; i <= g.vernum; i++)
    {
        if (g.AdjVector[i].vertex == u)
        {
            break;
        }
    }

    for (j = 0; j < g.AdjVector[i].vec.size(); j++)
    {
        if (v == g.AdjVector[i].vec[j].vertex)
        {
            //cout << "結(jié)點(diǎn)" << u << "和結(jié)點(diǎn)" << v << "相連" << endl;
            return true;
        }
    }
    //cout << "結(jié)點(diǎn)" << u << "和結(jié)點(diǎn)" << v << "不相連" << endl;
    return false;
}


//***********************************************************************
//檢測(cè)m頂點(diǎn)是否屬于S1烟勋；
bool BasicFunctions::isbelongto(int m, vector<int> S1)
{
    for (unsigned int i = 0; i < S1.size(); i++)
    {
        if (m == S1[i])
        {
            return true;
        }
    }
    return false;
}


//***********************************************************************
//求兩個(gè)vector的交集
vector<int> BasicFunctions::mixede(vector<int> A, vector<int> B)
{
    vector<int> v;
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    set_intersection(A.begin(), A.end(), B.begin(), B.end(), back_inserter(v));//求交集 ,必須引入<algorithm>、<iterator>才能使用這些函數(shù)
    return v;

}


//***********************************************************************
//找當(dāng)前團(tuán)C中的最大頂點(diǎn)編號(hào)
int BasicFunctions::MaxC(vector<int> C)
{
    if (C.empty())
    {
        return 0;
    }
    int max = 1;
    unsigned int i;
    for (i = 0; i < C.size(); i++)
    {
        if (max < C[i])
        {
            max = C[i];
        }
    }
    return max;
}

//***********************************************************************
//找到圖g中筐付，m結(jié)點(diǎn)的所有鄰接點(diǎn)
vector<int> BasicFunctions::AdjVertex(int m, UDG g)
{
    vector<int> C;
    unsigned int i;
    for (i = 0; i < g.AdjVector[m].vec.size(); i++)
    {
        C.push_back(g.AdjVector[m].vec[i].vertex);
    }
    return C;
}

//***********************************************************************
//用在Enum_Deterministic中卵惦，更新其中的none集合
vector<int> BasicFunctions::GenerateNone(vector <int> all, vector <int> none, UDG g)
{

    int m = MaxC(all);    //找到C中編號(hào)最大的點(diǎn)
    vector<int> S2 = AdjVertex(m, g); //在圖g中找到m的鄰居接點(diǎn)
    vector<int> _none;
    vector<int> S1;
    unsigned int i;
    for (i = 0; i < none.size(); i++)
    {
        S1.push_back(none[i]);
    }
    S1 = mixede(S1, S2);   //保證some中放的結(jié)點(diǎn)，都是和all中所有結(jié)點(diǎn)連接的


    for (i = 0; i < none.size(); i++)
    {
        if (isbelongto(none[i], S1))
        {
            _none.push_back(none[i]);
        }
    }
    return _none;


}

//***********************************************************************
//用在Enum_Deterministic中瓦戚，更新其中的some集合
vector<int> BasicFunctions::GenerateSome(vector <int> all, vector <int> some, UDG g)
{


    int m = MaxC(all);    //找到all中編號(hào)最大的點(diǎn)
    vector<int> S2 = AdjVertex(m, g); //在圖g中找到m的鄰居接點(diǎn)
    vector<int> _some;
    vector<int> S1;
    unsigned int i;
    for (i = 0; i < some.size(); i++)
    {
        S1.push_back(some[i]);
    }
    S1 = mixede(S1, S2);   //保證some中放的結(jié)點(diǎn)沮尿，都是和all中所有結(jié)點(diǎn)連接的


    for (i = 0; i < some.size(); i++)
    {
        if (some[i] > m && isbelongto(some[i], S1))
        {
            _some.push_back(some[i]);
        }
    }
    return _some;

}




//***********************************************************************
//用在Bron_Kerbosch算法中，枚舉圖中的極大團(tuán)
void BasicFunctions::Enum_Deterministic(vector <int> all, vector <int> some, vector <int> none, UDG g)
{
    unsigned int i;
    if (some.empty() && none.empty())    //兩者都為空较解，則找到極大團(tuán)
    {
        cout << "產(chǎn)生一個(gè)極大團(tuán)畜疾！" << endl;
        for (i = 0; i < all.size(); i++)
        {
            cout << all[i] << ' ';
        }
        cout << endl;
        return;
    }

    //int u = some[0];
    vector<int> allTemp(all);   //將all中的所有值，都賦給allTemp印衔，allTemp用來遞歸到下一層（去放置極大團(tuán)）
    for (i = 0; i < some.size(); i++)
    {

        //int v = some[i];
        //if (IfConnect(u, v, g)) continue;

        allTemp.push_back(some[i]);//更新下一層中的allTemp
        vector<int> _some = GenerateSome(allTemp, some, g);//產(chǎn)生新的some集合啡捶。要保證新的some集合，要和allTemp集合中的所有結(jié)點(diǎn)都連接
        vector<int> _none = GenerateNone(allTemp, none, g);//產(chǎn)生新的none集合奸焙。要保證新的none集合瞎暑，要和allTemp集合中的所有結(jié)點(diǎn)都連接
        Enum_Deterministic(allTemp, _some, _none, g);   //帶著新的all,some,none集合進(jìn)入到下一層中

        none.push_back(some[i]);//將some[i]放入none中彤敛，表示在這一層里面，由some[i]開始的極大團(tuán)了赌，已經(jīng)探索過了

        allTemp.pop_back(); //將some[i]從allTemp中拿出墨榄，開始下一輪的for循環(huán)，在下一輪的for循環(huán)中勿她，放入新的some[i]

    }

}



//***********************************************************************
//總算法的第一步袄秩，從原圖中得到所有的極大團(tuán)子圖
void BasicFunctions::Bron_Kerbosch(const UDG g)
{


    vector <int> some(g.vernum);//聲明一個(gè)初始大小為g.vernum的Vertex_Value類型的向量_I，_I中存放的結(jié)點(diǎn)逢并，就是預(yù)備要放入C中的
    vector<int> all;       //聲明一個(gè)int型向量all播揪，就是極大團(tuán)
    vector<int> none;   //聲明一個(gè)Vertex_Value型向量X ，X存放已經(jīng)探索過的某結(jié)點(diǎn)筒狠。
    int i = 1;
    for (i; i <= g.vernum; i++)
    {
        some[i - 1] = i;   //將所有的結(jié)點(diǎn)編號(hào)存放在some中
    }
    Enum_Deterministic(all, some, none, g);

}

下面是主函數(shù)：

#include <tchar.h>
#include "ReadFile.h"
#include "BasicFunctions.h"
#include <iostream>
using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
    UDG g;
    ReadFile A;
    A.CreateUdg(g);
    BasicFunctions BF;
    BF.Bron_Kerbosch(g);

    system("pause"); //暫停黑窗口
    return 0;
}

test2.txt如下:
9表示結(jié)點(diǎn)數(shù)，28表示邊數(shù)（這里的1 2和2 1算不同的邊）
第一位數(shù)字是頭結(jié)點(diǎn)箱沦，第二位數(shù)字是邊結(jié)點(diǎn)辩恼，第三個(gè)數(shù)字是邊上的概率

9 28
1 2 0.6
1 3 0.5
2 1 0.6
2 3 0.4
2 5 0.7
3 1 0.5
3 2 0.4
3 4 0.5
3 5 0.1
4 3 0.5
4 5 0.2
5 2 0.7
5 3 0.1
5 4 0.2
5 6 0.4
6 5 0.4
6 7 0.7
6 8 0.9
6 9 0.8
7 6 0.7
7 8 0.7
7 9 0.6
8 6 0.9
8 7 0.7
8 9 0.6
9 6 0.8
9 7 0.6
9 8 0.6

實(shí)驗(yàn)結(jié)果：

實(shí)驗(yàn)結(jié)果