1
00:00:06,130 --> 00:00:12,040
In this lecture, we are going to start looking at the depth first search graphing algorithm.

2
00:00:13,420 --> 00:00:19,450
This algorithm is going to start at a root node, which we are going to pass into it, and then it's

3
00:00:19,450 --> 00:00:25,360
going to explore as far as possible along each branch before backtracking.

4
00:00:25,870 --> 00:00:27,670
So there's a couple of things that we need.

5
00:00:27,700 --> 00:00:30,820
The first thing we need is a starting vertex.

6
00:00:35,590 --> 00:00:42,610
And the second thing that we need is to make sure that we track the vertex, the vertices that we have

7
00:00:42,610 --> 00:00:43,330
visited.

8
00:00:44,500 --> 00:00:48,400
So make sure to track

9
00:00:50,830 --> 00:00:52,210
visited

10
00:00:54,940 --> 00:01:07,750
vertex so we can create a simple graph and we'll say A, C, B, and then we will connect both to DX.

11
00:01:09,070 --> 00:01:19,540
We'll go from D to e, P to F to G, back to E, and we will take e to H.

12
00:01:19,570 --> 00:01:21,460
H will go to i.

13
00:01:22,240 --> 00:01:24,610
J and k.

14
00:01:25,540 --> 00:01:30,040
K will go to l and L will connect back to it.

15
00:01:31,540 --> 00:01:34,840
So a will be our starting vertex.

16
00:01:35,020 --> 00:01:45,460
So we will go a and then we can either go to C or to B, we will pick B since it shows up first and

17
00:01:46,540 --> 00:01:47,530
the alphabet.

18
00:01:47,530 --> 00:02:00,160
So we will go A to B, D, e from E, we can go to h, l, f and g, so we'll go f to G following the

19
00:02:00,160 --> 00:02:04,120
same criteria as before with what character shows up first.

20
00:02:04,390 --> 00:02:09,310
And since we're g we don't go back to E this way we backtrack.

21
00:02:09,310 --> 00:02:17,680
So we go from G to F, back to E, and from E, we now go to H, which we will now be able to visit

22
00:02:17,680 --> 00:02:18,910
IJ and K,

23
00:02:22,150 --> 00:02:28,690
and from K we can get to L and from L, we see that we're back to E.

24
00:02:28,720 --> 00:02:30,490
Well, we go backtrack now.

25
00:02:30,490 --> 00:02:42,340
So we go L to k, to h, to e, to D, to B to A, and the last vertex we need to visit is C, So now

26
00:02:42,340 --> 00:02:49,390
we finally make it to C, So as you saw, what we did there is we started out at our starting node and

27
00:02:49,390 --> 00:02:55,900
we tried to get as deep into the graph as possible to visit all of our nodes before we branched out

28
00:02:55,900 --> 00:02:59,950
the from A to our other C.

29
00:02:59,950 --> 00:03:04,000
So that was the last node that the last vertex we needed to visit.

30
00:03:05,680 --> 00:03:19,540
If we look at one more, we will say 1 to 3 and then from two we will go for five, three will go to

31
00:03:19,540 --> 00:03:22,090
six and three will go to seven.

32
00:03:22,210 --> 00:03:30,640
So if we start out at one, we will say one, two and then we will visit four and five.

33
00:03:30,640 --> 00:03:35,050
And now that we've hit all the vertices over here, we begin backtracking.

34
00:03:35,050 --> 00:03:39,760
So we'll go from five to 2 to 1 and now we'll go to three.

35
00:03:40,060 --> 00:03:42,430
And now we can hit six and seven.

36
00:03:44,110 --> 00:03:52,450
And what we'll do with this graph is this will be our test graph when we begin when we begin testing

37
00:03:52,450 --> 00:03:57,250
our depth for search implementation and the next lecture.