经典的求解图的所有最大完全子图的算法

目录

一、算法原理

Bron–Kerbosch (R, P, X) 三集合定义

二、Java 完整实现

三、运行输出

四、逐段代码解析

1. 存储结构：邻接矩阵boolean[][] adj

2. bronKerbosch(R,P,X)递归核心

3. 辅助工具方法

4. 入口calc()初始化

五、算法优缺点与优化拓展

1. 原生 BK 缺点

2. 经典优化：Pivot 支点优化（BK-P）

3. 应用场景

六、极大团 vs 最大团总结

---

一、算法原理

Bron–Kerbosch (R, P, X) 三集合定义

• R：当前已选中构成团的顶点集合（结果集，正在构造的团）
• P：候选顶点集合：所有可以加入 R、且和 R 中所有点相邻的顶点
• X：排除顶点集合：已经枚举过、不能再组合出新极大团的顶点（去重，避免重复生成同一个团）递归逻辑：

1. 若 P=∅∧X=∅：R 是一个极大团，保存结果；
2. 依次从 P 取出顶点 v：
   • 递归：BK(R∪{v},P∩N(v),X∩N(v))，N(v)是v的邻接点集合
   • P=P−{v}，X=X∪{v}（回溯，不再用 v 组合）

二、Java 完整实现

import java.util.*; /** * 极大团&最大团：Bron–Kerbosch基础回溯算法 */ public class MaximalClique { // 邻接矩阵存图: adj[u][v]=true 代表u、v有边相连 private final boolean[][] adj; private final int vertexNum; // 存储所有找到的极大团 private final List<List<Integer>> allMaximalCliques = new ArrayList<>(); // 全局保存最大团 private List<Integer> maximumClique = new ArrayList<>(); public MaximalClique(boolean[][] graph) { this.adj = graph; this.vertexNum = graph.length; } /** * 递归核心: Bron–Kerbosch(R,P,X) * @param R 当前团顶点 * @param P 候选集合 * @param X 排除集合 */ private void bronKerbosch(List<Integer> R, Set<Integer> P, Set<Integer> X) { // 终止条件：P、X都空，R是极大团 if (P.isEmpty() && X.isEmpty()) { List<Integer> clique = new ArrayList<>(R); allMaximalCliques.add(clique); // 更新全局最大团 if (clique.size() > maximumClique.size()) { maximumClique = clique; } return; } // 遍历候选集合中每个顶点v Set<Integer> pCopy = new HashSet<>(P); for (int v : pCopy) { // 新候选：P ∩ N(v) 只保留v的邻居 Set<Integer> newP = getIntersection(P, getNeighbors(v)); // 新排除：X ∩ N(v) Set<Integer> newX = getIntersection(X, getNeighbors(v)); // 选中v加入R，递归 R.add(v); bronKerbosch(R, newP, newX); // 回溯撤销 R.remove(R.size() - 1); // v从候选移除、加入排除集 P.remove(v); X.add(v); } } // 获取顶点v所有邻接点 private Set<Integer> getNeighbors(int v) { Set<Integer> neighbors = new HashSet<>(); for (int i = 0; i < vertexNum; i++) { if (adj[v][i] && v != i) { neighbors.add(i); } } return neighbors; } // 求两个集合交集 A ∩ B private Set<Integer> getIntersection(Set<Integer> a, Set<Integer> b) { Set<Integer> res = new HashSet<>(); for (int num : a) { if (b.contains(num)) res.add(num); } return res; } // 入口方法，启动算法 public void calc() { List<Integer> R = new ArrayList<>(); Set<Integer> P = new HashSet<>(); Set<Integer> X = new HashSet<>(); // 初始化候选P：所有顶点 0~n-1 for (int i = 0; i < vertexNum; i++) { P.add(i); } bronKerbosch(R, P, X); } // 获取全部极大团 public List<List<Integer>> getAllMaximalCliques() { return allMaximalCliques; } // 获取最大团 public List<Integer> getMaximumClique() { return maximumClique; } // 测试用例 public static void main(String[] args) { /* 测试图:5个顶点 0,1,2,3,4 边: 0-1,0-2,1-2,2-3,3-4 极大团：[0,1,2],[2,3],[3,4] 最大团：[0,1,2] size=3 */ int n = 5; boolean[][] graph = new boolean[n][n]; // 添加边 graph[0][1] = graph[1][0] = true; graph[0][2] = graph[2][0] = true; graph[1][2] = graph[2][1] = true; graph[2][3] = graph[3][2] = true; graph[3][4] = graph[4][3] = true; MaximalClique solver = new MaximalClique(graph); solver.calc(); System.out.println("===所有极大MaximalClique==="); for (List<Integer> clique : solver.getAllMaximalCliques()) { System.out.println(clique); } System.out.println("\n===最大MaximumClique==="); System.out.println(solver.getMaximumClique()); } }

三、运行输出

===所有极大MaximalClique=== [0, 1, 2] [2, 3] [3, 4] ===最大MaximumClique=== [0, 1, 2]

四、逐段代码解析

1. 存储结构：邻接矩阵boolean[][] adj

无向图：adj[u][v]=adj[v][u]=true代表两点连通，适合小规模图；百万级顶点改用 ** 邻接表List<Set<Integer>> adj** 优化。

2.bronKerbosch(R,P,X)递归核心

1. 终止分支P.isEmpty() && X.isEmpty()P空：没有任何顶点可以继续扩充当前团 R；X空：没有遗漏的回溯分支，因此 R 是极大团，存入全局集合。
2. 遍历每个候选 v ∈ P
   • newP = P ∩ N(v)：新候选只能是 v 的邻居，保证加入后全互连（团定义：任意两点相连）；
   • newX = X ∩ N(v)：排除集同步只保留 v 邻居，避免重复枚举；
   • 前序：R.add (v) 向下递归；回溯：R.remove () 撤销选择；
   • P.remove(v),X.add(v)：v 不再参与后续同分支枚举，防止重复生成相同团。

3. 辅助工具方法

• getNeighbors(v)：遍历邻接矩阵，返回 v 所有相邻顶点集合；
• getIntersection(A,B)：手动求集合交集，等价retainAll，便于理解算法数学定义。

4. 入口calc()初始化

• R=∅：初始没有选中任何点；
• P={0,1,2...n−1}：全部顶点作为初始候选；
• X=∅：初始无排除顶点。

五、算法优缺点与优化拓展

1. 原生 BK 缺点

原生无支点优化，稠密图、顶点 > 50 时递归爆炸（指数复杂度O(3n/3)，NP 完全问题，无多项式解法）。

2. 经典优化：Pivot 支点优化（BK-P）

优化思路：选支点 u∈P∪X，只枚举 P-N (u) 中的顶点，大幅减少递归分支，优化后实际速度提升数倍：

// 支点优化简易改造：选支点u，遍历 P \ N(u) Optional<Integer> pivot = P.stream().findAny(); Set<Integer> candidates = new HashSet<>(P); if(pivot.isPresent()){ int u = pivot.get(); candidates.removeAll(getNeighbors(u)); } for(int v : candidates){ ... }

3. 应用场景

• 社交网络社群挖掘（团 = 紧密社群）；
• 图着色、蛋白质结构匹配、组合优化、电路布线。

六、极大团 vs 最大团总结

1. 极大团：局部不能再加点，结果不止一个（代码 allMaximalCliques）；
2. 最大团：全局顶点数最多的那个极大团（代码 maximumClique）；

该回溯是暴力枚举所有合法极大团，是图论团问题最基础标准实现。