1
00:00:06,200 --> 00:00:11,240
In this lecture, we are going to begin discussing breadth for search.

2
00:00:12,680 --> 00:00:19,430
So unlike depth for search, breadth first search is going to again start at a tree root.

3
00:00:19,430 --> 00:00:21,380
So some arbitrary node.

4
00:00:21,530 --> 00:00:28,730
And then instead of going all the way as deep as it can, it's going to fan out first.

5
00:00:28,730 --> 00:00:36,350
So it's going to explore all the nodes at the present depth prior to moving on to the nodes at the next

6
00:00:36,350 --> 00:00:37,220
depth level.

7
00:00:37,220 --> 00:00:43,190
So that's the difference between depth first search and breadth first search depth first goes to tries

8
00:00:43,190 --> 00:00:51,530
to go to the end, breadth first fans out and hits all the nodes at the current depth before continuing

9
00:00:51,530 --> 00:00:52,040
on.

10
00:00:52,550 --> 00:01:02,750
So to keep it congruent, let's go ahead and recreate our graph from the next or excuse me, from the

11
00:01:02,750 --> 00:01:03,560
previous lecture.

12
00:01:03,560 --> 00:01:05,810
So we add a CB.

13
00:01:06,230 --> 00:01:09,560
We have DX with both of these funneling to it.

14
00:01:10,760 --> 00:01:20,360
DX goes to E, which goes to F and this goes to G or to G back to EA.

15
00:01:20,570 --> 00:01:21,830
We have

16
00:01:23,960 --> 00:01:36,530
h, i, j k, and then we have an L here which connects back to EA as well.

17
00:01:37,550 --> 00:01:48,890
So we are going to start at a and then our visited is going to be like this.

18
00:01:48,890 --> 00:01:54,380
So we'll go from a, from a we can go to C at the same depth.

19
00:01:54,380 --> 00:02:03,500
We also have B so we can go from A to B from C and B they both go to D so that's an obvious one.

20
00:02:03,500 --> 00:02:10,010
D can only go to EA and now EA can go to F.

21
00:02:13,180 --> 00:02:22,960
E can go to h h can go to I h can go to J and h can go to K.

22
00:02:22,960 --> 00:02:27,100
So we got i j and k.

23
00:02:28,660 --> 00:02:32,260
So also at E we have g.

24
00:02:34,520 --> 00:02:38,180
And lastly, we have l.

25
00:02:40,340 --> 00:02:48,680
So overall this concept shouldn't be too challenging since we have a really good idea of how depth first

26
00:02:48,680 --> 00:02:49,700
search works.

27
00:02:50,510 --> 00:02:58,430
Again, the key difference between depth first and breadth first is that depth goes all the way from

28
00:02:58,430 --> 00:03:05,660
A to down here as quickly as possible without worrying about branching out.

29
00:03:05,660 --> 00:03:11,770
So we went a D all the way to L before we even got to see in depth first.

30
00:03:11,780 --> 00:03:16,580
Whereas breadth first, we look at everything that's on that depth level.

31
00:03:16,580 --> 00:03:20,030
So we had a C, but we also had B, then we went to DH.

32
00:03:20,210 --> 00:03:24,770
So that's the big difference between depth first and breadth first.

33
00:03:24,770 --> 00:03:31,190
So what we can do is now we can go implement in our own solution to breadth first and run our test cases

34
00:03:31,190 --> 00:03:36,080
on it to see how it will compare to depth first.

35
00:03:36,560 --> 00:03:42,500
And we will begin implementing in breadth first in the next lecture.