has_bridges

has_bridges(G, root=None)

决定一个图是否有任何桥。

A 桥 在图中是一条边，它的删除会导致图中连接的组件的数量增加。

参数

G无向图

root节点(可选)

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

返回

布尔尔

图形（或包含 root ）有任何桥梁。

加薪

NodeNotFound

如果 root 不在图表中 G .

笔记

此实现使用 networkx.bridges() 函数，所以它分担了最坏情况下的时间复杂性， \(O(m + n)\) ，忽略多对数因子，其中 \(n\) 是图形中的节点数， \(m\) 是边数。

实例

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

>>> G = nx.barbell_graph(10, 0)
>>> nx.has_bridges(G)
True

另一方面，循环图没有桥梁：

>>> G = nx.cycle_graph(5)
>>> nx.has_bridges(G)
False