Skip to main content
`Ctrl`+`K`

# bridges

bridges(G, root=None)

  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.

  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

      If `root` is not in the graph `G`.

    NetworkXNotImplemented

      If `G` is a directed graph.

  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.

  The algorithm described in [1] 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.

  References

  [1] (1,2)

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