Maggie HTTN
Visual Algorithms • UX/UI Case Study

Depth-First Search (DFS)

Learn DFS as a clear, step-by-step exploration, then understand how DFS reveals non-tree edges and graph structure.

DFS is one of the most important graph algorithms because it is the foundation for many higher-level ideas: detecting cycles, building topological order, identifying strongly connected components, and classifying edges.

This page includes two demos: first, a guided DFS traversal; second, a “Non-tree Edge Analysis” demo showing how DFS produces edge types that explain graph relationships.

Watch Demo

Quick Facts

Core Idea
Go as deep as possible, then backtrack (stack/recursion behavior).
What learners practice
Visited order, backtracking moments, and edge interpretation.
Why it matters
Foundation for cycle detection, topological sort, SCC, and more.
My role
UX/UI teaching flow + animation design for clear graph reasoning.

What the Demos Emphasize

  • Traversal state: which node is active, which nodes are discovered, and when backtracking happens.
  • Tree vs non-tree edges: edges chosen by DFS become the DFS tree; other edges reveal structure.
  • Readable reasoning: each step is paired with a short explanation (“why this edge next?”).

Demo 1 — DFS Traversal

What to watch for

Notice how DFS commits to one path “deep” until no unvisited neighbor remains, then backtracks to the most recent branching point. This behavior is what makes DFS powerful for discovering structure in graphs.

DFS Rules (Beginner-Friendly)

  1. Start at a node and mark it visited.
  2. Choose an unvisited neighbor and move to it.
  3. Repeat until the current node has no unvisited neighbors.
  4. Backtrack to the previous node (stack/recursion) and continue exploring.
  5. Stop when all reachable nodes are visited (or restart from another node if needed).

Demo 2 — Non-tree Edge Analysis

What this explains

DFS creates a DFS tree from the edges it uses to discover new nodes. All other edges are non-tree edges. Classifying them helps explain cycles, ancestry, and directionality.

Non-tree Edges: The Rules

Tree Edge
An edge that discovers a new node. These edges form the DFS tree.
Back Edge
An edge from a node to one of its ancestors in the DFS tree. This is the classic signal of a cycle in directed graphs.
Forward Edge (Directed Graphs)
An edge from a node to a descendant in the DFS tree that is not a tree edge.
Cross Edge (Directed Graphs)
An edge between nodes that are not in an ancestor/descendant relationship (often between different branches).
Note: In undirected graphs, non-tree edges typically appear as back edges (because every undirected edge is seen from both directions).

Outcome

After these two demos, learners can follow DFS traversal with confidence and explain what non-tree edges mean. This prepares them for advanced topics like cycle detection, topological sorting, and strongly connected components.