find_cliques_recursive

find_cliques_recursive(G, nodes=None)

返回图中的所有极大团。

对于每个节点 v ，A V的最大集团 是包含 v . 最大的集团有时被称为 最大团 .

此函数返回一个遍历团的迭代器，每个团是一个节点列表。它是一个递归实现，因此可能会遇到递归深度问题，但出于教学原因而包含在内。有关非递归实现的信息，请参见 find_cliques() 。

此函数接受 nodes 只有包含所有这些的最大派系 nodes 都被退回了。如果需要一些特定的小集团，它可以大大加快运行时间。

参数

G网络X图表

nodes列表，可选(默认=无)

如果提供，则仅提供 最大团 包含中的所有节点 nodes 。如果 nodes 本身不是一个集团，则会引发ValueError。

返回

迭代器

极大团上的迭代器，每个团都是中的节点列表 G 。如果 nodes 中的所有节点的最大团 nodes 都是屈服的。集团的顺序是武断的。

加薪

ValueError

如果 nodes 不是一个小圈子。

参见

find_cliques

相同算法的迭代版本。

笔记

要获取所有极大团的列表，请使用 list(find_cliques_recursive(G)) 。但是，请注意，在最坏的情况下，此列表的长度可能与图中的节点数成指数关系。该函数在搜索期间只将当前候选节点列表保存在内存中，从而避免将所有集团存储在内存中。

该实现基于Bron和KerBosch(1973)发布的算法。 [1], 由富田、田中和高桥改编(2006) [2] 并在《卡泽尔与卡兰德》(2008)中进行了讨论 [3]. 有关非递归实现的信息，请参见 find_cliques() 。

该算法忽略了自循环和平行边，因为通常不使用这些边定义群。

工具书类

1

bron，c.和kerbosch，j.“算法457：寻找无向图的所有组别”。 ACM的通信 16，9（1973年9月），575-577.<http://portal.acm.org/ci典.cfm？doid=362342.362367>

2

Etsuji Tomita、Akira Tanaka、Haruhisa Takahashi，“产生所有最大群体和计算实验的最坏情况下的时间复杂性”， 理论计算机科学 ，第363卷，第1期，计算与组合学，第10届计算与组合学国际年会（Cocoon 2004），2006年10月25日，第28-42页<https://doi.org/10.1016/j.tcs.2006.06.015>

3

F.Cazals，C.Karande，“关于报告最大派系问题的说明”， 理论计算机科学 ，第407卷，第1-3期，2008年11月6日，第564-568页，<https://doi.org/10.1016/j.tcs.2008.05.010>