Depth First Search using Recursion

Jaani Solves

Hi readers,

Here I am back with today’s topic – Depth First Search(DFS), using recursion. This is one of the most beautiful traversal I personally have ever encountered. Now lets understand the applications of this algorithm, which will  prove its importance:

  • Solving maze puzzles having just one final solution
  • Maze generation
  • Finding bi-connectivity in a graph
  • Finding bridges in a graph
  • Finding connected components
  • Topological sorting

So this algorithm is really worth knowing! Well, lets start!

Pre-Requirements:

  1. Basics of trees
  2. Implementing a basic tree in your favorite language

(binary trees will be more than enough as of now)

What does this algorithm do?

As the name suggests, this algorithm goes till the end of the node starting from the root node, traces back the path and reaches for the other branches branching from below, unless an external stopping condition is given or the branches gets exhausted. You can imagine it as something like…

View original post 228 more words

Advertisements
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s