find_cliques_recursive

find_cliques_recursive(G, nodes=None)

返回图中的所有最大团。

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

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

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

Parameters:

GNetworkX 图

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

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

Returns:

迭代器

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

Raises:

ValueError

如果 nodes 不是一个团。

See also

find_cliques

同一算法的迭代版本。参见文档字符串中的示例。

Notes

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

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

此算法忽略自环和平行边，因为团通常不定义为包含此类边。

References

[1]

Bron, C. 和 Kerbosch, J. “Algorithm 457: finding all cliques of an undirected graph”. Communications of the ACM 16, 9 (Sep. 1973), 575–577. <http://portal.acm.org/citation.cfm?doid=362342.362367>

[2]

Etsuji Tomita, Akira Tanaka, Haruhisa Takahashi, “The worst-case time complexity for generating all maximal cliques and computational experiments”, Theoretical Computer Science, Volume 363, Issue 1, Computing and Combinatorics, 10th Annual International Conference on Computing and Combinatorics (COCOON 2004), 25 October 2006, Pages 28–42 <https://doi.org/10.1016/j.tcs.2006.06.015>

[3]

F. Cazals, C. Karande, “A note on the problem of reporting maximal cliques”, Theoretical Computer Science, Volume 407, Issues 1–3, 6 November 2008, Pages 564–568, <https://doi.org/10.1016/j.tcs.2008.05.010>