strongly_connected_components

strongly_connected_components(G)

在图的强连接组件中生成节点。

参数

G网络X图表

有向图。

返回

comp集合的生成元

G的每个强连通分支对应一个结点集的生成器。

加薪

NetworkXNotImplemented

如果g是无向的。

参见

connected_components

weakly_connected_components

kosaraju_strongly_connected_components

笔记

使用Tarjan的 algorithm[R827335e01166-1]_ 与Nuutila的 modifications[R827335e01166-2]_. 算法的非递归版本。

工具书类

1

深度优先搜索和线性图算法，R.Tarjan-Siam计算杂志1（2）：146-160，（1972）。

2

在有向图中寻找强连通分量。E.Nuutila和E.Soisalon Soinen信息处理信函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)