find_cliques

find_cliques(G, nodes=None)

返回无向图中的所有极大团。

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

此函数返回一个团的迭代器，每个团都是一个节点列表。它是一个迭代实现，因此不会遇到递归深度问题。

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

参数：

GNetworkX 图

一个无向图。

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

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

返回：

迭代器

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

引发：

ValueError

如果 nodes 不是一个团。

另请参阅

find_cliques_recursive

同一算法的递归版本。

注意

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

此实现基于 Bron 和 Kerbosch (1973) 发表的算法 [1]，并由 Tomita, Tanaka 和 Takahashi (2006) [2] 进行了改进，在 Cazals 和 Karande (2008) [3] 中进行了讨论。它基本上展开了参考文献中使用的递归，以避免递归栈深度问题（有关递归实现，请参阅 find_cliques_recursive()）。

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

参考文献

[1]

Bron, C. 和 Kerbosch, J. “算法 457：查找无向图的所有团”。ACM 通讯 16, 9 (1973 年 9 月)，575–577 页。 <http://portal.acm.org/citation.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>

示例

>>> from pprint import pprint  # For nice dict formatting
>>> G = nx.karate_club_graph()
>>> sum(1 for c in nx.find_cliques(G))  # The number of maximal cliques in G
36
>>> max(nx.find_cliques(G), key=len)  # The largest maximal clique in G
[0, 1, 2, 3, 13]

最大极大团的大小称为图的*团数*，可以直接通过以下方式找到：

>>> max(len(c) for c in nx.find_cliques(G))
5

还可以计算 G 中包含给定节点的极大团数量。以下代码生成一个以节点为键、以 G 中包含该节点的极大团数量为值的字典：

>>> pprint({n: sum(1 for c in nx.find_cliques(G) if n in c) for n in G})
{0: 13,
 1: 6,
 2: 7,
 3: 3,
 4: 2,
 5: 3,
 6: 3,
 7: 1,
 8: 3,
 9: 2,
 10: 2,
 11: 1,
 12: 1,
 13: 2,
 14: 1,
 15: 1,
 16: 1,
 17: 1,
 18: 1,
 19: 2,
 20: 1,
 21: 1,
 22: 1,
 23: 3,
 24: 2,
 25: 2,
 26: 1,
 27: 3,
 28: 2,
 29: 2,
 30: 2,
 31: 4,
 32: 9,
 33: 14}

或者，类似地，计算 G 中包含给定节点的极大团。例如，包含节点 31 的 4 个极大团：

>>> [c for c in nx.find_cliques(G) if 31 in c]
[[0, 31], [33, 32, 31], [33, 28, 31], [24, 25, 31]]