强连通分量#

strongly_connected_components(G)[源代码]#

生成图中强连通分量中的节点。

参数：

GNetworkX 图: 一个有向图。

返回：

comp集合生成器: 一个节点集合的生成器，G 的每个强连通分量对应一个集合。

抛出：

NetworkXNotImplemented: 如果 G 是无向图。

另请参阅

连通分量
弱连通分量
Kosaraju强连通分量

注意

使用 Tarjan 算法[R827335e01166-1]_ 并结合 Nuutila 的改进[R827335e01166-2]_。算法的非递归版本。

参考资料

[1]

Depth-first search and linear graph algorithms, R. Tarjan SIAM Journal of Computing 1(2):146-160, (1972).

[2]

On finding the strongly connected components in a directed graph. E. Nuutila and E. Soisalon-Soinen Information Processing Letters 49(1): 9-14, (1994)..

示例

生成一个强连通分量的排序列表，最大的在前。

>>> G = nx.cycle_graph(4, create_using=nx.DiGraph())
>>> nx.add_cycle(G, [10, 11, 12])
>>> [
...     len(c)
...     for c in sorted(nx.strongly_connected_components(G), key=len, reverse=True)
... ]
[4, 3]

如果只需要最大的分量，使用 max 会比 sort 更有效率。

>>> largest = max(nx.strongly_connected_components(G), key=len)