最大團問題

鎖定

給定無向圖G=(V,E)，其中V是非空集合，稱為頂點集；E是V中元素構成的無序二元組的集合，稱為邊集，無向圖中的邊均是頂點的無序對，無序對常用圓括號“( )”表示。如果

，且對任意兩個頂點u，v∈U有(u,v)∈E，則稱U是G的完全子圖。G的完全子圖U是G的團。G的最大團是指G的最大完全子圖。

圖1

如圖1所示，給定無向圖G={V, E}，其中V={1,2,3,4,5}，E={(1,2), (1,4), (1,5),(2,3), (2,5), (3,5), (4,5)}。根據MCP定義，子集{1,2}是圖G的一個大小為2的完全子圖，但不是一個團，因為它包含於G的更大的完全子圖{1,2,5}之中。{1,2,5}是G的一個最大團。{1,4,5}和{2,3,5}也是G的最大團。圖2是無向圖G的補圖G'。根據最大獨立集定義，{2,4}是G的一個空子圖，同時也是G的一個最大獨立集。雖然{1,2}也是G'的空子圖，但它不是G'的獨立集，因為它包含在G'的空子圖{1,2,5}中。{1,2,5}是G'的最大獨立集。{1,4,5}和{2,3,5}也是G'的最大獨立集。以圖1為例，利用回溯法搜索其空間樹，具體搜索過程（見圖3所示）如下：假設我們按照1®2®3®4®5的順序深度搜索。開始時，根結點R是唯一活結點，也是當前擴展結點，位於第1層，此時當前團的頂點數cn=0，最大團的頂點數bestn=0。在這個擴展結點處，我們假定R和第二層的頂點1之間有邊相連，則沿縱深方向移至頂點1處。此時結點R和頂點1都是活結點，頂點1成為當前的擴展結點。此時當前團的頂點數cn=1，最大團的頂點數bestn=0。繼續深度搜索至第3層頂點2處，此時頂點1和2有邊相連，都是活結點，頂點2成為當前擴展結點。此時當前團的頂點數cn=2，最大團的頂點數bestn=0。再深度搜索至第4層頂點3處，由於頂點3和2有邊相連但與頂點1無邊相連，則利用剪枝函數剪去該枝，此時由於cn+n-i=2+5-4=3＞bestn=0，則回溯到結點2處進入右子樹，開始搜索。此時當前團的頂點數cn=2，最大團的頂點數bestn=0。再深度搜索至第5層頂點4處，由於頂點3和4無邊相連，剪去該枝，回溯到結點3處進入右子樹，此時當前團的頂點數cn=2，最大團的頂點數bestn=0。繼續深度搜索至第6層頂點5處，由於頂點5和4有邊相連，且與頂點1和2都有邊相連，則進入左子樹搜索。由於結點5是一個葉結點，故我們得到一個可行解，此時當前團的頂點數cn=3，最大團的頂點數bestn=3。vi的取值由頂點1至頂點5所唯一確定，即v=(1, 2, 5)。此時頂點5已不能再縱深擴展，成為死結點，我們返回到結點4處。由於此時cn+n-i=3+5-6=2＜bestn=3，不能在右子樹中找到更大的團，利用剪枝函數可將結點4的右結點剪去。以此回溯，直至根結點R再次成為當前的擴展結點，沿着右子樹的縱深方向移動，直至遍歷整個解空間。最後得到圖1的按照1®2®3®4®5的順序深度搜索的最大團為U={1,2,5}。當然{1,4,5}和{2,3,5}也是其最大團。

圖3

圖2

//MaxClique.cpp : 定義控制枱應用程序的入口點。
/*

回溯法求解最大團問題
*/
#include <fstream>
#include <iostream>
#include <stdlib.h>
#include <conio.h>
using namespace std;
#define MAX_v 50 //定義一個最大頂點個數
typedef struct{
    int a[MAX_v][MAX_v]; //
無向圖G的
鄰接矩陣
    int v; //無向圖G的頂點
    int e; //無向圖G的邊
    int x[50]; //頂點與當前團的連接，x[i]=1 表示有連接
    int bestx[50]; //當前最優解
    int cnum; //當前團的頂點數目
    int bestn; //最大團的頂點數目
}MCP;
void Creat(MCP &G);
void 
Backtrack(MCP &G,int i);
void Creat(MCP &G){
    int i,j;
    ifstream fin("data.txt");
    if (!fin)
    {
        cout<<"不能打開文件:"<<"data.txt"<<
endl;
        exit(1);
    }
    fin>>G.v;
    for (int i=1;i<=G.v;i++)
        for (int j=1;j<=G.v;j++)
            fin>>G.a[i][j];
    for(i=1;i<=G.v;i++) //初始化
    {
        G.bestx[i]=0;
        G.x[i]=0;
        G.bestn=0;
        G.cnum=0;
    }
    cout<<"————————————————"<<
endl;
    cout<<"———
回溯法求解最大團問題———"<<endl;
    cout<<"————————————————"<<endl;
    cout<<"輸入初始化
無向圖矩陣為:"<<
endl; //初始化
    for(i=1;i<=G.v;i++)
    {
        for(j=1;j<=G.v;j++)
        cout<<G.a[i][j]<<" ";
        cout<<
endl;
    }
}
void Backtrack(MCP &G,int i){
    if (i>G.v){
        for (int j=1; j<=G.v; j++)
            G.bestx[j] = G.x[j];
        G.bestn =G.cnum;
        return ;
    }
    //檢查頂點i與當前團的連接
    int OK = 1;
    for (int j=1; j<=i ; j++)
        if (G.x[j]&& G.a[i][j]==0){
            //i不與j相連
            OK = 0;
            break;
        }
    if (OK) {
        G.x[i] = 1;//把i加入團
        G.cnum++;
        Backtrack(G,i+1);
        G.x[i]=0;
        G.cnum-- ;
    }
    if (G.cnum+G.v- i>G.bestn){
        G.x[i] = 0;
        Backtrack(G,i+1);
    }
}
int main(){
    MCP G;
    Creat(G);
    Backtrack(G,1);
    cout<<"最大團包含的頂點數為:"<<G.bestn<<
endl;
    cout<<"最大團方案為:( ";
    for (int i=1;i<=G.v;i++)
        if(G.bestx[i]==1){
            cout<<i<<" ";
        }
    cout<<")"<<
endl;
    
getch();
}

