桥梁

bridges(G, root=None)

在图中生成所有桥。

A 桥牌 图中有一条边，它的去掉会导致图的连通分支的数量增加。等同地，桥是不属于任何循环的边。桥梁也称为切割边、地峡或切割弧线。

参数

G无向图

root节点(可选)

图中的一个节点 G 。如果指定，则只返回包含此节点的已连接组件中的网桥。

产量

e边缘

图中的一条边，它的移除会断开图的连接(或导致连通分量的数量增加)。

加薪

NodeNotFound

如果 root 不在图表中 G .

笔记

这是中描述的算法的实现 [1]. 当且仅当边不包含在任何链中时，它才是桥。链是使用 networkx.chain_decomposition() 功能。

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

忽略多对数因素，最坏情况下的时间复杂度与 networkx.chain_decomposition() 函数， \(O(m + n)\) ，在哪里 \(n\) 是图形中的节点数， \(m\) 是边数。

工具书类

1(1,2)

https://en.wikipedia.org/wiki/bridge_u28graph_theory%29 bridge-finding_with_chain_分解

实例

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

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