1
00:00:01,170 --> 00:00:04,860
So we now have a pretty good idea about what is recursion.

2
00:00:05,430 --> 00:00:08,250
This means that we are ready to learn about the DFS.

3
00:00:09,000 --> 00:00:16,920
Now DFS or Defi's Surge is a blind search algorithm that starts at any node and goes as far as possible

4
00:00:17,010 --> 00:00:21,360
in a specific row and then backtracks until it finds a different route.

5
00:00:22,200 --> 00:00:29,370
Now, this will continue until the gold node has been found or all node has been visited in a maze.

6
00:00:29,670 --> 00:00:35,220
This amounts to going as far as possible in a specific part, until that path leads to a dead end.

7
00:00:35,640 --> 00:00:38,190
And then backtracking and finding a new but.

8
00:00:39,280 --> 00:00:40,630
Let's see how this pans out.

9
00:00:40,900 --> 00:00:42,010
Example scenario.

10
00:00:44,290 --> 00:00:50,020
Now suppose your Goku and your powers are gone and the only way forward is through the maze.

11
00:00:50,710 --> 00:00:56,050
So the defenses that keep going on, the way you're going onto that path leads to a dead end.

12
00:00:56,590 --> 00:01:00,610
So you do exactly that and encounter three in points.

13
00:01:01,940 --> 00:01:02,360
One.

14
00:01:03,260 --> 00:01:03,620
Do.

15
00:01:04,660 --> 00:01:05,020
Three.

16
00:01:06,990 --> 00:01:11,070
Until finally you encounter a dead end.

17
00:01:14,860 --> 00:01:19,690
So you will have to backtrack to previous interest points and find a new route.

18
00:01:20,230 --> 00:01:20,980
So you do that.

19
00:01:23,220 --> 00:01:29,670
One, do you encounter a new route and then follow along the route?

20
00:01:30,180 --> 00:01:34,290
Now, this procedure will continue until you find the Google note.

21
00:01:36,140 --> 00:01:39,500
This means that you have found the Google note and you're free.

22
00:01:39,800 --> 00:01:41,390
So the algorithm has ended.

23
00:01:42,320 --> 00:01:46,100
Let us now look at a few notable characteristics of the DFS.

24
00:01:50,020 --> 00:01:52,870
The number one is that a deficit is complete.

25
00:01:53,590 --> 00:01:57,910
So if the graph has no cycles, so the DFS will definitely find a path.

26
00:01:58,830 --> 00:02:01,530
Number two, it is not optimal.

27
00:02:02,010 --> 00:02:09,930
This is because the cost of finding the solution is high as it is a blind search algorithm and finally

28
00:02:10,470 --> 00:02:17,670
it is implemented using stick to keep track of all the visited nodes for backtracking later in last

29
00:02:17,670 --> 00:02:18,870
in first out order.