find_cliques_recursive

find_cliques_recursive(G, nodes=None)

返回图中所有的极大团。

对于每个节点v，v 的极大团是包含v的最大的完全子图。最大的极大团有时被称为最大团。

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

此函数接受一个 nodes 列表，并且仅返回包含所有这些 nodes 的极大团。如果需要查找特定的团，这可以显著加快运行时间。

参数:

GNetworkX 图

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

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

返回:

迭代器

一个包含极大团的迭代器，每个极大团都是 G 中的节点列表。如果提供了 nodes，则仅生成包含 nodes 中所有节点的极大团。团的顺序是任意的。

引发:

ValueError

如果 nodes 不是一个团。

另请参阅

find_cliques

同一算法的迭代版本。有关示例请参阅文档字符串。

注意

要获取所有极大团的列表，请使用 list(find_cliques_recursive(G))。但是请注意，在最坏情况下，此列表的长度可能是图节点数的指数级。此函数通过在搜索过程中仅在内存中保留当前候选节点列表来避免将所有团存储在内存中。

此实现基于 Bron 和 Kerbosch (1973) [1] 发表的算法，并经 Tomita, Tanaka 和 Takahashi (2006) [2] 改编以及 Cazals 和 Karande (2008) [3] 讨论。对于非递归实现，请参阅 find_cliques()。

此算法忽略自环和并行边，因为团在常规定义中不包含此类边。

参考文献

[1]

Bron, C. and Kerbosch, J. “算法 457：寻找无向图的所有团”。Communications of the ACM 16, 9 (1973 年 9 月), 575–577。<http://portal.acm.org/citation.cfm?doid=362342.362367>

[2]

Etsuji Tomita, Akira Tanaka, Haruhisa Takahashi, “生成所有极大团的最坏时间复杂度和计算实验”, Theoretical Computer Science, Volume 363, Issue 1, Computing and Combinatorics, 第十届国际计算与组合学年会 (COCOON 2004), 2006 年 10 月 25 日, 页码 28–42 <https://doi.org/10.1016/j.tcs.2006.06.015>

[3]

F. Cazals, C. Karande, “关于报告极大团问题的一个注记”, Theoretical Computer Science, Volume 407, Issues 1–3, 2008 年 11 月 6 日, 页码 564–568, <https://doi.org/10.1016/j.tcs.2008.05.010>