All language subtitles for 23 - Breadth First Search English

Find this video we're going to talk about breadth first search.

And one important video to watch before going through this tutorial is to make sure you're familiar

with what a cue is.

And I created a video talking about the difference between a stack and a Q and Q is just an abstract

data structure but it's what gets used with Brett for search so it's a helpful thing to know before

we go in on how this works.

I want to just point out one thing you may hear a lot of people talk about breadth first search and

how that compares with depth first search.

The biggest Kieta know it is breadth first search actually goes one layer at a time.

So if you're searching for an item in using a breath search methodology you're going to go here first

then you're going to go to all these nodes then you're going to go all these nodes and then finally

these lines and you're going to do it one layer at a time.

And I'm going to do that visually here in a second.

So say you want it to go through and see the order that you would find these nodes say these you know

these are all values that we don't know what they are.

So you can see this is not a binary search tree has some resemblances to it but it doesn't actually

it doesn't have the same properties.

This is going to show you how you could use a unstructured tree and see how to go through it and find

the item you're looking for.

So the way that you'd actually go through it is you'd first start at the root node.

And so we're going to give that a 1.

And so one would go into the queue.

After that you'd go to the left side and this would be a two and then you wouldn't keep going down the

left you would go now to all of the items in this level so that 1 2 three four.

And then we just go down to the other level.

So I would go five six seven eight and then we'd finish it off by going to this fourth level.

And so we'd have nine 10 11 and 12.

So the algorithm for breath first search is first you put the root node right here in the queue.

Then you remove a node from the queue and examine it.

So that's the process of going here and then going down to the next one.

And I could draw these arrows going to each node like so and you can see the flow goes like this level

this level.

And then that level and so the what's happening behind the scenes is you're moving a node from the queue

you're examining it.

If the goal element.

So what we're searching for.

So say we're searching you know for five have reset X equal to 5 we would search is five equal to 1.

No it's not.

So then you go down to 2 3 4 and then you finally find your element at 5 but that's the order that you

would search in.

So if it's not you put the successor which is the direct child node that have not been discovered into

the queue which is all that means is that you'd take whatever element and then go down to the next one.

If the element you are inspected is not the one that you're looking for.

If the queue is empty every node has been examined.

So that would be if we get down to 12.

And so if that's the case and we haven't found our item that means that the search returned a null value

which means the item was not included in the data structure.

And so if the queue is not empty then you would just keep on going so the queue is not going to be empty

until you get to this very last value.

So if you may wonder if you're like me why you'd ever use breath first search because that was my very

first thought because binary search trees are you know much more useful and there are also at least

to me a lot easier to understand.

And so what was explained to me is if you're building something like a artificial intelligence agent

and you say for example you want to build an agent that knows how to play chess in order to teach it

how to play chess you would actually give it a series of moves and then you would have the agent or

your artificial intelligent robot or a piece of software be able to make adjustments based off of those

moves in a good way of doing it is using breath for a search.

So say for example that the very first move that was made on the chess board was to this three value

right here.

If that was the case then you would be able to ignore the rest of all these items and you'd be able

to then just go down the line and say OK the only moves that matter from this point on are the ones

that are descended from this 3 node.

So the breadth first search isn't the best.

The best thing to use in every case however there are some cases where it actually is the most efficient

by far especially if you're doing things with having to do with artificial intelligence or you're doing

things that have a pre-determined set of steps so that you know that at each level there is a certain

item that it can be selected and that's going to be the most efficient way of doing it.

So that's a brief explanation of breath first search and the next video we're going to go over depth

first search and how that can be utilized in algorithm development.