How depth first traversal works?

Software Development
#1

How depth first traversal works?

#2

When doing Depth First Search (also known as DFS), we go in the depth of neighbours of a vertex instead of first visiting all the neighbours, it can sometimes lead to faster searches based on the problem given.

image

#3

You have a graph of cities, i.e. a map. You start from a city and then go to one of its neighbours (of course, there must be a road between these 2 cities). When you are in the neighbour city, you go to one of its neighbouring cities.

All this time you keep a checklist and mark each visited city, so you don’t visit the same city twice.
At some point you will reach a city from where you can go to no other city (because all its neighbours are visited). So you go back on the same route you came, until you find a city with a not-visited neighbour and take that route.

You keep going through the whole graph of cities like this until everything is visited or, if you have a goal (i.e. reach a city whose name starts with ‘K’) until you reach your goal.