has_bridges

has_bridges(G, root=None)

判断图是否包含任何桥。

图中的桥是指移除后会导致图的连通分量数量增加的边。

参数:

G无向图

root节点（可选）

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

返回:

bool

图（或包含 root 的连通分量）是否包含任何桥。

引发:

NodeNotFound

如果 root 不在图 G 中。

NetworkXNotImplemented

如果 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