最大团问题（回溯法）

最大团问题（回溯法）

Maximum Clique

杭电OJ Maximum Clique
Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 6637 Accepted Submission(s): 3371

Problem Description
Given a graph G(V, E), a clique is a sub-graph g(v, e), so that for all vertex pairs v1, v2 in v, there exists an edge (v1, v2) in e. Maximum clique is the clique that has maximum number of vertex.

Input
Input contains multiple tests. For each test:

The first line has one integer n, the number of vertex. (1 < n <= 50)

The following n lines has n 0 or 1 each, indicating whether an edge exists between i (line number) and j (column number).

A test with n = 0 signals the end of input. This test should not be processed.

Output
One number for each test, the number of vertex in maximum clique.

Sample Input
5
0 1 1 0 1
1 0 1 1 1
1 1 0 1 1
0 1 1 0 1
1 1 1 1 0
0

Sample Output
4

java

import java.util.Scanner;
public class Main {static long count = 0;	//目前求解出的最大顶点数static int [][]a;	//图的邻接矩阵static int []x;		//x[i] == 1，表示最大团包括第i个点。static int v;		//顶点数目public static void main(String[] args) {// TODO Auto-generated method stubScanner sc = new Scanner(System.in);while((v = sc.nextInt())!=0){a = new int[v+1][v+1];x = new int[v+1];for(int i=1;i<=v;i++)for(int j=1;j<=v;j++)a[i][j] = sc.nextInt();//该问题属于 子集树 时间复杂度为O（2^v）,即每个顶点都有选和不选两种可能。backtrack(1,0);System.out.println(count);count = 0;}}static void backtrack(int t,int n){		//t表示第几层，n表示已经选取顶点的个数if(t>v) {count = n;//print();return;}//判断当前结点（第t个点）与之前的t-1个点是否都相连//如果不相连 则剪去当前树，及其子树if(yueshu(t)){//如果都相连，则进入下一层，左子树x[t] = 1;	//选取第t个点backtrack(t+1,n+1);	//层数+1.选取顶点的个数+1，}// v-t 表示还剩下几层，也就是最多还能选多少个点。//n + v-t表示加上已经选取了的点。如果这个数大于已经求得     最大团中顶点的个数   才会进入下一层//否则 剪枝if(n + v-t>count) {//右子树x[t] = 0;backtrack(t+1,n);}}static boolean yueshu(int t){for(int j=1;j<t;j++)if(x[j] == 1&&a[t][j] == 0) {return false;}return true;}
}

CPP

回溯法最大的问题就是时间较长，很容易就超时。

#include <iostream>
using namespace std;
long count_v = 0;	//目前求解出的最大顶点数
int a[55][55];	//图的邻接矩阵
int x[55];		//x[i] == 1，表示最大团包括第i个点。
int v;		//顶点数目
static bool yueshu(int t) {for (int j = 1; j < t; j++)if (x[j] == 1 && a[t][j] == 0) {return false;}return true;
}
static void backtrack(int t, int n) {		//t表示第几层，n表示已经选取顶点的个数if (t > v) {count_v = n;//print();return;}//判断当前结点（第t个点）与之前的t-1个点是否都相连//如果不相连 则剪去当前树，及其子树if (yueshu(t)) {//如果都相连，则进入下一层，左子树x[t] = 1;	//选取第t个点backtrack(t + 1, n + 1);	//层数+1.选取顶点的个数+1，}// v-t 表示还剩下几层，也就是最多还能选多少个点。//n + v-t表示加上已经选取了的点。如果这个数大于已经求得     最大团中顶点的个数   才会进入下一层//否则 剪枝if (n + v - t > count_v) {//右子树x[t] = 0;backtrack(t + 1, n);}
}int main()
{while ((cin>>v) && v!= 0) {for (int i = 1; i <= v; i++)for (int j = 1; j <= v; j++)cin>>a[i][j];//该问题属于 子集树 时间复杂度为O（2^v）,即每个顶点都有选和不选两种可能。backtrack(1, 0);cout << count_v << endl;count_v = 0;}return 0;
}