Algorithms/Graph/Depth-First Search

Depth-First Search (DFS)

Explore as deep as possible along each branch before backtracking. Utilizes a LIFO stack or call stack recursion.

GraphTraversalStack (LIFO)RecursionBacktrackingO(V+E)

Graph Canvas(7 nodes, 10 edges)

1 / 0

Speed

bfs.js

1function dfs(graph, source, target) {

2 const stack = [source];

3 const visited = new Set();

4 const prev = { [source]: null };

5 const path = [];

7 while (stack.length > 0) {

8 const current = stack.pop(); // Pop LIFO

9 if (visited.has(current)) continue;

10 visited.add(current);

11 path.push(current);

12 if (current === target) break;

14 for (const neighbor of graph[current]) {

15 if (!visited.has(neighbor)) {

16 prev[neighbor] = current;

17 stack.push(neighbor); // Push to stack

18 }

19 }

20 }

21 return { path, prev };

22}

Algorithm Explanation

Depth-First Search (DFS) is an essential graph traversal algorithm that explores as far as possible along each branch before backtracking.

⚙️ How It Works

Initialize — Push the starting source node onto a Last-In-First-Out (LIFO) stack (or invoke recursive call).
Visit Node — Pop the top node, record its discovery timestamp d[u], and mark it as visited.
Explore Deeply — Push unvisited adjacent neighbors onto the stack to push deeper into unexplored branches.
Backtrack — When a dead end (no unvisited neighbors) is reached, step backward up the stack and record finish timestamp f[u].
Complete — Terminate when the stack is empty or target node is reached.

🔑 Discovery (d) and Finish (f) Timestamps

In DFS, each node u receives two integer timestamps:
• d[u]: The counter step when node u is first discovered.
• f[u]: The counter step when node u's adjacency list has been fully explored.
The interval [d[u], f[u]] forms a well-parenthesized nested structure used for topological sorting and cycle detection.

💡 Dynamic Graph Extension: You can add new nodes and custom edges to the graph using the + Add Node tool in the visualizer above!

Click nodes to set source/target · Toggle Iterative/Recursive mode · Use "+ Add Node" to extend graph topology