- bridges(G, root=None)¶
Generate all bridges in a graph.
A bridge in a graph is an edge whose removal causes the number of connected components of the graph to increase. Equivalently, a bridge is an edge that does not belong to any cycle.
- Gundirected graph
- rootnode (optional)
A node in the graph
G. If specified, only the bridges in the connected component containing this node will be returned.
An edge in the graph whose removal disconnects the graph (or causes the number of connected components to increase).
rootis not in the graph
This is an implementation of the algorithm described in _. An edge is a bridge if and only if it is not contained in any chain. Chains are found using the
Ignoring polylogarithmic factors, the worst-case time complexity is the same as the
networkx.chain_decomposition()function, \(O(m + n)\), 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) >>> list(nx.bridges(G)) [(9, 10)]