So now we understand why Kruskal's algorithm is correct, why it always
computes a Minimum cost-spanning Tree. In this video, we'll turn our attention
to implementation issues. We'll begin with a straightforward
implementation of Kruskal's algorithm. That'll give us a polynomial run time
bound which is good but we'd like to do better.
So then we'll show how deploying a suitable data structure, something you
haven't seen before, the Union-Find data structure, allows us to speed up
Kruskal's Algorithm to be competitive with Prim's Algorithm.
That is we'll get a near linear running time bound of MlogN.
So let's just briefly review the very elegant pseudocode for Kruskal's
Algorithm, so it's a greedy algorithm.
It considers the cheapest edges first, all the way up to the most expensive.
So we begin with a sorting pre-processing step to put the edges in sorted order for
notational convenience let's just rename the edges. So, that one is the cheapest
edge, and, all the way up to M being the most expensive edge.
We then have our single linear scan in this for loop, and we just grab edges
whenever we can, okay?
So we maintain this evolving set capital T, which at the end of the algorithm will
be our spanning tree. Now, what forces us to exclude an edge
from this set capital T? Well if it creates a cycle with the edges
was already chosen, obviously that's a no go.
We can't have cycles in our final output, but as long as we don't have a cycle from
including an edge, we go ahead and optimistically include it.
And as we've seen, this is a correct algorithm, it always outputs the minimum
cost spanning tree. So, what would be the running time of
this algorithm? If we just straightforwardly implement
the pseudocode on this slide? Well, let's just considered the algorithm
step by step. In the first step, we sort the edges,
so that's going to take M log N time. Now don't forget whenever we're speaking
about graphs, we have the convention that M denotes the number of edges and N
denotes the number of vertices. So, you might justifiably wonder why I
wrote M log N for the running time of the sorting step instead of M log M, since
after all what it is we're sorting are the edges and there's M of them.
Well, what I'm using here is that, in this context we can switch log N and log
M interchangeably with each other inside a big-O notation.
Why is that true? Well recall when we first discussed
graphs in part one, we noticed that there can't be too many edges.
So the number of edges M, is the most quadratic of the number of vertices,
it's the most big-O of N squared. So if M is at most M squared, then log M
is at most two log N And the two is suppressed in the big-O notation.
So log M and log M are interchangeable in this context.
Notice that for the minimum cost spanning tree problem you may as well assume that
there's no parallel edges. You may as well assume that the graphs
are simple. If you have a bunch of parallel edges
between a given vertices, you can just throw out all but the
cheapest one. That's the only one you'll ever need.
So, moving on to the main loop, pretty obvious how many iterations we have
there. We have M iterations.
So all we need to figure out is how much work we have to do in each iteration.
So what is it each iteration needs to accomplish?
It needs to check, whether or not adding the current edge to the edges we've
already chosen creates a cycle or not. So I claim that can be done in time
linear in the number of vertices. That is it can be done in the big-O of N
time. So how do we accomplish this?
Well, we need two quick observations. First of all, and this is something we've
seen in arguments in the previous videos, checking whether or not this new edge is
going to create a cycle. Say the edge has end points U and V.
Checking for a cycle boils down to checking whether or not there's already a
path between the end points U and V, and the edges capital T that was chosen so
far. If there is a UV path already, adding
this edge will close the loop and create a cycle.
If there currently is no UV path, then adding this edge will not create a cycle.
So the second observation is well, how do we check if there's a path from U to V,
in the edges we've already chosen? Well, we already know how to do that
just. Using graph search.
So you can use breadth for a search, you can use depth for a search.
It doesn't matter. You just start at the vertex U and you
see if you have a reach of V or not. If you reach it, there's a path.
If you don't reach it, there's not a path.
Breadth-first-search, depth-first-search, whatever.
It takes time linear, in the graph that you're searching.
And since we only need to search for the edges that are in capital T.
And there's going to be, at most, N minus one of them.
Linear time in this context means O of N. O of the number of vertices,
because that also bounds the number of edges that might be in capital T.
The edges that we're searching for are pathing.
So, adding up all of this work, what do we have?
We have this sorting pre-processing step. That takes time big-O of M log N,
then we have these M iterations of the four loop like this is takes O of N times
factor. the latter term dominates, so the overall
running time is big-O of M times N. So this, coincidentally, is the same
running time we got from the straightforward implementation of Prim's
algorithm, and I'll make the same comments here.
This is a reasonable running time, it's polynomial on the input size.
It's way better than checking all exponentially many spanning trees that
the graph might have. But we certainly would like to do better.
We'd certainly love to have implementation of Kruskal's algorithm
that gets us to a near linear running time bound, and that's the plan.
How are we going to do it? Well, really the work that we're doing
here over and over again, which is kind of a bummer, is these cycle checks.
And every single iteration, we're spending time linear in the number of
vertices to check for a cycle. And the question is,
can we speed that up? And the Union-Find data structure will
actually, believe it or not, allow us to check for a cycle in constant time.
So if we actually had a data structure that could implement constant time cycle
checks. Then we'd have to spend only constant
time for each iteration of this while loop.
So the loop overall would take only linear time in the number of edges, O of
M edges. If we got that, then believe it or not,
the sorting pre-processing step would become the bottle neck in the running
time of Kruskal's algorithm. Our running time would drop from N times
N down to near linear, down O of N log N.
So let me now tell you a little bit about this magical data structure that's going
to give us constant time cycle checks. I'm just going to give you the high level
picture, and how it connects to Kruskal's algorithm on this slide.
We'll look at the details of the data structure, in the next video.
I also want to warn you that I'm not going to discuss, in this pair of videos,
the state of the art for Union-Find Data Structures.
I'm going to give you a fairly primitive version,
but that is nevertheless, sufficient to give us our desired M Log N running time
of Kruskal's algorithm. So if you're interested, there is some
optional material about different implementations of Union-Find that use
some super cool ideas, like union by rank and path compression.
That give you different, and in some senses, better operation times.
But the quick and dirty version of Union-Find that I'm going to discuss
here, is sufficient for our present needs.
And so the Raison d'être of a Union-Find Data Structure is to maintain a partition
of a set of objects. So in this picture, the overall rectangle
is meant to denote a set of objects and then C1, C2, C3, and C4 are disjointed
subsets that together form the union of the entire set.
So that's what I mean by a partition of a group of objects.
We're not going to ask too much of this data structure.
We're only going to ask it to support two operations.
No prizes to guess what those two operations are called.
So the find operation, we give it an object from this universe and we ask the
data structure to return to us the name of the group to which that object
belongs. So for example, if we handed it something
in the middle of this rectangle, an object, we'd expect it to return to us
the name c3. The union operation by contrast, takes as
input, the names of two groups. And what we want the data structure to do
is to fuse those two groups together. That is, the objects in the first group,
and the objects in the second group should all coalesce, and be, now, in one
sole group. So why might such a data structure be
useful for speeding up Kruskal's Algorithm?
To see the connection, think of Kruskal's algorithm as working conceptually in the
following way. So initially, when the algorithm starts
in the Set capital T is empty, each of the vertices is by it's own,
it's on its own isolated component. And then each time Kruskal's adds a new
edge to the set capital T. What that does is it takes two current
connected components and fuses them into a single connected component.
So for example, toward the end of Kruskal's algorithm that maybe it's
included enough edges, that now the Tree capital T that is constructed so far has
only four different connected components. And maybe it's about to add a new edge U
comma V, where of course U and V should be in different connected components with
respect to the edges chosen for far. So this new edge addition at this
iteration of Kruskal is going to fuse the connecting components of U and V into a
single one. So that corresponds to taking the union
of the groups to which U and V respectively belong.
So to be a little more precise about it. So what are going to be the objects
contained by the Union-Find Data Structure in Kruskal's algorithm?
We're going to correspond to vertices. It's the vertices coalescing that we want
to keep track of. So what are going to be the groups in the
partition that we maintain? They're just going to correspond to
connected components with respect to the edges that Kruskal's algorithm has
already committed to. And with these semantics, it's clear that
every time Kruskal adds a new edge to its set capital T, we have to invoke the
union operation to fuse two connected components into one.