Intuition The ONE core ideaDFS is just this: walk into a graph as deep as one path goes, drop a marker in every room you enter, and step back to the last fork when you dead-end. Everything else on the parent page — the visited array, the stack, the O ( V + E )
Before you can read the parent DFS note, you must own every symbol it uses without apology. This page builds them from nothing , in an order where each idea rests only on the ones above it. Nothing here assumes you have seen a graph before line one.
Start with a picture, not a definition.
Look at the figure. The circles are rooms — in graph language a vertex (plural: vertices). The lines connecting them are tunnels — an edge . That is the whole object.
A graph is a set of vertices (dots, drawn as circles) joined by edges (lines). Formally we write G = ( V , E ) V E
Intuition Why DFS needs thisDFS is a way to walk a graph . If you don't have the picture of dots-and-lines fixed in your head, "traversal", "neighbor", and "adjacency list" are meaningless. Every later symbol is built on this drawing.
The letter V
V E
V set of vertices and , when written in a formula like O ( V + E ) number of vertices (how many circles).E set of edges and the number of edges (how many lines).
So "v ∈ V v V = 4
In the figure above there are V = 4 E = 4
V V whole collection or the count . A single vertex gets a lowercase letter like u v 0 , 1 , 2 ∑ v ∈ V v V
An edge can be a two-way tunnel or a one-way street. This choice changes the complexity formula, so it must be crisp.
Definition Undirected vs directed
Undirected edge (left, plain line): you can walk A → B and B → A Directed edge (right, arrow): A → B second arrow B → A
Intuition Why the topic caresThe parent's Handshake Lemma line — ∑ deg ( v ) = 2 E ∑ outdeg ( v ) = E entirely about this distinction. An undirected line is "seen" from both its endpoints (counted twice); a directed arrow leaves from exactly one. Hold that thought for §6.
Now we need the vocabulary DFS actually loops over.
Definition Neighbor and degree
A neighbor of vertex u u
The degree of u deg ( u ) how many neighbors u
For directed graphs, outdeg ( u ) leaving u
In the figure, vertex 0 1 2 deg ( 0 ) = 2 adjacency list : a table where row u u
Definition Adjacency listAn adjacency list is the data layout graph[u] = [list of u's neighbors]. The parent's 0:[1,2] 1:[3] 2:[] 3:[] is an adjacency list: vertex 0 points to 1 and 2, vertex 2 points to nobody.
adjacency list and not a grid?
DFS's inner line for v in graph[u] walks exactly this list. The reason the whole algorithm is O ( V + E ) O ( V 2 ) graph[u] costs only deg ( u ) real edges, not empty cells of a V × V is the complexity.
DFS's whole visited machinery exists to survive one thing: cycles. Define it.
Definition Path and cycle
A path is a sequence of vertices where each consecutive pair is joined by an edge: 0 → 1 → 3
A cycle is a path that returns to where it started: 0 → 1 → 2 → 0 tree is a graph with no cycles.
Intuition Why cycles force a visited arrayFollow the triangle in the figure with your finger: 0 → 1 → 2 → 0 → 1 → … must mark rooms. In a tree (no cycle) there's only one way to reach each node, so a plain traversal never revisits and needs no marker. Cycle = the reason visited exists.
The parent writes O ( V + E ) ∑ v deg ( v ) = 2 E ( 2 n )
O ( ⋅ ) O ( f ) no faster than f O ( V + E ) plus number of edges)." We add because DFS does one chunk of work per vertex and a separate chunk per edge.
Definition The summation symbol∑ ∑ v ∈ V deg ( v ) v V deg ( v ) for-loop that adds .
∑ v deg ( v ) = 2 E two endpoints. When you total up all the degrees, each edge gets counted once from each end — so the grand total is exactly 2 E = 2 × Handshake Lemma .
Definition The choose symbol( 2 n ) ( 2 n ) = 2 n ( n − 1 ) unordered pairs you can pick from n complete graph every pair is joined, so E = ( 2 n ) O ( n 2 )
DFS backtracks "for free." The reason is one data structure.
A stack is a pile where the last thing you put on is the first you take off — L ast I n, F irst O ut. push adds to the top, pop removes from the top. See Stack data structure .
Intuition Why a stack = backtrackingWhen you dive 0 → 1 → 3 most recent fork you must return to is 1, then 0 — exactly reverse order of how you entered. That is LIFO. The call stack of recursion is a stack you never had to build; that's why recursive DFS is so short. See Recursion and the Call Stack .
Degree and Handshake Lemma
DFS complexity O of V plus E
Read it top-down: the raw picture (vertices/edges) feeds every branch; cycles justify the visited array; the stack + recursion give backtracking; degree + Handshake give the cost — and all of it converges on DFS.
Cover the right side and answer each before you open the parent note.
A graph G = ( V , E ) Vertices (dots/circles) and edges (lines joining them).
What does V O ( V + E ) The number of vertices (its other meaning is the whole set of vertices).
Difference between an undirected and a directed edge? Undirected = travel both ways on one line; directed = one-way, shown by an arrow.
What is deg ( u ) The number of edges touching u u
What does graph[u] (an adjacency list row) store? The list of u
What is a cycle, and why does DFS fear it? A path returning to its start (0 → 1 → 2 → 0
State the Handshake Lemma in one line. Summing all vertex degrees counts every undirected edge twice, so ∑ v deg ( v ) = 2 E
What does ( 2 n ) 2 n ( n − 1 ) n
What does LIFO mean and why does DFS use it? Last In First Out; it makes you return to the most-recent fork first, which is backtracking.
Why is recursive DFS "free" backtracking? The program's call stack is already a LIFO stack, so returns happen automatically.
Parent: back to the DFS topic .
Stack data structure — the LIFO engine.Recursion and the Call Stack — free backtracking.Handshake Lemma — why ∑ deg = 2 E Cycle Detection — cycles are why visited exists.BFS — Breadth-First Search — same foundations, a queue instead of a stack.Connected Components — repeated DFS launches over the same graph.Topological Sort — needs directed edges from §3. 
