Home

About 

Depth-First Search (DFS) is a type of uninformed (blind) search algorithms.

DFS traverses search trees vertically first, looking for a goal.

Works on a LIFO (last-in, first-out) principle of a queue.

Start (initial node) is added to a queue.

Initial node is popped from the queue, and checked if it's a goal; if not, DFS expands it, and adds its children to the queue (at the beginning).

Then repeats the same for each node in a queue recursevily, in opposite order of their insertion to the queue (LIFO).

Pops node from the queue, checks if it's a goal; addss its children to the beginning of a queue.

Thus, DFS algorithm always checks all nodes in the same depth level first, before going deeper.

Algorithm's Metrics:

Completeness: not complete in general - if the search space is infinite or contains loops, can get stuck on endless path, or in a cycle revisiting the same nodes forever (unless keeping track of visited nodes)

Optimality: not optimal - finds the first solution it encounters, not necessarily the best; even if all step costs are equal, DFS might find a longer solution, because it goes deep before exploring alternatives

b - branching factor; m - maximum-depth

Time Complexity: O(b^m)

Space Complexity: O(bm) [stores only one path from root to leaf plus unexplored siblings → more memory-efficient]