Skip to content

Connectivity and Cycles

Connectivity means different things in directed and undirected graphs.

Undirected components

Start BFS or DFS from every unvisited vertex. Each traversal discovers exactly one connected component. Total time is Θ(V + E) and auxiliary space is Θ(V).

An undirected DFS detects a cycle when it encounters a visited neighbor other than the edge back to the current vertex's parent. Parallel edges require an edge-identity-aware implementation; comparing only parent vertices can miss a two-edge cycle in a multigraph.

Directed cycles

Use three states:

  • white: undiscovered;
  • gray: active in the current DFS path;
  • black: completely processed.

An edge to a gray vertex is a back edge and proves a directed cycle. An edge to a black vertex does not. Kahn's topological algorithm offers another test: if it cannot emit all vertices, a cycle exists.

Incremental connectivity

Disjoint-set union answers connectivity efficiently while undirected edges are only added. It does not support arbitrary deletions or reconstruct an actual path. Dynamic connectivity with deletions requires stronger techniques or offline processing.

Bipartiteness

Color each component with two colors during BFS/DFS. Every edge must join opposite colors. A conflict proves an odd cycle; conversely, an undirected graph without an odd cycle is bipartite.

Exercises

  1. Extend traversal to return each component's vertices.
  2. Reconstruct an odd cycle after a coloring conflict.
  3. Contrast weak and strong connectivity in directed graphs.