networkx.algorithms.bridges.has_bridges

has_bridges(G, root=None)

Decide whether a graph has any bridges.

A bridge in a graph is an edge whose removal causes the number of connected components of the graph to increase.

Parameters

• G (undirected graph)

• root (node (optional)) – A node in the graph G. If specified, only the bridges in the connected component containing this node will be considered.

Returns

Whether the graph (or the connected component containing root) has any bridges.

Return type

bool

Raises

NodeNotFound – If root is not in the graph G.

Examples

The barbell graph with parameter zero has a single bridge:

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

On the other hand, the cycle graph has no bridges:

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

Notes

This implementation uses the networkx.bridges() function, so it shares its worst-case time complexity, \(O(m + n)\), ignoring polylogarithmic factors, where \(n\) is the number of nodes in the graph and \(m\) is the number of edges.