bridges#

bridges(G, root=None)[source]#

生成图中的所有桥。

图中的*桥*是指移除该边后会导致图的连通分量数量增加的边。等价地，桥是不属于任何环的边。桥也被称为割边、峡、或割弧。

Parameters:
G无向图
root节点（可选）

图 G 中的一个节点。如果指定，则只返回包含该节点的连通分量中的桥。

Yields:
e边

图中的一条边，移除该边会使图断开连接（或导致连通分量数量增加）。

Raises:
NodeNotFound

如果 root 不在图 G 中。

NetworkXNotImplemented

如果 G 是有向图。

Notes

这是[1]中描述的算法的实现。一条边是桥当且仅当它不包含在任何链中。链是通过 networkx.chain_decomposition() 函数找到的。

[1]中描述的算法需要一个简单图。如果提供的图是一个多重图，我们将其转换为简单图，并验证通过链分解算法发现的任何桥不是多重边。

忽略多项对数因子，最坏情况下的时间复杂度与 networkx.chain_decomposition() 函数相同，\(O(m + n)\)，其中 \(n\) 是图中的节点数，\(m\) 是边数。

References

Examples

参数为零的杠铃图有一个桥：

>>> G = nx.barbell_graph(10, 0)
>>> list(nx.bridges(G))
[(9, 10)]
On this page