Cyclic Graphs — Graph Theory

Overview

What this concept solves

A cyclic graph is one you can walk in a circle: start at some vertex, follow edges, and arrive back where you began without retracing a step. That closed walk is a cycle. A graph with even one such loop is cyclic; a graph with none is acyclic (and a connected acyclic graph is exactly a tree). The whole topic is really one question — is there a loop? — and the interesting part is how you answer it without eyeballing the picture.

The answer is a depth-first search, and it hinges on a single idea: the DFS stack. As DFS dives into the graph it keeps a stack of the vertices on the current path — the chain of "I'm still busy exploring this one" nodes between the root and where you are now. A vertex is on the stack while DFS is working inside its subtree, and only comes off when DFS has finished everything below it. A cycle exists exactly when you follow an edge and land on a vertex that is still on the stack — that edge is a back edge, and it closes a loop with the path already on the stack.

One subtlety makes the undirected case its own thing: the edge straight back to your parent doesn't count. Every undirected edge can be walked both ways, so from a child you'll always see the edge back to the vertex you just came from — but that's not a loop, it's the same edge. So the rule is sharpened: a cycle is a back edge to an on-stack vertex that is not your parent. Get that one exception right and DFS detects cycles in O(V + E), the same cost as visiting the graph once.

Mechanics

How it works

Three colours, one stack

White (unseen) — DFS hasn't reached this vertex yet.
On stack — DFS has entered this vertex but hasn't finished it; it sits on the current path. These are the vertices a back edge can hit.
Done — DFS has explored everything reachable below this vertex and popped it off the stack. An edge to a done vertex is harmless: it left the stack, so it can't close a loop on the current path.
The DFS stack is just the on-stack vertices in order, root at the bottom, the vertex you're currently inside at the top.

The detection rule

Run DFS from any unvisited vertex (repeat for each component so disconnected pieces are covered).
On entering a vertex, push it onto the stack and mark it on stack.
For each neighbour: if it's the parent you just came from, skip it — that's the same undirected edge, not a loop.
If the neighbour is white, recurse into it (it goes on the stack on top of you).
If the neighbour is on stack (and not the parent), you've found a back edge — a cycle. The loop is the stack slice from that neighbour up to the current vertex, plus the back edge.
When a vertex's neighbours are exhausted, pop it (mark done). If DFS finishes with no back edge ever found, the graph is acyclic.

Why "on the stack", not just "visited"

A common bug is to flag a cycle whenever you reach an already-visited vertex. That's wrong: a done vertex was visited but has already left the stack, so reaching it just means two paths met — no loop on the current path. The cycle test is specifically "still on the stack." In CLRS terms the three colours are white / gray / black, and a cycle is a gray edge (an edge to a gray, i.e. on-stack, vertex).

The edge-count shortcut

For a connected undirected graph you don't even need DFS to know whether a cycle exists: a tree on n vertices has exactly n − 1 edges, so any connected graph with n or more edges must contain a cycle. With 6 vertices, 5 edges can be acyclic (a tree) but 6 edges cannot. DFS earns its keep when you want to find the loop, handle multiple components, or detect cycles in a directed graph where the edge count alone won't tell you.

Interactive prototype

Run it. Break it. Tune it.

Sandboxed simulation embedded right in the page. No setup, no install.

simulation › Cyclic Graphs

About this simulation

A six-vertex undirected graph across four tabs, all driven by a depth-first search. Find the cycle runs DFS on a graph that loops and stops the instant an edge reaches a vertex still on the DFS stack — a back edge — then paints the loop red; The acyclic case runs the same DFS on a tree and shows that no back edge ever appears; Break the cycle removes one edge of the loop and re-runs to prove a single cut makes the graph acyclic. Free play lets you click two vertices to toggle an edge, drag vertices, and hit Detect cycle to run DFS on your own graph — the on stack and result stats update live.

Hands-on

Try these on your own

Open the prototype above, run each experiment, predict the answer, then verify.

try 01

Find the cycle

On Find the cycle, press Play. DFS dives from A, pushing each vertex onto the stack shown in the side panel (the top is marked). Watch it walk A → B → E → D and then test the edge D–A: A is still on the stack, so this is a back edge and the loop snaps red. The narration names the cycle and the result stat flips to Cyclic. Use Step / Back to inspect the exact moment the back edge is found.

try 02

The acyclic case

Switch to The acyclic case — same DFS, but the preset is a tree (5 edges, 6 vertices). Play it through and watch the stack grow and shrink as DFS dives and backtracks. Every edge it tests either leads to a white vertex (go deeper) or straight back to the parent (ignored). No edge ever reaches a non-parent vertex on the stack, so no back edge is found and the result stays Acyclic.

