Edit page

Bridges

In graph theory, a bridge, isthmus, cut-edge, or cut arc is an edge of a graph whose deletion increases its number of connected components. Equivalently, an edge is a bridge if and only if it is not contained in any cycle. For a connected graph, a bridge can uniquely determine a cut. A graph is said to be bridgeless or isthmus-free if it contains no bridges.

Another meaning of "bridge" appears in the term bridge of a subgraph. If H is a subgraph of G, a bridge of H in G is a maximal subgraph of G that is not contained in H and is not separated by H. [Source: Wikipedia]

Bridges in graph

A graph with 16 vertices and 6 bridges (highlighted in red).

Complexity

NameBest timeComments
Bridgesv + eBased on the algorithm used.

* Where v = number of vertices; e = number of edges

References

  • Geeksforgeeks
  • Wikipedia
  • YouTube
  • Hackerearth
  • cp-algorithms
  • Tutorialspoint