Maggie HTTN
Case Study • Graph Algorithms

Depth-First Search (DFS) with Tree Types

Designing a structured learning experience for traversal order, pre/post numbering, and non-tree edge classification.

Depth-first search often feels simple at first, but learners quickly become overwhelmed when they must track recursion, traversal order, parent relationships, pre/post numbering, and edge classification at the same time.

This module separates those layers into visible, synchronized representations so learners can follow how DFS builds a traversal tree, assigns timestamps, and classifies non-tree edges as back, forward, or cross.

Watch Demo

Project Scope

Curricular Target
Data Structures, Algorithms, and introductory graph theory coursework.
Delivery Model
Hybrid instructional module; adaptable for synchronous lecture, guided practice, or asynchronous review.
Learner Profile
Students learning graph traversal for the first time and moving from path-following intuition to formal DFS reasoning.
Primary Objective
Enable learners to explain how DFS order, parent relationships, and pre/post timestamps work together to classify edges.

Core Learning Outcomes

  • Trace the DFS traversal order from a chosen start vertex using the adjacency list.
  • Record parent relationships and assign correct pre and post numbers during traversal and backtracking.
  • Distinguish between tree edges and non-tree edges in the resulting traversal.
  • Classify non-tree edges as back, forward, or cross using structural position and timestamp intervals.

Learning Challenge

Learners may be able to follow the path of DFS visually, yet still struggle to explain why a vertex receives a certain post number or why a non-tree edge is classified one way instead of another. Static notes usually show the final answers but not the reasoning process that produces them.

Design Strategy

Adjacency-List First
The module keeps the graph’s adjacency list visible so each traversal decision can be traced back to the given input order.
Synchronized Views
The graph, vertex table, and non-tree edge table update together so learners can connect movement in the graph with changes in timestamps and classification.
Backtracking Made Visible
Post numbers are assigned during return steps, not just discovery, so learners can see why DFS is defined by both descent and backtracking.
Edge-Type Reasoning Through Time
Non-tree edges are analyzed after traversal using pre/post intervals and ancestor-descendant relationships, helping learners move beyond memorized labels.

Solution Design

The learning sequence is structured to make DFS feel less like a disappearing recursive process and more like a set of visible state changes.

1. Traversal Begins From a Fixed Root

The lesson starts at vertex a, making the initial decision explicit and giving learners a stable reference point for the rest of the traversal.

2. Parent and Discovery Order Are Recorded Together

Each newly visited vertex is paired with its parent and discovery number, helping learners connect the traversal path to the emerging DFS tree.

3. Post Numbers Are Assigned During Return

Instead of showing only final timestamps, the module slows the backtracking phase so learners can see when a vertex becomes complete and why post numbers appear in reverse completion order.

4. Tree Edges and Non-Tree Edges Are Separated

The traversal tree is built first, then non-tree edges are analyzed one by one. This prevents learners from trying to classify every edge before the DFS structure is stable.

5. Edge Classification Uses Structure and Time

Back, forward, and cross edges are interpreted using both graph position and pre/post intervals, helping learners understand why timestamps matter beyond simple numbering.

Design Refinement:

Early confusion centered on two moments: assigning post numbers during backtracking and distinguishing forward edges from cross edges.

To address this, the animation slows the return steps, keeps parent and timestamp tables visible, and analyzes non-tree edges after traversal so classification happens with complete structural context.

Interactive Implementation

The animation shows DFS as a coordinated sequence of graph movement, parent recording, timestamp assignment, and edge-type analysis.

Watch actively: pause, predict the next visited vertex or next post number, then decide how the next non-tree edge should be classified.

The implementation uses the adjacency list, traversal table, and non-tree edge table together so learners can follow DFS as both a process and a classification system.

Guided Worksheet (Pause & Predict)

These worksheet prompts follow the same sequence shown in the animation. Pause at each major change, predict what will happen next, then continue to confirm or revise your reasoning.

Part 1 — Read the Graph and Adjacency List
  • Which vertex is chosen as the DFS start vertex?
  • What are the outgoing neighbors of a in the given adjacency list?
  • Why does DFS need the adjacency list order, not just the picture of the graph?
  • Before traversal begins, which values in the vertex table are still empty?
Part 2 — First Discovery from a
  • What pre number should a receive first?
  • Which neighbor of a is visited next according to the adjacency list?
  • What parent should be recorded for that next vertex?
  • Why is the edge from a to that vertex considered a tree edge?
Part 3 — Following the First Deep Path
  • After visiting b, which vertex is explored next?
  • What pre number does e receive?
  • From e, which vertex is visited next along the DFS path?
  • What path is being formed through the tree edges as DFS goes deeper?
Part 4 — Visiting f and Reaching g
  • What pre number is assigned to f?
  • Which neighbor of f is visited next?
  • Why does g become a tree-edge child of f?
  • At this moment, which vertices are on the active DFS path from the root?
Part 5 — First Backtracking and Post Numbers
  • Why does g receive a post number before f?
  • What post number is assigned to g?
  • What post number is assigned to f after returning from g?
  • What does this tell you about how DFS finishes a subtree?
