在图论的世界里，有一个非常经典且具有挑战性的问题：如何在错综复杂的网络关系中，找出那个紧密连接的小团体？具体来说，如果给你一个包含 N 个节点和 E 条边的无向图，以及一个目标值 K，你的任务是找出图中所有构成 K 大小团的节点集合。
在这篇文章中，我们将不仅探讨这一问题的理论解法，还将深入到代码层面，手把手教你如何实现它。无论你是正在准备算法面试，还是正在处理实际的社交网络分析任务，我相信你都会有所收获。
什么是“团”？
在正式开始之前，让我们先明确一下核心概念。想象一下社交网络中的“朋友圈”。如果图中的每两个节点之间都有一条边相连，那么这些节点就构成了一个“团”。简单来说，团是指图的一个完全子图（Complete Subgraph）。在这个子图中，任意两个顶点都是相邻的。
寻找大小为 K 的团（K-Clique 问题）是计算机科学中的一个 NP 完全问题。这意味着随着图规模的增加，找到所有团的时间复杂度会呈指数级增长。但对于中小规模的数据或者特定的 K 值，我们依然可以通过巧妙的算法来高效求解。
问题示例
让我们通过一个直观的例子来理解题目要求。观察下面的无向图：
> !示例图示
输入： N = 5, 边[] = { {1, 2}, {2, 3}, {3, 1}, {4, 3}, {4, 5}, {5, 3} }, K = 3
输出：
1 2 3
3 4 5
解释：
我们可以清楚地看到，节点 {1, 2, 3} 之间两两相连，构成了一个三角形（即大小为 3 的团）；同样，节点 {3, 4, 5} 之间也是两两互联，形成了另一个团。没有其他的节点组合能满足这一条件。
再看一个例子：
输入： N = 4, 边[] = { {1, 2}, {2, 3}, {3, 1}, {4, 3} }, K = 3
输出：
1 2 3
解释：
这次，只有子图 {1, 2, 3} 构成了完全子图。虽然节点 4 与节点 3 相连，但它并没有与节点 1 或节点 2 相连，因此无法加入这个“朋友圈”。
核心思路：回溯与递归
为了找到所有大小为 K 的团，最直观的方法是尝试所有可能的节点组合，并检查它们是否构成了完全图。这听起来像是一个排列组合问题，而解决这类问题最强大的工具之一就是递归（Recursion），或者更具体地说是回溯法（Backtracking）。
#### 算法设计思路
我们可以这样设计我们的搜索策略：
- 剪枝：度数检查。首先，一个节点要成为大小为 K 的团的一部分，它的度数（连接的边数）至少必须为 K-1。如果图中有节点度数小于 K-1，我们可以直接忽略它们，这能大大减少搜索空间。
- 逐步构建。我们需要构建一个递归函数，它维护一个当前的“候选集合”。在递归的每一步，我们尝试向这个集合中添加一个新的节点。
- 完全性检查。在添加新节点之前，我们有一个硬性条件：新加入的节点必须与当前集合中已有的所有节点都相连。只有满足这个条件，当前的集合才有可能最终演变成一个团。
- 递归推进。如果当前集合大小还没达到 K，我们就继续寻找下一个符合条件的节点进行递归调用。
- 达成目标。如果当前集合的大小正好等于 K，恭喜，我们找到了一个解！把它打印出来即可。
#### 详细步骤解析
让我们把上述思路转化为具体的操作步骤。假设我们需要一个函数 findCliques(i, l, s)，其中：
i：当前搜索的起始节点索引（为了避免重复，我们只考虑编号大于当前已选最大节点的节点）。l：当前正在构建的团的长度（大小）。s：我们需要的目标团的大小（即 K）。
算法流程如下：
- 确定搜索范围：我们需要从节点 INLINECODEa04fb9a4 开始，一直搜索到节点 INLINECODE4363ed46。这里有一个优化技巧：循环的上限不一定要到 INLINECODEb46d4acc。如果我们还需要 INLINECODEf1f8dad8 个节点，且剩下的节点数不足以满足这个数量，就可以提前终止。所以，循环范围可以设定为 INLINECODEd06eb5ae 从 INLINECODEf969ddb5 到
n - (s - l)。
- 筛选候选节点：在循环中，对于每一个候选节点 INLINECODE07f54ac8，首先检查它的度数。如果 INLINECODEf6015fcf，说明这个节点即使连上所有可能的邻居，也凑不够 K 个人的团，直接跳过（continue）。
- 尝试加入节点：将节点 INLINECODEe99b2c1a 加入到我们的临时存储数组 INLINECODE0b6924e7 的第
l个位置。
- 验证团属性：这是最关键的一步。调用 INLINECODE639df717 函数来检查当前的 INLINECODEf147290c 数组中的节点是否依然构成一个团。
* 这个 INLINECODE02c325b5 函数的工作原理是：遍历 INLINECODE5adc4556 中现有的所有节点对，检查它们在邻接矩阵中是否有边相连。如果有一对不相连，返回 false。
- 递归或输出：
* 如果 INLINECODE8fd82a39 返回 INLINECODEfeca7b4c，说明目前的组合是有效的。
* 此时检查 INLINECODE6e3dfe31 是否等于 INLINECODEf6d1cad7（即当前大小 INLINECODEe2eeeb20 是否等于 INLINECODEfad7d141）。如果是，说明我们找齐了 K 个人，调用打印函数。
* 如果 INLINECODE29a1fdd8 还小于 INLINECODEeaf97b5d，说明还需要继续找人，于是递归调用 findCliques(j, l + 1, s)，继续寻找下一个节点。
代码实现详解
接下来，让我们把上述逻辑转化为具体的代码。我们将使用邻接矩阵（Adjacency Matrix）来存储图的结构，因为这在判断两点是否相连时非常高效（O(1) 时间复杂度）。
#### 1. 数据结构定义
首先，我们需要一些全局变量来存储图的信息和中间结果。
// 定义最大节点数，防止数组越界
const int MAX = 100;
// store数组用于临时存储当前正在探索的团的节点路径
// store[1] 到 store[l] 是当前的有效节点
int store[MAX], n;
// graph[MAX][MAX] 是图的邻接矩阵表示
// graph[i][j] = 1 表示节点 i 和 j 之间有边，0 表示无边
int graph[MAX][MAX];
// d数组存储每个节点的度数（即连接了多少个其他节点）
int d[MAX];
#### 2. 检查是否构成团：is_clique
这是我们的“安检”函数。每当我们要接纳一个新成员进入当前的小圈子时，都要确认新成员与圈子里的每个人都认识。
// b 参数表示当前 store 数组中有效节点的数量（即当前尝试构成的团的大小）
bool is_clique(int b)
{
// 遍历当前团中的所有节点对
// 索引从 1 开始（为了与逻辑中的节点编号对应，虽然数组从0开始）
for (int i = 1; i < b; i++) {
for (int j = i + 1; j < b; j++) {
// 如果在邻接矩阵中，store[i] 和 store[j] 之间没有边
// 说明当前集合不是完全图，返回 false
if (graph[store[i]][store[j]] == 0)
return false;
}
}
// 如果所有节点对之间都有边，返回 true
return true;
}
#### 3. 核心递归函数：findCliques
这是引擎室，驱动着整个搜索过程。
// i: 上一次加入的节点索引（本次搜索的起始点）
// l: 当前团的大小（或者理解为 store 数组中下一个可用的空位索引）
// s: 我们的目标团的大小 K
void findCliques(int i, int l, int s)
{
// 尝试从 i+1 开始的每个节点 j
// 循环条件 j <= n - (s - l) 是一个重要的剪枝优化
// 它确保剩下的节点数量足够让我们凑齐 s 个
for (int j = i + 1; j = s-1 时，它才有可能属于大小为 s 的团
if (d[j] >= s - 1) {
// 1. 将候选节点 j 放入当前集合
store[l] = j;
// 2. 检查加入了 j 之后，当前集合是否仍然构成一个团
// 注意这里传入 l + 1，表示检查 store[1...l] 这 l 个节点
if (is_clique(l + 1)) {
// 3. 如果是团，检查大小是否已达到目标 s
// 这里用 l < s 来判断是否还需要继续递归
if (l < s) {
// 大小还不够，递归调用，去寻找下一个节点
// 下一轮搜索从 j 之后开始
findCliques(j, l + 1, s);
}
else {
// 大小已达到 s (注意因为传入的是l+1作为大小判断依据，这里逻辑是l < s，
// 若 l == s-1，说明加入这个j后大小为s，此时应打印。
// 原文代码中 print函数参数是 size，通常传 l+1 比较严谨，
// 但根据递归逻辑，如果走到 else 分支，说明我们刚刚填充了 store[l] 且总大小有效)
print(l + 1);
}
}
}
}
}
#### 4. 辅助函数与主函数
我们需要一个打印函数来输出结果，以及 main 函数来驱动整个程序。
// 打印当前找到的团
// 参数 l 表示当前团的大小
void print(int l)
{
for (int i = 1; i < l; i++)
cout << store[i] << " ";
cout << ", ";
}
// Driver code
int main()
{
// 示例图的边列表
int edges[][2] = { { 1, 2 },
{ 2, 3 },
{ 3, 1 },
{ 4, 3 },
{ 4, 5 },
{ 5, 3 } };
// 目标团的大小
int k = 3;
// 计算边的数量
int size = sizeof(edges) / sizeof(edges[0]);
// 节点总数
n = 5;
// 1. 根据边列表构建邻接矩阵并计算度数
for (int i = 0; i < size; i++) {
// 获取边的两个端点
int u = edges[i][0];
int v = edges[i][1];
// 标记 u 和 v 之间有边（无向图是对称的）
graph[u][v] = 1;
graph[v][u] = 1;
// 增加两个端点的度数
d[u]++;
d[v]++;
}
// 2. 开始查找大小为 k 的所有团
// 初始调用：从索引0开始，当前长度设为1（准备放入第一个点），目标大小k
findCliques(0, 1, k);
return 0;
}
性能分析与优化建议
实现上述算法后，你可能会关心它的效率。让我们来分析一下。
时间复杂度：在最坏的情况下，这是一个 NP 难问题。我们需要检查几乎所有可能的节点组合。对于每一个递归层，我们都在尝试添加新节点，因此最坏时间复杂度大约是 O(N^K) 或 O(3^(N/3))（对于最大团问题）。这意味着当 N 很大（例如超过 100）且 K 较大时，程序可能会运行得比较慢。
空间复杂度：主要取决于递归栈的深度和存储图的空间。空间复杂度为 O(N^2)（邻接矩阵） + O(K)（递归深度）。
优化建议：
- 使用邻接表代替邻接矩阵：对于稀疏图（边数远小于 N^2），邻接表能节省大量内存，并且遍历邻居时更快。但在判断两节点是否相连时，邻接矩阵是 O(1)，而邻接表最坏是 O(Degree)。这里我们使用矩阵主要是为了
is_clique检查的方便。 - Bron-Kerbosch 算法：如果你需要处理更大的图或者寻找所有的最大团（不仅仅是大小为 K 的），Bron-Kerbosch 算法及其带 Pivot 的优化版本是目前解决此类问题的行业标准算法，效率远高于基础的回溯法。
- 更严格的剪枝：在递归之前，可以预先计算邻居集合的交集。如果当前候选集合与剩余所有节点的邻居交集大小小于 K – current_size，那么可以提前终止该分支的搜索。
常见陷阱与解决方案
在实际编写或调试这段代码时，你可能会遇到以下问题：
- 节点编号从 0 还是 1 开始？ 本例中为了清晰，假设节点编号是 1 到 N。如果你的图节点编号是 0 到 N-1，记得调整循环范围和数组索引。
- 重复输出：如果不使用起始索引 INLINECODE1cdfa287 来限制后续搜索的范围（即总是从 0 开始搜索），你会发现同一个团会被以不同的顺序打印多次（例如 1-2-3 和 3-2-1）。通过强制 INLINECODE4d2bd3fe，我们保证了团内节点的有序性，从而避免重复。
- 栈溢出：如果 K 非常大（例如接近 N），递归深度会很大。虽然对于 K-Clique 问题 K 通常较小，但遇到栈溢出时，可以考虑将递归改为迭代的栈实现。
总结与进阶方向
通过这篇文章，我们一步步地拆解了“寻找无向图中所有大小为 K 的团”这一问题。从理解什么是“团”，到利用递归和回溯思想设计算法，再到具体的 C++ 代码实现和细节优化，我相信现在你对图论搜索算法有了更深的理解。
这个算法不仅仅是一个学术练习，它在社交网络分析（寻找紧密社群）、生物信息学（蛋白质相互作用网络分析）等领域都有广泛的应用。
接下来，你可以尝试：
- 修改代码，使其统计输出团的总数，而不是直接打印。
- 尝试实现 Bron-Kerbosch 算法来寻找图中的最大团，对比两者的性能差异。
- 如果边是带权重的，我们如何寻找总权重最大的 K 团？这将是一个更有趣的进阶挑战。
希望这篇文章对你的技术旅程有所帮助！快去试试吧，如果有任何问题，欢迎随时交流。