Now we will look a Kruskal's algorithm for computing the MST this is an old algorithm
that dates back over 50 years but it is an effective way to solve the problem.
The idea is very simple. We are going to take the edges and we are
going to sort them by weight. And we are going to consider ''em in order
of ascending weight. And the algorithm is simply add the next
edge to the tree. Unless that edge would create a cycle.
If it, if the edge creates cycle, ignore it and go on to the next one.
Let's look at a demo of Kruskal's algorithm.
Okay. So we have the edges sorted by weight and
we're going to take them in ascending order of weight.
The smallest edge is in the MST. And so we add that to the tree it doesn't
create a cycle. Next smallest edge is two, three.
That doesn't create a cycle. Next one is one, seven that's fine.
Next one is zero, two. Next one, five, seven.
Now when we get to one, three that one creates a cycle and the algorithm says,
creates a cycle just ignore it. Next one is one, five that one also
creates a cycle. one, five, seven. Again, just ignore it.
Two, seven creates a cycle not in the MST. Four, five that, the next smallest edge
does not create a cycle so we add it to the MST.
One, two creates a cycle. Four, seven creates a cycle.
Zero, four creates a cycle. And finally we get to six, two which does
not create a cycle, so we add that to the tree.
At this point we have an MST we could check that we have V - one edges and stop
or we can just keep going and see that the other edges in the graph create a cycle.
And when we're done considering all the edges then we have computed the minimum
spanning tree. That's with Kruskal's Algorithm.
Consider the edges in descending order of weight, add the next edge to T, unless
doing so would create a cycle. Now let's look at what Kruskal's algorithm
does on a very large graph. You get a good feeling for what it's
doing. It's taking the small edges and they
coalless together in little clusters and eventually the edges get longer and longer
and they connect together the clusters. Initially it is broken up into the very
small edges and after a while if you look at the larger clusters eventually an edge
will come that will connect them together. It's not going to be so easy to see how
the algorithm ends. Though there's some, long edge there.
That's the longest edge in the MST that'll finally connect the graph.
This simulation really gives a good feeling for Kruskal's algorithm.
In fact when we first had personal computers I was fortunate to be in Xerox
Park. And I remember very well in the late 70s,
This was one of the first algorithms that I wanted to see visualized on a personal
computer. And I, I wrote a program at that time that
produced pretty much this image it's a very interesting way to look at MST
algorithms. Alright, so it's easy to implement we have
to prove that it computes the MST of course I and we've done a lot of work
setting that up. And.
We do so just by proving that its a special case of the greedy MST algorithm.
So what does that mean? Well.
It, suppose that crosco's algorithm. Colors a given edge black.
So say it's VW. So we'll define a cut.
That, is the set of vertices that are connected to V.
So it might be just a V, but if theres any black edges connecting V to other vertices
we put all of those in the cut. So for that cut there's no black crossing
edge. Cuz it's a, it's a component.
And the other thing is that there's no crossing edge with lower weight than VW.
And why is that? Well we haven't examined any of those
edges yet, and they're all longer because we are considering the edges in increasing
order of their weight. So this new edge that connects V somewhere
else is a crossing edge of minimal weight. And so therefore the algorithm always
finds a cut and colors a crossing edge of minimal weight for that cut black.
And it's an instance of the Greedy Algorithm.
Now we still have a bit away from having an implementation of Kruskal's algorithm.
So the question is, how do we know whether adding a new edge to the tree will cause a
cycle? So, you might think about how difficult
that is. I've, I've got a tree, that's represented
as the set of edges or however. And I have a new edge, and I want to know
whether it creates a cycle or not. How, how difficult is that going to be?
Well, it turns out way back in the first lecture of algorithms part one we had a
way. What one thing we could do is just run DFS
to check if we can get to W from V. That'd take time proportional to V.
But the union find data structure that we did in the first lecture absolutely does
the job. It's just testing whether this edge
connects anybody in, in the equivalence class corresponding to V with anybody in
the equivalence class corresponding to Y, for to W and if it did, it creates a
cycle. So union find is exactly what we need.
So we're going to what we're going to do is maintain a set for each of the
connected components in the spanning tree, that we built up so far and so if the new
edge connects vertices that are in the same set, then that means it would create
a cycle. And otherwise we're going to be adding the
edge to the tree. So then we just do the union operation and
merge the set containing V with the set containing W.
Those are the two things that we need to do and those are the two things that union
find does for us. So this leads to a very compact
implementation of Kruskal's Algorithm. Now to consider the edges in order, we'll
use a, a priority queue, a modern data structure.
So let's take a look the, the every line of this implementation of Kruskal's
algorithm. We are going to have a queue of edges.
That's how we are going to represent the MST.
It could be a stack or bag, but, but we'll use a queue.
And then, the, Cruskill MST algorithm takes a graph.
And it's going to compute the MST in this MST.
And to do that, it's going to use a priority queue, a min priority queue.
A minimum oriented priority queue of edges.
So we'll build that minimum, priority queue.
Now edges are comparable. We had a compare to a method so our, our,
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.