最大团问题的回溯法_试设计一个解最大团问题的迭代回溯法

原文链接：https://www.cnblogs.com/wkfvawl/p/11923848.html

分析

首先设最大团为一个空团，往其中加入一个顶点，然后依次考虑每个顶点，查看该顶点加入团之后仍然构成一个团，如果可以，考虑将该顶点加入团或者舍弃两种情况，如果不行，直接舍弃，然后递归判断下一顶点。对于无连接或者直接舍弃两种情况，在递归前，可采用剪枝策略来避免无效搜索

为了判断当前顶点加入团之后是否仍是一个团，只需要考虑该顶点和团中顶点是否都有连接

程序中采用了一个比较简单的剪枝策略，即如果剩余未考虑的顶点数加上团中顶点数不大于当前解的顶点数，可停止继续深度搜索，否则继续深度递归

代码

#include <iostream>
#include <cstring>
using namespace std;

const static int MAX = 1e3 + 5;
bool a[MAX][MAX]; //图的邻接矩阵
bool x[MAX];      //当前解
int cn;           //当前团的顶点数
int bestn;        //当前的最优解
int n;            //图G的顶点数
int e;            //图G的边数

bool ok(int i)
{
    for (int j = 1; j < i; j++)
    {
        if (x[j] && !a[j][i]) //i与j不相连
        {
            return false;
        }
    }
    return true;
}

void backtrack(int i)
{
    int j;
    if (i > n)
    {
        bestn = cn;
        cout << "最大顶点数：" << bestn << endl;
        cout << "顶点有：";
        for (int i = 1; i <= n; i++)
        {
            if (x[i])
            {
                cout << i << ' ';
            }
        }
        return;
    }

    if (ok(i)) //进入左子树
    {
        cn++;
        x[i] = true;
        backtrack(i + 1);
        cn--;
    }
    if (cn + n - i > bestn) //剪枝
    {
        x[i] = false;
        backtrack(i + 1);
    }
}

int main()
{
    cout << "请输入图的顶点数和边数：";
    cin >> n >> e;
    memset(a, 0, sizeof(a));
    memset(x, 0, sizeof(x));
    cout << "请输入" << e << "条边" << endl;
    for (int i = 0, u, v; i < e; i++)
    {
        cin >> u >> v;
        a[u][v] = true;
        a[v][u] = true;
    }

    cn = bestn = 0;
    backtrack(1);

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

输入

请输入图的顶点数和边数：5 7
请输入7条边
1 2
1 4
1 5
2 5
2 3
3 5
4 5
1
2
3
4
5
6
7
8
9

输出

最大顶点数：3
顶点有：1 2 5
1
2

参考：https://www.cnblogs.com/wkfvawl/p/11923848.html