Depth-First Search and Depth-First Traversal

Depth-first search is a method for walking through a tree or graph where you go as deep as possible…

Depth-first search (DFS) is a method for exploring a tree or graph. In a DFS, you go as deep as possible down one path before backing up and trying a different one.

Depth-first search is like walking through a corn maze. You explore one path, hit a dead end, and go back and try a different one.

Here's a how a DFS would traverse this tree, starting with the root:

We'd go down the first path we find until we hit a dead end:

Then we'd do the same thing again – go down a path until we hit a dead end:

And again:

And again:

Until we reach the end.

Depth-first search is often compared with breadth-first search .

Advantages:

Disadvantages:

Date: 2020-01-30 Thu 21:59

Author: Jack Liu

Created: 2020-02-08 Sat 21:26

Validate