# DFS

### From charlesreid1

## Depth first search notes

Depth first search utilizes backtracking and recursion to explore each node of a tree, or each vertex of a graph, exactly once.

On a graph, depth-first search is a crucial building block of several algorithms related to connectivity, such as finding cycles, determining of two vertices are connected, and constructing spanning trees.

For an example of depth-first search on a graph, see traveling salesperson problem page.

## Related

Recursion:

- See Recursion

Graphs:

- Graphs#Graph Traversals
- Graphs/Depth First Traversal
- Graphs/Breadth First Traversal
- Graphs/Euler Tour

Traversals on trees:

Breadth-first search and traversal on trees:

Depth-first search and traversal on trees:

OOP design patterns:

## Flags

TreesSeries on Data Structures Abstract data type: Trees/ADT Concrete implementations: Trees/LinkedTree
Preorder traversal: Trees/Preorder Postorder traversal: Trees/Postorder In-Order traversal: Binary Trees/Inorder Breadth-First Search: BFS Breadth-First Traversal: BFT Depth-First Search: DFS Depth-First Traversal: DFT OOP Principles for Traversal: Tree Traversal/OOP Tree operations: Trees/Operations Performance
Finding Minimum in Log N Time: Tree/LogN Min Search
Abstract data type: Binary Trees/ADT Concrete implementations: Binary Trees/LinkedBinTree Binary Trees/Cheat Sheet
· Template:TreesFlagBase · e |