Depth First Search Calculator

Example	Nodes	Edges	Start	Target	Order	Expected Traversal
Tree graph	A,B,C,D,E,F	A-B, A-C, B-D, B-E, C-F	A	E	Ascending	A → B → D → E → C → F
Directed cycle	1,2,3,4	1->2, 2->3, 3->1, 3->4	1	4	Input	1 → 2 → 3 → 4
Disconnected graph	P,Q,R,S,T	P-Q, Q-R, S-T	P	T	Ascending	P → Q → R → S → T

Formula Used

Depth progression: depth(child) = depth(parent) + 1

Parent path reconstruction: Follow each node’s parent repeatedly until the start node is reached.

Traversal time complexity: T(V,E) = Θ(V + E), because DFS processes each vertex and edge once in an adjacency-list graph.

Auxiliary space complexity: S(V) = Θ(V), due to the visited map, parent map, recursion stack, and supporting arrays.

Cycle logic: A back edge to an active gray node signals a cycle in directed graphs. In undirected graphs, a gray neighbor that is not the parent also signals a cycle.

How to Use This Calculator

Enter node labels with commas or one label per line.
Enter edges line by line using formats like A-B or A->B.
Set the start node and add a target node if path checking is needed.
Choose input, ascending, or descending neighbor order.
Enable directed mode for one-way edges.
Enable full traversal to continue through disconnected graph parts.
Click Run Depth First Search to show results above the form.
Review traversal order, timestamps, parent links, depth values, cycle detection, and the Plotly graph.

FAQs

1. What does this calculator compute?

It runs depth first search on a graph and reports traversal order, discovery times, finish times, parents, node depths, cycle hints, components, and optional target paths.

2. How should I enter edges?

Use one edge per line. Accepted styles include A-B, A B, A,B, and A->B. Node names should stay compact, using letters, numbers, or underscores.

3. What changes when directed mode is enabled?

Only the entered edge direction is followed. Connectivity is then reported as weak connectivity, because standard connectedness is defined differently for directed graphs.

4. What are discovery and finish times?

Discovery time marks when DFS first visits a node. Finish time marks when all of that node’s reachable descendants have been fully processed.

5. Why can traversal order change?

DFS depends on neighbor ordering. Changing input, ascending, or descending order can produce different valid traversals while still using the same graph.

6. What does DFS forest count mean?

A DFS forest appears when the graph has multiple disconnected parts or when full traversal continues beyond the starting component. Each root starts a new tree.

7. Can the calculator stop at a target node?

Yes. Enable the stop option to halt further expansion after the target is reached. This is useful when you only need an early path result.

8. Is DFS the same as shortest path?

No. DFS explores deeply before backtracking. It can find a path, but it does not guarantee the shortest path in general graphs.