Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

# 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. e (edge) – An edge in the graph whose removal disconnects the graph (or causes the number of connected components to increase). NodeNotFound – If root is not in the graph G.

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 _. 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 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.

References