strongly_connected_components_recursive

strongly_connected_components_recursive(G)

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

算法的递归版本。

参数

G网络X图表

有向图。

返回

comp集合的生成元

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

加薪

NetworkXNotImplemented

如果g是无向的。

参见

connected_components

笔记

使用Tarjan的 algorithm[Re7cb971df765-1]_ 与Nuutila的 modifications[Re7cb971df765-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_recursive(G), key=len, reverse=True
...     )
... ]
[4, 3]

如果只需要最大的组件，那么使用max而不是sort会更有效。

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

要创建组件的诱导子图，请使用：>>>s= [G.subgraph(c).copy() for c in nx.weakly_connected_components(G)]