has_bridges#
- 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.
- Parameters:
- 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.
- Returns:
- bool
Whether the graph (or the connected component containing
root
) has any bridges.
- Raises:
- NodeNotFound
If
root
is not in the graphG
.- NetworkXNotImplemented
If
G
is a directed graph.
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.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