# Depth-first search

## Search algorithm / From Wikipedia, the free encyclopedia

#### Dear Wikiwand AI, let's keep it short by simply answering these key questions:

Can you list the top facts and stats about Depth-first search?

Summarize this article for a 10 year old

SHOW ALL QUESTIONS

**Depth-first search** (**DFS**) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking. Extra memory, usually a stack, is needed to keep track of the nodes discovered so far along a specified branch which helps in backtracking of the graph.

This article needs additional citations for verification. (July 2010) |

**Quick Facts**Class, Data structure ...

Order in which the nodes are visited | |

Class | Search algorithm |
---|---|

Data structure | Graph |

Worst-case performance | $O(|V|+|E|)$ for explicit graphs traversed without repetition, $O(b^{d})$ for implicit graphs with branching factor b searched to depth d |

Worst-case space complexity | $O(|V|)$ if entire graph is traversed without repetition, O(longest path length searched) = $O(bd)$for implicit graphs without elimination of duplicate nodes |

Optimal | no (does not generally find shortest paths) |

Close

A version of depth-first search was investigated in the 19th century by French mathematician Charles Pierre Trémaux^{[1]} as a strategy for solving mazes.^{[2]}^{[3]}