Depth-first search (DFS)

This is a way of traversing a graph (could be a directed graph or undirected graph). It explores all the way down one branch of the graph before tracing and exploring other branches.

The generally runs in time.

Examples

• DFS to find connected components in an undirected graph
• DFS to find path in a directed graph
• DFS to find path in an undirected graph