最大团问题图例演示 - 穷举搜索与启发式

在一个无向图中，团（Clique）是指一个顶点子集，其中任意两个顶点之间都有边相连（即构成完全子图）。最大团是图中顶点数最多的团。最大团问题是图论中的经典NP完全问题，意味着对于一般图，不存在多项式时间的精确算法（除非P=NP）。它在社交网络分析、生物信息学、计算机视觉等领域有广泛应用。

极大团（Maximal Clique）：不能再添加任何其他顶点的团（即不是任何更大团的子集）。
最大团（Maximum Clique）：所有团中顶点数最多的团。

关键区别：最大团一定是极大团，但极大团不一定是最大团。例如，一个图可能同时存在大小为3的极大团和大小为5的最大团。本工具中穷举搜索找到的是最大团，而贪心启发式可能只找到极大团。

穷举搜索需要检查所有可能的顶点子集。对于n个顶点的图，共有2ⁿ个子集。对每个子集需要检查其中所有顶点对是否都有边，最坏情况需要O(n²)时间。总时间复杂度为O(2ⁿ · n²)。

本工具从大到小搜索（从大小为n的子集开始向下），一旦找到团就立即停止，因此实际运行时间取决于图的结构。对于8个顶点（256个子集），搜索几乎瞬间完成；对于10个顶点（1024个子集），仍然很快；但超过12个顶点（4096+子集）时可能明显变慢。

本工具实现的贪心启发式策略：按顶点度数降序排列，依次以每个顶点为起点构建团。构建过程中，维护候选集（与当前团中所有顶点相邻的顶点），每次从候选集中选择度数最高的顶点加入团，然后更新候选集。

⚠️ 贪心启发式不保证找到最大团。它可能陷入局部最优。例如，度数最高的顶点不一定属于最大团。本工具的"对比模式"会同时运行两种算法，直观展示贪心可能遗漏最优解的情况。启发式的优势在于速度——时间复杂度为O(n²·log n)级别，可处理大规模图。

• 社交网络分析：发现紧密联系的社群或朋友圈
• 生物信息学：蛋白质结构预测、基因表达数据分析
• 计算机视觉：特征匹配中的一致性检验
• 编码理论：寻找最大独立集（最大团在补图中的对应问题）
• 调度问题：寻找互不冲突的任务集合
• 网络安全：检测协同攻击的节点群组

快速上手：
1️⃣ 点击预设图例按钮加载示例图
2️⃣ 选择算法（推荐"对比两种算法"）
3️⃣ 调整演示速度
4️⃣ 点击"执行算法"观察搜索过程
5️⃣ 绿色节点 = 找到的最大团，金色边 = 团内的边

自定义图：使用"添加节点"按钮和模式切换（移动/连线/删除）来构建自己的图。"连线"模式下点击两个节点创建边。