最大团问题(Bk 框架)
839 字
4 分钟
最大团问题(Bk 框架)
最大团问题
完全子图(团): 是指在给定无向图中 ,任意两个顶点之间存在边相连的子图。
最大完全子图 : 指所有完全子图中, 顶点数最多的完全子图。
完全图: 图中任意两点都有一条边相连的图。
团(clique) :给定一个无向图 G=(V,E),团就是图G 的一个完全子图 。
极大团(maximal clique): 在图G 中,如果一个团不被其他任何一个团所包含 , 即它不是其他任一团的真子集, 则该团为图G 的极大团。
最大团(maximum cllique) : 图G中最大的极大团为最大团。

最大团问题:(回溯)
.B4L9lVID_Z19UrUn.webp)
时间复杂度O():
- 每个顶点 都有选 或不选 两种可能 所以递归搜索树最多有O() 个节点
- 在一个节点中 ,
for i=1 to n最多检查n 次 ,耗时O(n)
Bk 框架
思路: 选取一个节点 , 从这个节点的邻节点随机选取一个节点 , 再从这两个节点的共同邻节点选取一个节点,依次类推 , 每次都从已经选取过的共同邻节点选取一个节点加入团 ,直到再也找不到共同邻节点,形成的团就是极大团。
剪枝: 对某个节点进行过极大团搜索 , 而 的当前团的邻节点, 那么将 加入到当前团 ,形成的团已经被搜索过了 (可以通过数组S来保存已经被搜索过的节点)
S 集合的形成 :
1.父节点继承
- 已经 访问过的兄弟节点
最大团回溯算法 2
1: 输入:图 G = (V, E)2: 初始化:R ← ∅, P ← V, S ← ∅, maxNumber ← 0, maxNodes ← ∅ //R 表示当前团的顶点数 , P代表当前团的共同邻居 ,S 代表访问过的节点3: maxClique2(R, P, S) ;
maxClique2(R, P, S)1: if P = ∅ then // 到达叶子节点 递归出口2: if |R| > maxNumber then3: maxNumber ← |R|4: maxNodes[] ← R5: end if6: end if
7: for each v ∈ P do8: if v ∈ S then // 从P中选取的点在S(访问过) 中 ,丢弃 (剪枝)9: continue10: end if11: R' ← R ∪ {v} // 更新R,p ,S12: N ← v 的邻节点13: P' ← P ∩ N14: maxClique2(R', P', S) // 当递归完 更新S15: S ← S ∪ {v}16: end forAlgorithm 66 Bron-Kerbosch 算法
1: 输入:图 G = (V, E);2: 初始化:R ← ∅, P ← V, S ← ∅, max_Number ← 0, max_Nodes ← ∅;3: Bron-Kerbosch(R, P, S);
Bron-Kerbosch(R, P, S)1: if P = ∅ and S = ∅ then // 3️⃣ 因此 相当于 没有共同邻居p= 空集 以及 当前团的邻节点没有有已经被搜索过的节点 则表明 是极大团12: if |R| > max_Number then3: max_Number ← |R|;4: max_Nodes[] ← R;5: end if6: end if7: for each v ∈ P do8: Bron-Kerbosch(R ∪ v, P ∩ N(v), S ∩ N(v));9: S ← S ∪ v; // v 已经处理过了 , s 一直保留处理过的节点 1️⃣10: P ← P \ v; // v已经出过了 直接拿掉 2️⃣11: end for- S: 可以表示当前团的邻节点中已经被搜索过的节点
- p: 可以表示当前团的邻节点中未被搜索过的节点

支持与分享
如果这篇文章对你有帮助,欢迎分享给更多人或打赏支持!
相关文章智能推荐
1
Firefly 代码块示例
文章示例在Firefly中使用表达性代码的代码块在 Markdown 中的外观。
2
Firefly 布局系统详解
博客指南深入了解 Firefly 的布局系统,包括侧边栏布局(左侧/双侧)和文章列表布局(列表/网格),以及自适应网格列数。
3
Firefly Wiki Link 内部链接示例
博客指南在 Firefly 文章中使用 Obsidian 风格的 Wiki Link 内部链接,并自动生成文章链接卡片。
4
Firefly 一款清新美观的 Astro 博客主题模板
文章示例Firefly 是一款基于 Astro 框架和 Fuwari 模板开发的清新美观且现代化个人博客主题模板,专为技术爱好者和内容创作者设计。该主题融合了现代 Web 技术栈,提供了丰富的功能模块和高度可定制的界面,让您能够轻松打造出专业且美观的个人博客网站。
5
Firefly 简单使用指南
博客指南如何使用 Firefly 博客模板。
随机文章随机推荐














