首先介绍下最大团问题：
问题描述：给一个无向图G=(V,E) ，V是顶点集合，E是边集合。然后在这顶点集合中选取几个顶点，这几
个顶点任意两个之间都有边在E中。求最多可以选取的顶点个数。这几个顶点就构成一个最大团。
注：最大团可能不唯一。
问题求解思想：这个问题的本质是一个子集选取问题，就是有集合包括n个元素{1,2,…,n}选取其中一个子
集，这个子集满足某种性质（对于最大团问题，就是任意两个顶点之间有边），求这个子集的最大元素数。
每个元素（对应顶点编号）有2种选择，加入或不加入。所以子集个数为2^n个。
这里用回溯的思想求解。
回溯的概念如是理解：在包含所有问题的所有解的解空间树中，从根节点进行深度优先搜索，搜索空间树中
的任一节点的时候，首先判断是否可能包含最优解，如果不包含，就跳过改节点为根的子树的搜索，向其上
一层祖先节点回溯。入包含，则进入该子树，进行深度优先搜索。
部落卫队问题描述：
原始部落中的居民为了争夺资源，常发生冲突。几乎每个居民都有仇敌。酋长为了组织一个部落卫队，希望
从部落居民中选出最多的居民入伍，并保证队伍中任何2个人都不是仇敌。
编程任务：
根据给定的居民间的仇敌关系，编程计算出部落卫队的最佳方案。
数据输入：
第1行2个整数n,m表示部落中居民个数，居民中有m个仇敌关系。居民编号1，2，…,n。接下来m行，每行2
个整数u,v表示居民u和v是仇敌。
数据输出：
第1行是最佳方案中部落卫队的人数，第2行是卫队组成xi, 1=<i<=n，
import java.util.Scanner;
public class buluoweidui {
public static int N=100; //默认定义数组大小
static int[][] a=new int[N][N]; //图用邻接矩阵表示
static int [] x=new int[N]; //是否将第i个节点加入团中
static int [] bestx=new int[N]; //记录最优解
static int bestn; //记录最优值
static int cn; //当前已放入团中的节点数量
static int n,m; //n为图中节点数 m为图中边数
public static void main(String [] args) {
Scanner sc=new Scanner(System.in);
System.out.println("请输入部落的人数n（节点数):");
n=sc.nextInt();
System.out.println("请输入人与人的友好关系(边数):");
m=sc.nextInt();
System.out.println("请依次输入有友好关系的两个人(有边相连的两个节点u,v）用空格分开:");
int u,v; //有边相连的两个节点u,v
for(int i=1;i<=m;i++) {
u=sc.nextInt();
v=sc.nextInt();
a[u][v]=a[v][u]=1; //边数为1
}
bestn=0; //初始最优值为0
cn=0; //初始的团中节点也为0
backTrack(1); //从第一个节点进行深度搜索
System.out.println("国王护卫队的最大人数为:"+bestn);
System.out.println("国王护卫队的成员：");
for(int i=0;i<=n;i++) {
if(bestx[i]==1) //打印最优解中记录为1的节点标号
System.out.print(i+" ");
}
}
/*进行深度搜索*/
private static void backTrack(int t) { //t：当前扩展节点在第t层
if(t>n) { //达到根节点 记录可行解 并记录此时节点数目
for(int i=1;i<=n;i++)
bestx[i]=x[i];
bestn=cn;
return;
}
if(place(t)) { //判断是否满足约束条件（边是否连通）-->左子树-->把节点加入团中
x[t]=1; //左子树 标记为1
cn++; //当前节点数+1
backTrack(t+1); //继续搜索t+1层
cn--; //回溯 加多少就减多少 回退
}
if(cn+ n-t> bestn) { //满足限界条件 -->右子数
x[t]=0;
backTrack(t+1);
}
}
private static boolean place(int t) { //判断是否可以把节点t加入团中
boolean ok=true;
for(int j=1;j<t;j++) {
if(x[j]==1 && a[t][j]==1) {
ok=false;
break;
}
}
return ok;
}
}