Afrikaans
Akan
Albanian
Amharic
Armenian
Azerbaijani
Basque
Belarusian
Bemba
Bengali
Bihari
Bosnian
Breton
Bulgarian
Cambodian
Catalan
Cebuano
Cherokee
Chichewa
Chinese (Simplified)
Chinese (Traditional)
Corsican
Croatian
Czech
Danish
Dutch
English
Esperanto
Estonian
Ewe
Faroese
Filipino
Finnish
French
Frisian
Ga
Galician
Georgian
German
Greek
Guarani
Gujarati
Haitian Creole
Hausa
Hawaiian
Hebrew
Hindi
Hmong
Hungarian
Icelandic
Igbo
Indonesian
Interlingua
Irish
Italian
Japanese
Javanese
Kannada
Kazakh
Kinyarwanda
Kirundi
Kongo
Korean
Krio (Sierra Leone)
Kurdish
Kurdish (Soranî)
Kyrgyz
Laothian
Latin
Latvian
Lingala
Lithuanian
Lozi
Luganda
Luo
Luxembourgish
Macedonian
Malagasy
Malay
Malayalam
Maltese
Maori
Marathi
Mauritian Creole
Moldavian
Mongolian
Myanmar (Burmese)
Montenegrin
Nepali
Nigerian Pidgin
Northern Sotho
Norwegian
Norwegian (Nynorsk)
Occitan
Oriya
Oromo
Pashto
Persian
Polish
Portuguese (Brazil)
Portuguese (Portugal)
Punjabi
Quechua
Romanian
Romansh
Runyakitara
Russian
Samoan
Scots Gaelic
Serbian
Serbo-Croatian
Sesotho
Setswana
Seychellois Creole
Shona
Sindhi
Sinhalese
Slovak
Slovenian
Somali
Spanish
Spanish (Latin American)
Sundanese
Swahili
Swedish
Tajik
Tamil
Tatar
Telugu
Thai
Tigrinya
Tonga
Tshiluba
Tumbuka
Turkish
Turkmen
Twi
Uighur
Ukrainian
Urdu
Uzbek
Vietnamese
Welsh
Wolof
Xhosa
Yiddish
Yoruba
Zulu
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.
Can't find what you're looking for?
Get subtitles in any language from opensubtitles.com, and translate them here.