最大团问题和最大独立子集

迷南。 2022-09-04 08:50 160阅读 0赞

不要去百度百科找最大团，因为你会找到一个团购网站= =  
维基百科：https://en.wikipedia.org/wiki/Clique\_problem

首先，团是什么呢？  
团就是一个点集，点集中任意两点都有直接的边相连  
举个栗子：  
图中红色的点构成了一个团，当然单独一个点也算是一个团。

那么，独立子集又是什么呢？  
和团正好相反，独立子集也是一个点集，但是任意两点之间都没有直接的边相连……  
再举个栗子……

图中绿色的点构成了一个独立子集，你说一个点是一个独立子集我也没意见……

那么，最大团和最大独立子集怎么求呢？  
首先最大独立子集和最大团正好相反，所以最大独立子集的数目就是这个图的“补图”的最大团……  
(补图就是一张图有边的改成没边，没边的改成有边……)  
于是最大独立子集问题转化成最大团问题

最大团又怎么求呢？？？  
最大团其实是个NP完全问题……目前常用的算法是搜索+优化和随机化……  
这里介绍随机化算法(适合懒人……)  
把点组成随机组成一个排列，然后从前往后暴力找……首先第一个点可以组成一个最大团，然后加入第二个，看看是不是，如果是，加入第三个，如果不是，不加入第二个，直接加入第三个……这样跑一边是n^2的，但是答案并不一定正确，所以需要多次随机，然后取max……  
这样的准确性还是挺高的，代码也不难打，这里还是贴出来吧……(代码风格鬼畜，请做好心理准备！！！)

#include <iostream>
    #include <cstdio>
    #include <cstdlib>
    #include <ctime>
    using namespace std;
    bool a[120][120];
    int b[120];
    bool p[120];
    int n,m,x,y;
    
    void RANDOM()
    {
        srand(time(0));
        for(int i = 1;i <= n;i ++)
            swap(b[i],b[rand()%n+1]);
        return ;
    }
    
    int JUDGE()
    {
        for(int i = 1;i <= n;i ++)
            p[i] = 0;
        int ans = 0;
        for(int i = 1;i <= n;i ++)
        {
            if(!p[i])
            {
                ans ++;
                for(int j = i+1;j <= n;j ++)
                {
                    if(!a[b[i]][b[j]])
                        p[j] = 1;
                }
            }
        }
        return ans;
    }
    
    int main()
    {
        cin >> n >> m;
        for(int i = 1;i <= m;i ++)
        {
            cin >> x >> y;
            a[x][y] = 1;
            a[y][x] = 1;
        }
        for(int i = 1;i <= n;i ++)
            b[i] = i;
        int maxn = 0;
        for(int i = 1;i <= 1000;i ++)
        {
            RANDOM();
            maxn = max(maxn,JUDGE());
        }
        cout << maxn << endl;
        return 0;
    }

————————————————  
版权声明：本文为CSDN博主「FAreStorm」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。  
原文链接：https://blog.csdn.net/farestorm/article/details/48950089