Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

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.