All language subtitles for 22 - Prims Algorithm English

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.