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
High in this video I'm going to go over an algorithm called Prim's algorithm and what Prim's algorithm
is at a high level is a greedy algorithm for finding the minimum spanning tree of a graph.
If you don't know what that means that's perfectly fine it actually is a lot easier to understand than
that it's finding or whatever path has the lowest value in a graph.
And so it means that right here is you can see on the graph we have values like 3 and 4 in 1 to 7.
Every single one of the edges has a weight associated with it.
And what we're looking for is the path that connects all of the nodes together that has the lowest number.
And I'm going to go through and show you how that works on a step by step basis and you'll understand
how Prim's algorithm works.
Once that happens.
So the very first thing to do is to pick a node in the graph and it can be completely arbitrary.
And so if you're new to graph algorithms and digraphs in general nodes are the circles like that and
then the edges are the lines that connect those nodes together and the nodes are also called vertexes
as well.
I'm going to call them nodes for the sake of this discussion because that's how I learned them.
So we're going to start at A.
So this is going to be our starting point right here.
We could have started though at Or we could have started anywhere we wanted but we're doing it just
because I think it's a little bit easier to read it this way.
And the very first thing we're going to do is we're going to look at a and we're going to see what edges
it has connected to what nodes.
So we can see right here that we have a is connected to B and the value of A to B.
So if we go A to B there as a way of 3 then we have another option A to see an ADA see has a weight
of for because then all we have to do is we just compare these two.
We see that three is less than four.
And so we know three is going to be the option which means A to B is going to be our very first option
and that is essentially as easy as it gets.
And the only complicated thing will happen here in a second I'll show you how that works.
So the very first thing that we're going to do is I'm just going to color this so you can see the way
it actually works.
So we're going to go to be and we're going to take up that line.
And now this edge is taking care of.
So we know we're going here now that we have that set up.
Now all we have to do is add in the other options.
So if we want to connect to different nodes we can see that B has a few different options we can go
B to either we can go BTD we can go B to C.
And because of the way the Prim's algorithm works we can actually still go Atassi.
So that one is still available to us.
So if you think of the algorithm in a certain real world can't sense it's almost like a snowball as
you add new edges and new nodes every step of the way.
You add in all of their possible connections.
So we started off with just when we had just a in our set we only had two options but now that we have
a and b in our set now we have a to be or I'm sorry we have to see which we solve that one.
Then we have three other options.
And so now we have a total of four different items that we're going to be comparing.
So let's do that.
So we'll just take a nice easy approach and just go from top to bottom with it.
So B-D is 5 to DS 2 b c is 1 and A to C is 4.
So we can see pretty easy B to C is switch colors.
B c is going to be our best option.
So we now have those points connected.
Another important thing to know about Prim's algorithm is once once an edge is connected or once a node
has been reached I should say then we don't have to worry about connecting it again.
So in other words this a c is no longer necessary.
So this for we can cross off because A is now in our set B's and our set in C is in our set.
So there is no reason to go from A to C anymore.
So we don't have to worry about that which makes it nice and that gets to be one item that gets crossed
off our list.
So now that we have these now we can see we still have BT which is five BDD which is two.
Then we have seeded D which is 7 and C to F which is 8.
It's pretty easy to see we have B to D is our best option.
And the way Prim's works it's very easy you just keep on recursively going down adding different nodes
and then adding in all of the items that they point to.
So we need to get to E and F now and to do that we just compare all of the items whether it's from B
D or C so we can see we have a five a 9 a three and a name.
Obviously a three is our best option right there.
And so now we have f covered and the last item is to connect the we have 5 9 and 6 5 is our best pick
and there we go.
So if I know the graphs a little bit messy so I'm going to actually write out what our best options
are.
So we have
to be
then we have to see and we have BTD
then we have B E.
And lastly we have deid
And there you go.
If you take each one of these items each one of these connections where are these nodes are connected
you will have your minimum spanning tree for this graph and you use Prim's algorithm in order to get
it.
So good job.
And let me know if you have any questions at all about that video.
Can't find what you're looking for?
Get subtitles in any language from opensubtitles.com, and translate them here.