- has_bridges(G, root=None)[source]#
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.
- Gundirected graph
- rootnode (optional)
A node in the graph
G. If specified, only the bridges in the connected component containing this node will be considered.
Whether the graph (or the connected component containing
root) has any bridges.
rootis not in the graph
Gis a directed graph.
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.
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