Depth-First Search (DFS) Interactive Tool

Interactive depth-first search (DFS) tool. Paste an adjacency list, choose directed or undirected, select a start node, and see visit order, discovery/finish times, and DFS tree edges.

Graph Input

Format: Node: neighbor1 neighbor2. Blank lines are ignored.

How to Use This Tool

Model your graph as an adjacency list, pick whether the edges are directed, choose a starting node (optional), and click Run DFS. This hero view summarizes the visit order, metadata, and a tabular view of discovery/finish timestamps.

1. Graph input

Write one node per line, use a colon after the node, then space-separated neighbors. Blank lines are ignored and neighbors are added automatically for undirected graphs.

A: B C
B: D
C: D E
D: F
E:
F:
  • Use simple labels (A, B, C or 1, 2, 3) to keep the visit order readable.
  • The start node is optional; if omitted, the algorithm visits nodes in alphabetical order after the current component is exhausted.
  • Check the Directed graph box when edge direction matters; leave it unchecked for undirected traversal.

2. DFS results

The hero result box shows the full visit order. KPI rows highlight node/edge counts, how many components were explored, and which node you seeded first.

The traversal table lists discovery and finish timestamps per node, and the edge inspection pane (below) classifies each edge as tree/back/forward/cross for directed graphs or tree/back for undirected graphs.

Methodology

DFS explores a graph deeply by visiting unvisited neighbors until a dead end, then backtracking. This implementation emulates the CLRS-style recursive DFS, tracking discovery/finish timestamps, parents, and edge classification. The pseudo-code lives under the Formulas section.

  • Time complexity is O(V + E) with an adjacency list, which is optimal for a full traversal.
  • In directed graphs we report tree, back, forward, and cross edges. In undirected graphs every non-tree edge is treated as a back edge to avoid duplicates.
  • The component counter increments every time DFS starts from a white node, so you can see how many disconnected pieces the graph has.
Edge classification note: Tree edges lead to newly discovered nodes, back edges revisit ancestors, forward edges point ahead in discovery order, and cross edges connect nodes on different branches. Undirected graphs only emit tree and back edges to avoid mirrored duplicates.

Tips

Keep node labels concise (A, B, C or 1, 2, 3). The parser ignores blank lines and trims whitespace, so reformatting is quick. If the start node is missing, DFS will still traverse all nodes in alphabetical order.

Related graph tools

FAQs

What is depth-first search (DFS)? DFS explores as far as possible along each branch before backtracking; typical implementations use recursion or an explicit stack.

What is DFS used for? It powers topological sorting, cycle detection, connected components, edge classification, and spanning tree construction.

What is the time complexity of DFS? It runs in O(V + E) time using an adjacency list.

Formulas
DFS pseudocode
DFS(G):
for each vertex u in G.V:
color[u] = WHITE, parent[u] = NIL
time = 0
for each vertex u in G.V:
if color[u] == WHITE:
DFS-Visit(u)
Variables
  • G.V: the set of vertices in graph G.
  • color[u]: tracks traversal state (WHITE, GRAY, BLACK).
  • parent[u]: parent pointer for tree edges.
  • d[u]/f[u]: discovery and finish timestamps.
Citations
Changelog
Version 0.1.0-draft · Last code update: 2026-01-19
  • 0.1.0-draft — 2026-01-19: Initial audit spec draft generated from HTML extraction (review required).
  • Verify formulas match the calculator engine and convert any text-only formulas to LaTeX.
  • Confirm sources are authoritative and relevant to the calculator methodology.
✓ Audit: Complete Verified by Ugo Candido on 2026-01-19 Version 0.1.0-draft
Version 1.5.0