- 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. Bridges are also known as cut-edges, isthmuses, or cut arcs.
- 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
Gis a directed 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
The algorithm described in  requires a simple graph. If the provided graph is a multigraph, we convert it to a simple graph and verify that any bridges discovered by the chain decomposition algorithm are not multi-edges.
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)]