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:  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 returned.
Yields: e (edge) – An edge in the graph whose removal disconnects the graph (or causes the number of connected components to increase).
Raises: NodeNotFound
– Ifroot
is not in the graphG
.Examples
The barbell graph with parameter zero has a single bridge:
>>> G = nx.barbell_graph(10, 0) >>> list(nx.bridges(G)) [(9, 10)]
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
[1] https://en.wikipedia.org/wiki/Bridge_%28graph_theory%29#BridgeFinding_with_Chain_Decompositions