Note
This documents the development version of NetworkX. Documentation for the current release can be found here.
networkx.algorithms.bridges.bridges¶

bridges
(G, root=None)[source]¶ 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.
 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 returned.
 Yields
 eedge
An edge in the graph whose removal disconnects the graph (or causes the number of connected components to increase).
 Raises
 NodeNotFound
If
root
is not in the graphG
.
Notes
This is an implementation of the algorithm described in _[1]. An edge is a bridge if and only if it is not contained in any chain. Chains are found using the
networkx.chain_decomposition()
function.Ignoring polylogarithmic factors, the worstcase 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.References
Examples
The barbell graph with parameter zero has a single bridge:
>>> G = nx.barbell_graph(10, 0) >>> list(nx.bridges(G)) [(9, 10)]