{"id":106,"date":"2014-12-26T14:44:22","date_gmt":"2014-12-26T14:44:22","guid":{"rendered":"http:\/\/theoryofprogramming.wordpress.com\/?p=106"},"modified":"2023-11-11T16:31:31","modified_gmt":"2023-11-11T16:31:31","slug":"depth-first-search-algorithm","status":"publish","type":"post","link":"https:\/\/theoryofcoding.com\/index.php\/2014\/12\/26\/depth-first-search-algorithm\/","title":{"rendered":"Depth First Search Algorithm"},"content":{"rendered":"\n

Hello people…! In this post I will talk about the other Graph Search Algorithm, the Depth First Search Algorithm. Depth First Search is different by nature from Breadth First Search. As the name suggests, “Depth”, we pick up a vertex S<\/strong> and see all the other vertices that can possibly reached by that vertex S <\/strong>and we do that to all vertices in V<\/strong>. Depth First Search can be used to search over all the vertices, even for a disconnected graph. Breadth First Search can also do this, but DFS is more often used to do that. Depth First Search is used to solve puzzles! You can solve a given maze or even create your own maze by DFS. DFS is also used in Topological Sorting, which is the sorting of things according to a hierarchy. It is also used to tell if a cycle exists in a given graph. There are many other applications of DFS and you can do a whole lot of cool things with it. So, lets get started…!<\/p>\n\n\n\n

The way the Depth First Search goes is really like solving a maze. When you see a maze in a newspaper or a magazine or anywhere else, the way you solve it is you take a path and go through it. If you find any junction or a crossroad, where you have a choice of paths to choose, you mark that junction, take up a path and traverse the whole route in your brain. If you see a dead end, you realize that this leads you now where so you come back to the junction you marked before and take up another path of the junction. See if that is also a dead end, else you continue to explore the, puzzle as this route contributes in reaching your destination. Well, at least that’s how I solve a maze. But… I hope you get the idea. You pick up a path and you explore it as much as possible. When you can’t travel any further and you haven’t yet reached your destination, you come back to the starting point and pick another path.<\/p>\n\n\n\n

In code, you do this by recursion. Because of the very nature of recursion. Your recursion stack grows-grows and eventually becomes an empty stack. If you think for a while you can notice that the way of traversing which I told you above is logically covering only the vertices accessible from a given vertex S<\/strong>. Such traversal can be implemented using a single function that is recursive. But we want to explore the whole graph. So, we will use another function to do this for us. So, DFS is a two-functions thing. We will come back to the coding part later. Now, DFS too can be listed out in a step-by-step process –<\/p>\n\n\n\n