//MaxClique_BB.cpp : 定義控制枱應用程序的入口點。
/*

分支限界法求解最大團問題
*/
#include <fstream>
#include <iostream>
#include <queue>
#include <conio.h>
using namespace std;
typedef struct{
    int v; //
無向圖G的頂點
    int e; //無向圖G的邊
    int a[50][50]; //定義圖G的
鄰接矩陣
    int bestx[50]; //最優解
}MCP;
void Creat(MCP &G){
    int i,j;
    ifstream fin("data.txt");
    if(!fin)
    {
        cout<<"不能打開文件:"<<"data.txt"<<endl;
        exit(1);
    }
    fin>>G.v;
    for(int i=1;i<=G.v;i++)
        for(int j=1;j<=G.v;j++)
            fin>>G.a[i][j];
    for(i=1;i<=G.v;i++) //初始化
    {
        G.bestx[i]=0;
    }
    cout<<"————————————————————————"<<
endl;
    cout<<"———
優先隊列式
分支限界法求解最大團問題———"<<endl;
    cout<<"————————————————————————"<<endl;
    cout<<"輸入初始化
無向圖矩陣為:"<<endl; //初始化
    for(i=1;i<=G.v;i++)
    {
        for(j=1;j<=G.v;j++)
        cout<<G.a[i][j]<<" ";
        cout<<endl;
    }
}
struct BBNode
{
    BBNode *parent; //指向父結點的指針
    bool LChild; //左兒子結點標誌
};
struct CliqueNode //定義
優先隊列類型為CliqueNode
{
    int cnum; //當前團的頂點數
    int un; //當前團最大頂點數的上界
    int level; //結點在子集空間樹種所處的層次
    BBNode *p; //指向活結點在子集樹中相應結點的指針
    bool operator<(const CliqueNode &b) const //<號
重載建立大根堆
    {
        if (b.un>un) return true;
    if (b.un==un&& b.cnum>cnum) return true;
    else return false;
   }
};
void BBMaxClique(MCP&G)
{
    BBNode *E=new(BBNode); //定義B代表記錄的隊列情況
    //初始化
    int j,i=1;
    int cnum=0,bestn=0;
    int OK=1;
    priority_queue<CliqueNode> Q; //定義
優先隊列Q
    E->LChild=false; //初始化
    E->parent=NULL;
    
while(i!=G.v+1)//非葉結點
    {
        //檢查頂點i與當前團中其它頂點之間是否有邊相連
        OK=1;
        BBNode *B=E; //把當前點的數據給B，B為中間變量
        for(j=i-1;j>0;B=B->parent,j--)
        if(B->LChild&& G.a[i][j]==0) //如果不滿足就停止
        {
            OK=0;
            break;
        }
        if(OK) //滿足條件，即左兒子結點為可行結點
        {
            CliqueNode *D=new(CliqueNode); //定義一個節點D
            D->p=new(BBNode);
            if(cnum+1>bestn)bestn=cnum+1;
            D->cnum=cnum+1;
            D->level=i+1;
            D->p->LChild=true;
            D->p->parent=E;
            D->un=cnum+1+G.v-i;
            Q.push(*D); //進隊列
        }
        if(cnum+G.v-i>bestn) //不滿足條件但是還是可能有最優解
        {
            CliqueNode *D=new(CliqueNode); //定義一個節點D
            D->p=new(BBNode);
            D->cnum=cnum;
            D->level=i+1;
            D->p->LChild=false;
            D->p->parent=E;
            D->un=cnum+G.v-i;
            Q.push(*D); //進隊列
        }
        CliqueNode N;
        N=Q.top(); //取隊頂元素，
最大堆
        Q.pop(); //刪除隊頂元素
        E=N.p; //記錄當前團的信息
        cnum=N.cnum; //記錄當前團的頂點數
        i=N.level; //所在的層次
    }
    for(j=G.v;j>0;j--) //保存最優解
    {
        G.bestx[j]=E->LChild;
        E=E->parent;
        bestn=cnum;
    }
}
int main(){
    MCP G;
    Creat(G);
    BBMaxClique(G);
    cout<<"最大團方案為:(";
    for(int i=G.v;i>0;i--)
        if (G.bestx[i]==1){
            cout<<i<<" ";
        }
    cout<<")"<<
endl;
    
getch();
}