最大团问题（Maximum Clique Problem）是图论中的经典NP完全问题，在社交网络分析、生物信息学、聚类分析、蛋白质结构预测等领域具有重要应用。本文用Java实现经典的Bron-Kerbosch回溯算法，并引入Pivot优化策略，深入讲解最大团的高效求解方法。
一、问题定义
给定无向图G=(V,E)，团（Clique）是顶点集的一个子集，其中任意两个顶点之间都有边相连。最大团是所有团中顶点数最多的一个。
1.1 相关概念
- 团（Clique）：两两相邻的顶点子集
- 极大团（Maximal Clique）：不能被其他团包含的团
- 最大团（Maximum Clique）：顶点数最多的极大团
- 独立集：两两不相邻的顶点子集（最大团对应补图的最大独立集）
二、算法原理
2.1 Bron-Kerbosch算法
Bron-Kerbosch算法通过递归回溯枚举所有极大团，同时记录最大团的大小。
算法维护三个互不相交的顶点集合：
– R：当前正在构建的团
– P：候选顶点集（可能与R中所有顶点相连）
– X：排除顶点集（已处理过的顶点）
递归终止条件：当P和X都为空时，R是一个极大团。
2.2 Pivot优化
通过选择一个Pivot顶点（通常从P∪X中选度数最大的），可以大幅剪枝：Pivot及其在P中的非邻居不需要作为递归起点，因为它们会被Pivot覆盖。
三、Java实现
import java.util.*;
/**
* 最大团问题求解
* 实现Bron-Kerbosch算法及其Pivot优化版本
*/
public class MaximumClique {
private final int vertices;
private final boolean[][] adjacencyMatrix;
private final List<Set<Integer>> adjacencyList;
// 记录最优解
private Set<Integer> maxClique;
private int maxCliqueSize;
private long recursiveCalls;
public MaximumClique(int vertices) {
this.vertices = vertices;
this.adjacencyMatrix = new boolean[vertices][vertices];
this.adjacencyList = new ArrayList<>();
for (int i = 0; i < vertices; i++) {
adjacencyList.add(new HashSet<>());
}
this.maxClique = new HashSet<>();
this.maxCliqueSize = 0;
}
/**
* 添加无向边
*/
public void addEdge(int u, int v) {
if (u == v) return;
adjacencyMatrix[u][v] = true;
adjacencyMatrix[v][u] = true;
adjacencyList.get(u).add(v);
adjacencyList.get(v).add(u);
}
/**
* 检查两个顶点是否相邻
*/
public boolean isAdjacent(int u, int v) {
return adjacencyMatrix[u][v];
}
/**
* 获取顶点度数
*/
public int degree(int v) {
return adjacencyList.get(v).size();
}
/**
* 基本Bron-Kerbosch算法（无Pivot优化）
* 枚举所有极大团并记录最大团
*/
public Set<Integer> bronKerboschBasic() {
maxClique = new HashSet<>();
maxCliqueSize = 0;
recursiveCalls = 0;
Set<Integer> R = new HashSet<>();
Set<Integer> P = new HashSet<>();
for (int i = 0; i < vertices; i++) P.add(i);
Set<Integer> X = new HashSet<>();
bronKerboschBasic(R, P, X);
return new HashSet<>(maxClique);
}
private void bronKerboschBasic(Set<Integer> R, Set<Integer> P, Set<Integer> X) {
recursiveCalls++;
if (P.isEmpty() && X.isEmpty()) {
// R是一个极大团
if (R.size() > maxCliqueSize) {
maxCliqueSize = R.size();
maxClique = new HashSet<>(R);
}
return;
}
// 遍历P中的每个顶点
List<Integer> pList = new ArrayList<>(P);
for (int v : pList) {
Set<Integer> newR = new HashSet<>(R);
newR.add(v);
// P ∩ N(v)
Set<Integer> newP = new HashSet<>();
for (int u : P) {
if (isAdjacent(v, u)) {
newP.add(u);
}
}
// X ∩ N(v)
Set<Integer> newX = new HashSet<>();
for (int u : X) {
if (isAdjacent(v, u)) {
newX.add(u);
}
}
bronKerboschBasic(newR, newP, newX);
P.remove(v);
X.add(v);
}
}
/**
* Bron-Kerbosch算法 with Pivot优化
* 选择一个Pivot顶点u∈P∪X，只遍历P\N(u)中的顶点
*/
public Set<Integer> bronKerboschPivot() {
maxClique = new HashSet<>();
maxCliqueSize = 0;
recursiveCalls = 0;
Set<Integer> P = new HashSet<>();
for (int i = 0; i < vertices; i++) P.add(i);
bronKerboschPivot(new HashSet<>(), P, new HashSet<>());
return new HashSet<>(maxClique);
}
private void bronKerboschPivot(Set<Integer> R, Set<Integer> P, Set<Integer> X) {
recursiveCalls++;
if (P.isEmpty() && X.isEmpty()) {
if (R.size() > maxCliqueSize) {
maxCliqueSize = R.size();
maxClique = new HashSet<>(R);
}
return;
}
// 选择Pivot：从P∪X中选择度数最大的顶点
int pivot = selectPivot(P, X);
// 只遍历P中不与Pivot相邻的顶点
Set<Integer> candidates = new HashSet<>(P);
if (pivot != -1) {
candidates.removeAll(adjacencyList.get(pivot));
}
List<Integer> candList = new ArrayList<>(candidates);
for (int v : candList) {
Set<Integer> newR = new HashSet<>(R);
newR.add(v);
Set<Integer> newP = intersect(P, adjacencyList.get(v));
Set<Integer> newX = intersect(X, adjacencyList.get(v));
bronKerboschPivot(newR, newP, newX);
P.remove(v);
X.add(v);
}
}
/**
* 选择Pivot顶点（从P∪X中选度数最大的）
*/
private int selectPivot(Set<Integer> P, Set<Integer> X) {
Set<Integer> union = new HashSet<>(P);
union.addAll(X);
if (union.isEmpty()) return -1;
int bestPivot = -1;
int maxDegree = -1;
for (int v : union) {
int deg = 0;
for (int u : P) {
if (isAdjacent(v, u)) deg++;
}
if (deg > maxDegree) {
maxDegree = deg;
bestPivot = v;
}
}
return bestPivot;
}
/**
* 集合交集
*/
private Set<Integer> intersect(Set<Integer> a, Set<Integer> b) {
Set<Integer> result = new HashSet<>(a);
result.retainAll(b);
return result;
}
/**
* 带退化序（Degeneracy Ordering）优化的Bron-Kerbosch
* 对于稀疏图特别有效
*/
public Set<Integer> bronKerboschDegeneracy() {
maxClique = new HashSet<>();
maxCliqueSize = 0;
recursiveCalls = 0;
// 计算退化序
int[] ordering = computeDegeneracyOrdering();
for (int i = 0; i < vertices; i++) {
int v = ordering[i];
// P = N(v) ∩ 后续顶点
Set<Integer> P = new HashSet<>();
for (int u : adjacencyList.get(v)) {
int uIndex = findIndex(ordering, u);
if (uIndex > i) {
P.add(u);
}
}
// X = N(v) ∩ 前面顶点
Set<Integer> X = new HashSet<>();
for (int u : adjacencyList.get(v)) {
int uIndex = findIndex(ordering, u);
if (uIndex < i) {
X.add(u);
}
}
Set<Integer> R = new HashSet<>();
R.add(v);
bronKerboschPivot(R, P, X);
}
return new HashSet<>(maxClique);
}
/**
* 计算图的退化序
* 每次选择度数最小的顶点
*/
private int[] computeDegeneracyOrdering() {
int[] ordering = new int[vertices];
boolean[] removed = new boolean[vertices];
// 复制度数数组
int[] degrees = new int[vertices];
for (int i = 0; i < vertices; i++) {
degrees[i] = degree(i);
}
for (int i = 0; i < vertices; i++) {
// 找到未移除中度数最小的顶点
int minDeg = vertices + 1;
int minVertex = -1;
for (int v = 0; v < vertices; v++) {
if (!removed[v] && degrees[v] < minDeg) {
minDeg = degrees[v];
minVertex = v;
}
}
ordering[i] = minVertex;
removed[minVertex] = true;
// 更新邻居度数
for (int neighbor : adjacencyList.get(minVertex)) {
if (!removed[neighbor]) {
degrees[neighbor]--;
}
}
}
return ordering;
}
private int findIndex(int[] array, int value) {
for (int i = 0; i < array.length; i++) {
if (array[i] == value) return i;
}
return -1;
}
/**
* 贪心近似算法（适合大规模图）
* 近似比无法保证，但速度快
*/
public Set<Integer> greedyClique() {
Set<Integer> clique = new HashSet<>();
Set<Integer> candidates = new HashSet<>();
for (int i = 0; i < vertices; i++) candidates.add(i);
while (!candidates.isEmpty()) {
// 选择候选集中度数最大的顶点
int bestVertex = -1;
int maxConnections = -1;
for (int v : candidates) {
int connections = 0;
for (int u : candidates) {
if (v != u && isAdjacent(v, u)) {
connections++;
}
}
if (connections > maxConnections) {
maxConnections = connections;
bestVertex = v;
}
}
clique.add(bestVertex);
// 只保留与bestVertex相邻的候选点
Set<Integer> newCandidates = new HashSet<>();
for (int u : candidates) {
if (u != bestVertex && isAdjacent(bestVertex, u)) {
newCandidates.add(u);
}
}
candidates = newCandidates;
}
return clique;
}
/**
* 验证一个集合是否为团
*/
public boolean isClique(Set<Integer> set) {
List<Integer> list = new ArrayList<>(set);
for (int i = 0; i < list.size(); i++) {
for (int j = i + 1; j < list.size(); j++) {
if (!isAdjacent(list.get(i), list.get(j))) {
return false;
}
}
}
return true;
}
/**
* 获取最大团大小
*/
public int getMaxCliqueSize() {
return maxCliqueSize;
}
/**
* 获取递归调用次数
*/
public long getRecursiveCalls() {
return recursiveCalls;
}
/**
* 打印团的详细信息
*/
public void printClique(Set<Integer> clique) {
System.out.println("团大小: " + clique.size());
System.out.println("顶点: " + clique);
System.out.println("是否为团: " + isClique(clique));
}
public static void main(String[] args) {
// 示例1：简单图
System.out.println("=== 示例1：6顶点图 ===");
MaximumClique graph1 = new MaximumClique(6);
graph1.addEdge(0, 1);
graph1.addEdge(0, 2);
graph1.addEdge(1, 2);
graph1.addEdge(1, 3);
graph1.addEdge(2, 3);
graph1.addEdge(2, 4);
graph1.addEdge(3, 4);
graph1.addEdge(3, 5);
graph1.addEdge(4, 5);
System.out.println("\n--- 基本Bron-Kerbosch ---");
Set<Integer> clique1 = graph1.bronKerboschBasic();
graph1.printClique(clique1);
System.out.println("递归调用次数: " + graph1.getRecursiveCalls());
System.out.println("\n--- Pivot优化 ---");
Set<Integer> clique2 = graph1.bronKerboschPivot();
graph1.printClique(clique2);
System.out.println("递归调用次数: " + graph1.getRecursiveCalls());
System.out.println("\n--- 退化序优化 ---");
Set<Integer> clique3 = graph1.bronKerboschDegeneracy();
graph1.printClique(clique3);
System.out.println("递归调用次数: " + graph1.getRecursiveCalls());
System.out.println("\n--- 贪心近似 ---");
Set<Integer> clique4 = graph1.greedyClique();
graph1.printClique(clique4);
// 示例2：完全图K5
System.out.println("\n\n=== 示例2：完全图K5 ===");
MaximumClique graph2 = new MaximumClique(5);
for (int i = 0; i < 5; i++) {
for (int j = i + 1; j < 5; j++) {
graph2.addEdge(i, j);
}
}
Set<Integer> cliqueK5 = graph2.bronKerboschPivot();
graph2.printClique(cliqueK5);
// 示例3：二分图（无三角形）
System.out.println("\n=== 示例3：二分图（最大团=2） ===");
MaximumClique graph3 = new MaximumClique(6);
graph3.addEdge(0, 3);
graph3.addEdge(0, 4);
graph3.addEdge(0, 5);
graph3.addEdge(1, 3);
graph3.addEdge(1, 4);
graph3.addEdge(1, 5);
graph3.addEdge(2, 3);
graph3.addEdge(2, 4);
graph3.addEdge(2, 5);
Set<Integer> cliqueBipartite = graph3.bronKerboschPivot();
graph3.printClique(cliqueBipartite);
}
}
四、复杂度分析
| 算法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 基本Bron-Kerbosch | O(3^(V/3)) | O(V) | 小规模图 |
| Pivot优化 | O(3^(V/3))（常数更小） | O(V) | 中等规模图 |
| 退化序优化 | O(d × V × 3^(d/3)) | O(V) | 稀疏图（d为退化度） |
| 贪心近似 | O(V³) | O(V) | 大规模图 |
Bron-Kerbosch算法在最坏情况下需要枚举所有极大团，而极大团的数量最多可达3^(V/3)。Pivot优化虽然不能改变最坏复杂度，但在实际应用中通常能减少大量递归调用。
五、应用场景
- 社交网络分析：发现紧密联系的社区或小团体
- 生物信息学：蛋白质相互作用网络中的功能模块
- 聚类分析：基于完全子图的密度聚类
- 推荐系统：找到具有共同偏好的最大用户群体
- 编码理论：纠错码的构造与优化
- 计算机视觉：特征点匹配中的一致性检验
六、总结
本文实现了最大团问题的多种求解方法，从经典的Bron-Kerbosch回溯算法到Pivot优化、退化序优化，再到贪心近似算法。对于小规模图，精确算法能够找到最优解；对于大规模图，贪心近似提供了可接受的替代方案。最大团问题作为NP完全问题的代表，其算法研究对理解计算困难性和设计高效启发式方法具有重要价值。
