has_bridges

has_bridges(G, root=None)

确定一个图是否包含任何桥。

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

Parameters:

G无向图

root节点（可选）

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

Returns:

bool

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

Raises:

NodeNotFound

如果 root 不在图 G 中。

NetworkXNotImplemented

如果 G 是有向图。

Notes

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

Examples

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

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

另一方面，循环图没有桥:

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