Part 6 — Continuing from e to h
  • After returning to e, which remaining neighbor is explored next?
  • What pre number is assigned to h?
  • Why is e→h a tree edge even though g has already been visited?
  • What post number does h receive when its exploration ends?
Part 7 — Completing the First Major Branch
  • When e finishes, what post number does it receive?
  • After that, what post number is assigned to b?
  • Why does DFS return all the way back to a before visiting c?
  • What does this reveal about DFS priority: breadth or depth?
Part 8 — Starting the Second Branch from a
  • Which new neighbor of a is visited after the b–e–f–g–h branch is complete?
  • What pre number is assigned to c?
  • Which vertex becomes the child of c in the traversal tree?
  • What pre number is assigned to d?
Part 9 — Completing c and d
  • Why does d receive its post number before c?
  • What post number is assigned to d?
  • What post number is assigned to c?
  • When the entire traversal finishes, what final post number is assigned to a?
Part 10 — Reading the Final Tree Edges
  • Which edges in the graph became tree edges during DFS?
  • Which parent is recorded for b?
  • Which parent is recorded for e?
  • Which parent is recorded for c and d?
  • How does the final tree show the order in which DFS explored the graph?
Part 11 — Non-Tree Edge List
  • Which non-tree edges are listed after the traversal tree is complete?
  • Why are these edges not part of the DFS tree?
  • What information do we now have that allows us to classify them?
  • Why is it easier to classify them after traversal rather than during the first visit?
Part 12 — Classifying f→b
  • Does f→b point from a descendant back to an ancestor, or from an ancestor to a descendant?
  • What do the pre/post intervals of f and b suggest?
  • Why is f→b classified as a back edge?
  • How does this edge relate to the active DFS ancestry path?
Part 13 — Classifying e→g
  • Is g a descendant of e in the DFS tree?
  • Why is e→g not a tree edge even though it goes from ancestor to descendant?
  • What interval relationship between e and g supports the classification?
  • Why is e→g a forward edge?
Part 14 — Classifying h→g
  • Do h and g lie in the same DFS branch, or in separate completed branches under e?
  • Why is neither vertex an ancestor of the other?
  • What does that imply about the classification of h→g?
  • Why is this edge considered a cross edge?
Part 15 — Classifying d→a and d→h
  • Why is d→a classified as a back edge?
  • How do the intervals of d and a show an ancestor-descendant relationship?
  • Why is d→h not back or forward?
  • What makes d→h a cross edge between disjoint completed regions?
Part 16 — Final Reflection
  • Why are pre numbers assigned on first visit, but post numbers assigned only after returning?
  • How does DFS produce both a traversal tree and a timing system?
  • Which non-tree edge type felt hardest to distinguish, and why?
  • What part of the animation most helped you understand the difference between back, forward, and cross edges?

Focus on the relationship between traversal order, parent structure, and time intervals. The goal is to understand why the edge labels are correct, not just memorize their names.

Assessment Strategy

This module evaluates understanding through guided prediction, timestamp reasoning, and edge-type interpretation based on the completed DFS tree.

  • Formative assessment (during learning): Students predict the next visited vertex and explain when a post number should be assigned.
    • Which vertex should DFS visit next from the current position?
    • Why is this vertex chosen based on the adjacency list?
    • Has the current vertex finished, or must DFS go deeper first?
    • When should the next post number be assigned, and to which vertex?
  • Application assessment (parent + timestamp reasoning): Students explain how the DFS tree is built and how timestamps record both descent and return.
    • Which parent is recorded for this newly discovered vertex?
    • What pre number should it receive?
    • What evidence shows that this subtree is now complete?
    • How do the post numbers reflect the order of backtracking?
  • Edge classification assessment: Students use ancestor relationships and pre/post intervals to classify non-tree edges.
    • Does this edge point to an ancestor, a descendant, or a disjoint completed branch?
    • What do the interval relationships tell you about the edge type?
    • Why is this edge not a tree edge?
    • Should this edge be classified as back, forward, or cross?
  • Summative assessment (after learning): A short exit check confirms whether students can explain both the DFS process and its edge classification results.
    • How does DFS assign pre and post numbers?
    • Why does backtracking matter in DFS?
    • How can pre/post numbers help classify non-tree edges?
    • What is the difference between a back edge, a forward edge, and a cross edge in this traversal?

Assessment Activities

  • Prediction prompts before each new discovery and each return step.
  • Parent-pointer and timestamp checks during traversal.
  • Pre/post interval comparisons during non-tree edge analysis.
  • Tree-edge versus non-tree-edge interpretation using the final DFS structure.

Inclusive Design

  • Multiple synchronized representations reduce cognitive search during traversal and classification.
  • Visible pre/post numbering supports learners who need a slower reasoning tempo.
  • Pacing control supports repeated review of descent and backtracking phases.
  • Guided worksheet prompts support different learning preferences.

Instructional Impact

The module helps learners move from following DFS as a path animation to understanding it as a timed structural process that produces both a traversal tree and a meaningful edge classification system.