Connectivity & Cycle Detection

Graph Theory

Chapter 4 · Connectivity & Cycle Detection

Chapter 3 built two ways to explore a graph. This chapter puts them to work answering two genuinely practical questions: is everything actually reachable from everything else, and does this graph loop back on itself somewhere?

Connected Components

A connected component is a maximal group of vertices all reachable from each other. Finding every component in a graph is just Chapter 3's own traversal, repeated: run DFS (or BFS) from any unvisited vertex, mark everything it reaches, then repeat from the next still-unvisited vertex.

A graph with three separate "islands": {A,B,C} (a triangle), {D,E}, {F,G} — no edges connecting the groups.

Verified directly

Running the repeated-traversal method produces exactly three components: ['A','B','C'], ['D','E'], ['F','G'] — each vertex accounted for exactly once, matching the graph's own visibly disconnected structure.

Cycle Detection in Undirected Graphs

During a DFS, encountering an edge to an already-visited vertex normally signals a cycle — except the edge leading straight back to the vertex you just came from, which is always there in an undirected graph and doesn't count.

The parent-tracking rule

While doing DFS, track the vertex each call arrived from (its "parent"). If DFS reaches an already-visited vertex that isn't the current parent, a genuine cycle exists.

Testing two small graphs directly:

Graph	Structure	Has a cycle?
Triangle	A-B, B-C, C-A	True
Path/tree	A-B, B-C, C-D	False

A useful fact, forward-referencing Chapter 9

An undirected tree with V vertices always has exactly V−1 edges and contains no cycles — the second row above (4 vertices, 3 edges) is exactly a tree, Chapter 9's own subject.

Cycle Detection in Directed Graphs — A Genuinely Different Problem

The parent-tracking trick doesn't work for directed graphs — an edge can point to an already-visited vertex without forming a cycle at all, if that vertex was finished processing along a completely different branch. The real signal is a back edge: an edge to a vertex still currently on the DFS call stack, not just visited at some point in the past.

The three-color DFS method

Mark each vertex white (unvisited), gray (currently being explored — on the active DFS path), or black (fully finished). An edge to a gray vertex is a genuine back edge — a cycle. An edge to a black vertex is safe.

Real Relevance: Detecting Circular Dependencies

Modeling packages as vertices and "depends on" as directed edges — exactly Chapter 1's own dependency-resolution connection:

Dependency graph	Edges	Has a cycle?
Circular	A→B, B→C, C→A	True — A depends on B depends on C depends on A, impossible to install
Valid	A→B, A→C, B→C	False — a valid order exists: C, B, A

This is exactly what a real package manager runs before attempting any installation — a directed cycle means the dependency requirements are genuinely impossible to satisfy, not just difficult.

Connectivity & Cycle Detection in Code

def find_components(adj):
    visited, components = set(), []
    for v in adj:
        if v not in visited:
            comp, stack = [], [v]
            while stack:
                u = stack.pop()
                if u in visited: continue
                visited.add(u); comp.append(u)
                stack.extend(w for w in adj[u] if w not in visited)
            components.append(comp)
    return components

def has_cycle_directed(adj):
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {v: WHITE for v in adj}
    def dfs(u):
        color[u] = GRAY
        for v in adj[u]:
            if color[v] == GRAY:
                return True
            if color[v] == WHITE and dfs(v):
                return True
        color[u] = BLACK
        return False
    return any(dfs(v) for v in adj if color[v] == WHITE)

cyclic_deps = {'A': ['B'], 'B': ['C'], 'C': ['A']}
print(has_cycle_directed(cyclic_deps))  # True

Hands-On Exercises

Exercise 1

Find all connected components of the undirected graph with edges P-Q, Q-R, S-T, U (U has no edges at all — an isolated vertex).

📄 View solution

Exercise 2

Using this chapter's own parent-tracking method, determine whether the undirected graph with edges A-B, B-C, C-D, D-B contains a cycle. Show which edge creates it, if one exists.

📄 View solution

Exercise 3

A package dependency graph has: app → libA, app → libB, libA → libC, libB → libC, libC → libA. Using this chapter's own three-color method, determine whether this dependency graph is installable, and if not, identify the specific cycle.

📄 View solution

Chapter 4 Quick Reference

Connected components: repeated DFS/BFS from every unvisited vertex — each run finds one full component
Undirected cycle detection: a DFS edge to an already-visited, non-parent vertex signals a cycle
Directed cycle detection: the three-color method — an edge to a currently-gray (on-the-active-path) vertex is a genuine back edge/cycle
A tree with V vertices has exactly V−1 edges and no cycles (Chapter 9 forward reference)
Directed cycle detection is exactly how real package managers detect impossible circular dependencies before attempting installation
Next chapter: Topological sorting