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 graph G.

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

1

https://en.wikipedia.org/wiki/Bridge_%28graph_theory%29#Bridge-Finding_with_Chain_Decompositions

Examples

The barbell graph with parameter zero has a single bridge:

>>> G = nx.barbell_graph(10, 0)
>>> list(nx.bridges(G))
[(9, 10)]