try 03

Break the cycle

Break the cycle starts from the looping graph and highlights the cycle in red. Then it removes one edge of that loop and re-runs DFS — and now the search completes with the stack emptying cleanly and no back edge. The takeaway is on screen: a cycle needs every one of its edges, so cutting any single one of them makes the whole graph acyclic. Compare the before/after panel.

try 04

Free play — build your own loops

Open Free play. Click any two vertices to toggle an edge; drag vertices to rearrange. Build a tree first, then add one edge between two vertices that are already connected by a path — that single edge closes a loop. Hit Detect cycle to run DFS on your graph and watch the on stack counter rise and fall and the result report Cyclic or Acyclic. Clear edges to start from scratch.

In practice

When to use it — and what you give up

Care about cycles when

You're checking for deadlock or circular dependency — a cycle in a resource-wait graph or an import graph is a bug you must find and break.
You need a tree or spanning structure — adding an edge is only safe if it doesn't close a loop; that's exactly the test Kruskal's and union-find use to build a minimum spanning tree.
You're validating a schedule or build order — a topological order exists only when the dependency graph is acyclic, so cycle detection is the precondition for ordering anything.
You want graph structure — girth (shortest cycle), feedback edge sets, and "how many independent loops" (the cyclomatic number m − n + c) all start from finding cycles.

Reach for something other than plain DFS cycle detection when

The graph is directed — the on-stack rule still works, but you drop the parent exception (a 2-cycle A→B→A is a real cycle), and "done" vs "on stack" becomes the whole story.
You only need to maintain acyclicity as edges arrive — incremental union-find answers "would this edge make a cycle?" in near-constant time, faster than re-running DFS each time.
You want the shortest cycle (girth) in an unweighted graph — a BFS-based approach is usually cleaner than instrumenting DFS.

Pros

Linear time — one DFS pass, O(V + E), finds a cycle or proves there's none.
Constructive — the moment it fires, the DFS stack hands you the actual cycle, not just a yes/no.
Handles disconnected graphs — restart DFS from each unvisited vertex and every component is covered.
One idea ports everywhere — the "edge to an on-stack vertex" rule extends to directed graphs (topological sort, deadlock detection) with only the parent rule dropped.

Cons

The parent exception is a footgun — forget it on undirected graphs and you'll report a cycle for every single edge.
Recursion depth — a naive recursive DFS can blow the call stack on a long path; deep graphs need an explicit stack.
*Finds a cycle, not the best one* — plain DFS gives you whichever loop it hits first, not the shortest (girth) or any particular one.
Re-runs from scratch — if edges are arriving one at a time, re-running DFS per edge is wasteful; union-find is the incremental tool.

Reference

Code & further reading

A minimal reference implementation and pointers worth bookmarking.

cyclic-graph.ts

// Undirected cycle detection by DFS.
// A cycle exists iff DFS finds an edge to a vertex that is
// STILL ON THE STACK (i.e. an ancestor) and isn't the parent.
function hasCycle(adj: Map<string, string[]>): boolean {
  const onStack = new Set<string>();   // vertices on the current DFS path
  const done = new Set<string>();      // fully explored vertices

  function dfs(u: string, parent: string | null): boolean {
    onStack.add(u);                    // push: u is on the path now
    for (const v of adj.get(u) ?? []) {
      if (v === parent) continue;      // the edge back to parent is NOT a cycle
      if (onStack.has(v)) return true; // back edge -> v is an ancestor -> cycle!
      if (!done.has(v) && dfs(v, u)) return true;
    }
    onStack.delete(u);                 // pop: u and its subtree are finished
    done.add(u);
    return false;
  }

  // Restart for every component so disconnected pieces are covered.
  for (const start of adj.keys()) {
    if (!done.has(start) && dfs(start, null)) return true;
  }
  return false;
}

// To return the cycle itself, keep an explicit array stack and, on the
// back edge u->v, slice it from the first occurrence of v up to u.

References & further reading

6 sources

Knowledge check

Did the prototype land?

Quick questions, answers revealed on submit. No scoring saved.

question 01 / 03

During a DFS on an undirected graph, you follow an edge and arrive at a vertex. In which case have you found a cycle?

question 02 / 03

A connected undirected graph has 6 vertices. What is the largest number of edges it can have while still being acyclic?

question 03 / 03

You've found a cycle in a graph and want to make the graph acyclic with the fewest edge removals. How many edges of that single cycle must you remove?

0/3 answered