Skip to main content
`Ctrl`+`K`

# has_bridges

has_bridges(G, root=None)

  Decide whether a graph has any bridges.

  A bridge in a graph is an edge whose removal causes the number of connected components of the graph to increase.

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

  Returns:
    bool

      Whether the graph (or the connected component containing `root`) has any bridges.

  Raises:
    NodeNotFound

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

    NetworkXNotImplemented

      If `G` is a directed graph.

  Notes

  This implementation uses the `networkx.bridges()` function, so it shares its worst-case time complexity, \(O(m + n)\), ignoring polylogarithmic factors, where \(n\) is the number of nodes in the graph and \(m\) is the number of edges.

  Examples

  The barbell graph with parameter zero has a single bridge:

      >>> G = nx.barbell_graph(10, 0)
      >>> nx.has_bridges(G)
      True

  On the other hand, the cycle graph has no bridges:

      >>> G = nx.cycle_graph(5)
      >>> nx.has_bridges(G)
      False