Depth-First Search (DFS)
Explore a graph by going as deep as possible first, while recording parent relationships, pre/post numbering, and edge types.
DFS often feels simple at first, but it becomes harder when learners must track discovery order, backtracking, parent pointers, timestamps, and edge classification at the same time.
The key teaching flow is: start at a root → go as deep as possible → backtrack when stuck → assign pre/post numbers → classify non-tree edges using structure and time.
Quick Facts
DFS keeps moving deeper into the graph before returning to explore alternate branches.
A pre number is assigned when a vertex is first discovered.
A post number is assigned when DFS finishes exploring a vertex and backtracks.
The edges used to discover new vertices form the DFS tree.
Key Idea
DFS is not just about visiting vertices. It is also about recording when a vertex begins and when it finishes.
The most important mental model is: DFS has two phases for every vertex — discovery and completion. That is why both pre and post numbers matter.
Visualization
This visualization starts at a, keeps the adjacency list visible, records parent relationships as the DFS tree grows, then slows the backtracking phase so you can see exactly when post numbers are assigned. After traversal, the animation classifies non-tree edges as back, forward, or cross.
Watch actively: pause before each return step and predict which vertex gets the next post number.
How It Works
Begin at a chosen start vertex, here a.
Visit an unvisited neighbor, record its parent, and continue as deeply as possible.
If a vertex has no unvisited neighbors, DFS returns to its parent.
Assign post numbers during the return steps and complete the traversal tree.
Pre and Post Numbering
A pre number is assigned the moment DFS first arrives at a vertex. It marks discovery time.
A post number is assigned only after DFS finishes exploring all descendants of that vertex. It marks completion time.
Learners often follow discovery easily, but post numbers require understanding the backtracking process.
Together, pre and post numbers help explain edge classification and ancestor-descendant relationships.
Tree Edges and Non-Tree Edges
These are the edges used to discover new vertices during DFS. Together they form the DFS tree.
These connect already discovered vertices and are analyzed after the DFS structure is clear.
It is easier to understand edge classification after the traversal tree and timestamps are complete.
The DFS tree shows how the graph was explored, not every edge that exists in the graph.
Back, Forward, and Cross Edges
Points from a descendant back to an ancestor in the DFS tree.
Points from an ancestor to a descendant, but is not itself a tree edge.
Connects vertices that are in different completed branches, where neither is an ancestor of the other.
Pre/post intervals make these edge types easier to justify instead of just memorizing names.
Why It Matters
DFS is one of the most important graph algorithms and supports many later topics.
DFS helps learners understand how recursive exploration and return steps work together.
It teaches that traversal creates structure, not just a visitation order.
Pre/post numbering makes graph relationships more precise and more explainable.
Pseudocode
This pseudocode shows the core DFS process with pre and post numbering:
time = 1
DFS(G, start):
for each vertex v in G:
visited[v] = false
parent[v] = null
EXPLORE(start)
EXPLORE(v):
visited[v] = true
pre[v] = time
time = time + 1
for each neighbor u of v:
if visited[u] == false:
parent[u] = v
EXPLORE(u)
post[v] = time
time = time + 1The important detail is that pre is assigned on discovery, while post is assigned only after returning from deeper calls.
Common Confusions
Not exactly. DFS follows one branch as deep as possible before returning to explore alternatives.
No. Post numbers are assigned only when DFS finishes that vertex and backtracks.
No. Only discovery edges become tree edges. Other edges must be classified separately.
They are different. Forward edges go to descendants; cross edges connect separate completed branches.
Outcome
After this lesson, learners should be able to trace DFS traversal order, record parents, explain why pre and post numbers differ, and classify non-tree edges as back, forward, or cross using structure and timing.