桥#
- bridges(G, root=None)[source]#
生成图中的所有桥。
图中的*桥*是一条边，移除该边会使图的连通分量数量增加。等效地，桥是不属于任何环的边。桥也被称为割边、地峡或割弧。
- 参数:
- G无向图
- root节点 (可选)
图
G中的一个节点。如果指定，将只返回包含此节点的连通分量中的桥。
- 返回（生成器）:
- e边
图中的一条边，移除该边会断开图（或导致连通分量数量增加）。
- 抛出异常:
- NodeNotFound
如果
root不在图G中。- NetworkXNotImplemented
如果
G是有向图。
注意
这是 [1] 中描述的算法的一种实现。一条边是桥当且仅当它不包含在任何链中。链使用
networkx.chain_decomposition()函数找到。[1] 中描述的算法需要一个简单图。如果提供的图是多重图，我们将其转换为简单图，并验证链分解算法发现的任何桥都不是多重边。
忽略多对数因子，最坏情况下的时间复杂度与
networkx.chain_decomposition()函数相同，为 \(O(m + n)\)，其中 \(n\) 是图中的节点数，\(m\) 是边数。参考文献
示例
参数为零的杠铃图有一个单一的桥
>>> G = nx.barbell_graph(10, 0) >>> list(nx.bridges(G)) [(9, 10)]