generic priority queue code is going to work fine.

And so, what we'll do is we'll put all the edges in the graph into the priority

queue. So that's building a priority queue.

Containing all the edges in the graph. Alternatively, we could put the edges in

an array and sort the array, but priority queues.

A more elegant way to express this, and is a way to look at more efficient algorithms

as well. Okay, so that's priority queue, so that's

the first data structure from part one that we're going to make use of.

And then the second one is the union find data structure.

So we're going to build a union find data structure with for vertices because the

spanning force divides the vertices into equivalence classes.

So then we go into the main loop. And the main loop stops in two conditions.

We run out of edges is one, where we'd have a minimum spinning force.

Or the other condition is we get to V - one edges in the MST.

So as long as neither one of those is true, then we've got an edge in the

priority queue, and we want to take the smallest one.

We want to get its vertices V and W either and other.

And then we want to check using the union find algorithm if they're connected.

If they're connected we don't want to do anything, if they're not connected then we

want to merge them, and put that edge onto the MST.

Thats it. And then when the that's the full

implementation and then we have the edges method for the client to return the MST.

It's quite a compact implementation of a classic algorithm.

Using the basic data structures that we built up in algorithm part one data

structures and algorithms of priority queue.

And union find gives a, a, really fine implementation of this MST algorithm.

So what about the running time of this algorithm?

Well it's not hard to see that it's going to compute the MST in time proportional to

e log e. It's linearithmic in the number of edges.

Which means that we can use it for huge graphs.

So this is just, this table is just a proof that, summarizes the costs.

We're going to first build the priority queue.

And, we can do that in linear time using bottom-up, construction method.

We have to, every edge comes off the priority Q.

So there's E of them, and it takes log E per operation.

Snd then union operations, every vertex is involved in one, and connected operations,

every edge is involved in one. So the total time is dominated by the E

log E for the priority queue operations. One thing to note is that, if the edges

come in, in sorted order, for some reason, it's almost linear.

The order of growth is E log star of E. And, actually we don't have to always,

sort'em. We can, in real life situations, we can

stop when we get the V-1 edges in the MST. When we have those v - one edges we can

stop and usually that's for practical situations that's way before we see all

the edges in the graph. So that's Kruskal's algorithm for

computing the MST.