-1

Can anyone tell me in simple terms, how is backtracking used in a depth-first traversal? I am struggling to understand so I could use an example.

Thanks.

Sourav Multani
  • 1
  • 4
    Does this answer your question? [What's the difference between backtracking and depth first search?](https://stackoverflow.com/questions/1294720/whats-the-difference-between-backtracking-and-depth-first-search) – diogenesgg Jan 22 '20 at 20:59

1 Answers1

0

Backtracking is used in depth-first traversals every time you hit a “dead-end”. It ensures that every path is eventually explored. For example, let’s say given this graph, you do a depth-first traversal starting at A. (We’ll use the convention that left children go first.)

1. A -> B (blue in the picture)

B has a child! Nice, we’ll go there.

2. B -> D (green in the picture)

D has 2 children! Nice, let’s go left first.

3. D -> E (purple in the picture)

Uh oh, E has no children! This is a dead end. This means we need to backtrack one level (go back “up” to D), and see if we have other paths we can search.

Yes — D has another unexplored child. Let’s go there.

4. D -> F (pink in the picture)

F has no children! This is another dead end, let’s backtrack one level (“up” to D), and see if we have other paths to search.

No — D has no children left. Let’s backtrack another level (“up” to B).

No — B has no children left. Let’s backtrack another level.

Yes — A has another unexplored child! Let’s go there.

5. A -> C (yellow in the picture)

C has no children. Let’s backtrack another level.

No — A has no children left to explore, and it’s the root. This means our traversal is done! :)

Rhiannon Moilanen
  • 1