Foundations — DFS applications — cycle detection (directed and undirected)

Before you can trust the parent note's colored-node algorithm, you need to own every word it throws at you: graph, node, edge, directed vs undirected, adjacency list, DFS, recursion stack, parent, the White/Gray/Black colors, and the notation $O(V+E)$. We build them one at a time, each on the picture of the one before it.

1. What is a graph? (dots and connections)

Look at the figure below. The five circles are vertices; the segments between them are edges. That is the entire object — a graph is nothing more than "some things, and which pairs of them are connected."

Why the topic needs it: cycle detection is a question about a graph ("does this network contain a loop?"). You cannot ask it without first having dots and connections to ask about.

We write $V$ for the number of vertices and $E$ for the number of edges. These two letters are the only sizes that matter for speed later, so meet them now.

2. Directed vs undirected (one-way vs two-way doors)

This is the single most important fork in the whole topic, so we give it a picture.

Why the topic needs it: the parent note has two different rules for cycles precisely because these two kinds of edge behave differently. In the undirected world the edge $u-v$ can be walked back the way you came; in the directed world $u\to v$ does not let you return unless a separate arrow $v\to u$ also exists. Hold onto that — it is the reason the "parent-exception" trick works for one and breaks the other.

3. Path and cycle (a route, and a route that bites its own tail)

The smallest simple undirected cycle is a triangle (3 vertices: $A-B-C-A$). The smallest directed cycle is just two arrows that point back at each other ($A\to B\to A$) — or even a single self-loop $A\to A$. That size difference will matter, and it comes straight from rule 2: with an undirected edge $A-B$ you could walk $A\to B\to A$ over the same line, but that reuses the edge, so it is not a cycle; directed edges are separate arrows, so $A\to B\to A$ uses two different edges and is a cycle.

Why the topic needs it: "detect a cycle" is literally the goal. You must know exactly what counts (closes a loop, no edge reused) and what does not.

4. Adjacency list (how the computer stores the picture)

A drawing is for humans. The computer needs the same information as text.

Why the topic needs it: the parent's code writes for v in adj[u]. That loop is "look at every neighbour of $u$." If you did not know adjacency lists, that line would be nonsense.

5. Depth-First Search (the string-in-a-maze walk)

Picture unrolling a ball of string as you walk a maze (this is the parent note's Feynman image). You always push forward into new rooms; when a corridor dead-ends you reel the string back to the last junction and try another corridor.

Why DFS and not some other search? Because a cycle is about returning to where you already are on the current path. DFS is the one strategy that keeps a single unbroken "current path" from your start to your deepest point — so it can notice the instant an edge points back onto that path. A breadth-first "explore everything one ring at a time" search does not maintain that single live chain, so it is the wrong tool for this question. (For a full definition see Depth-First Search.)

6. Recursion and the recursion stack (the string, made literal)

DFS is naturally written as a function that calls itself: dfs(u) calls dfs(v) for a neighbour $v, which calls dfs(w)`, and so on.

The recursion stack is the string on the maze floor: the vertices currently on the stack are precisely the unbroken chain from your start down to where you stand right now.

Why the topic needs it: the whole directed rule is "did we hit a vertex that is still on the stack?" Without understanding the stack, "Gray = on the stack" (next section) is a meaningless phrase.

7. The three colors — White, Gray, Black

Now the colors are easy, because each one just names a stage of the DFS walk you already understand.

Map each color to section 6: White = string never reached here; Gray = string lies here right now; Black = string was here but is already reeled up. Reaching a Gray vertex means an edge points back onto the string still under your feet → a loop closed → cycle. Reaching a Black vertex is harmless — you finished that area on another branch.

Why the topic needs it: these three colors are the directed algorithm's entire memory. (The undirected version simplifies to a two-state visited flag plus a parent, because its symmetric edges let a cheaper test work.)

8. Parent (the door you just came through)

Because an undirected edge is stored both ways (section 4), when you stand at $v$ you will see the edge back to your parent $u$. That is not a new route — it is the exact door you just walked through. The undirected algorithm ignores it with the test v != parent.

Why the topic needs it: the parent-exception is the one line that separates a false alarm from a real undirected cycle.

9. The notation $O(V+E)$

Why this exact size? DFS touches each vertex once (the color/visited guard stops it re-entering) and scans each adjacency-list entry once (each edge looked at a constant number of times). Sum those two amounts of work: $V$ (vertices) $+E$ (edges). That is the whole cost, so the label is $O(V+E)$.

How these foundations feed the topic

Equipment checklist

Read the parent topic (Hinglish version) and the main note only after you can answer every line below.

Connections

• Depth-First Search — the traversal engine every rule here rests on.
• Back Edges and Edge Classification — names the exact edge (back edge) that a Gray hit represents.
• Union-Find (DSU) — a non-DFS way to detect undirected cycles.
• Topological Sort — possible iff a directed graph has no cycle.
• Strongly Connected Components — deeper DFS machinery built on the same colors and finish order.
• Bipartite Checking — another DFS coloring application.