- [Instructor] All right, Kruskal's algorithm.
In an earlier video, we saw Prim's algorithm,
which is designed to find a minimum spanning tree
in a connected graph.
And we had a little reminder
about trees and graphs and things like that.
And in this video,
we're gonna look at Kruskal's algorithm,
which solves the same problem as Prim's,
finding the minimum spanning tree in a graph,
but it does it with a completely different approach.
So before we dive in,
let's just again remind ourselves
what is a minimum spanning tree?
Let's say we have some graph here on some nodes,
the node set given by V and the edge set given by E.
And we have weights on all of these edges.
These are weighted edges.
And we want to find a minimum spanning tree.
That's a tree that touches each one of the nodes.
We call this minimum spanning tree G prime.
It's gonna have exactly the same node set.
It's gonna have a different edge set we call E prime,
where E prime is a subset of the edges
in the underlying graph.
We want G prime to be a tree.
It's gotta be a spanning tree, right?
And we want to minimize this sum.
This sum is the sum of all of the weights
of all of the edges in E prime.
So for E prime here, for every u, v in E prime,
we add the weight, that's our sum.
So we wanna find the minimum of those.
So that's a minimum spanning tree.
And again, in the previous video,
we saw this example of this minimum spanning tree
on this graph here,
where the sum of the edges in E prime was equal to 12,
which is the smallest possible weight edges
that we can find that spans all of G.
So that's a minimum spanning tree.
So what does Kruskal's algorithm do?
Well, Kruskal's algorithm works differently than Prim's.
And what we do is we take a list of all of the edges,
we have that edge set, and we order them.
We just notice that this is now a sorted list of edges.
Bh has weight two,
that's the smallest weight edge in this graph here.
And ah, which is this one here, has a weight of nine.
That's the largest weight edge.
And so these just go from the smallest weight edge
to the largest weight edge.
And then what we do,
what we did in Prim's algorithm is we picked a node
and we said now let's find the minimum weight edge
that connects us to this subset of nodes V prime.
We're gonna do this differently.
We're simply gonna take the minimum weight edge here
and we're gonna add that to our minimum spanning tree.
And we're just gonna keep doing that.
We're gonna throw out edges that form cycles.
So if a cycle is formed, we're just gonna toss that edge,
and we're gonna move on to the next one.
And we're just going to do that
until we either exhaust all the edges.
Maybe the last one is the last one we add.
Or we have a set of edges
that touches every node in the graph,
and that's Kruskal's algorithm.
It's really, really simple.
It's a very elegant algorithm.
But it does mean that we have to check
to see if there are cycles formed
and throw out the edges that cause cycles.
So again, the first one we add is this one bh,
cause it's the first one in our list.
We gray that out to show that that's no longer available.
We check aj, can we add aj?
Yeah, sure, we can add aj.
Does it form a cycle?
No, it doesn't form a cycle.
So we're good.
Now bc, that's the next one on the list.
Can we add that?
Yeah, sure.
It doesn't form a cycle. We're safe.
Now the next one on the list is ac, can we add ac?
Yup, doesn't form a cycle.
Next one on the list is dh.
Dh, that's this one here.
Can we add that?
Sure, we can add that.
That doesn't add a cycle.
And now we have a minimum spanning tree.
Now that was a little bit of a contrived example
so that we didn't encounter any cycles.
But it gives you an idea.
Let's do a different example where we have some cycles.
We have to throw out some edges.
So here again, we have a different graph, same idea though.
We have a collection of nodes
and we have a collection of weighted edges
and we sort the edges by their edge weight.
And notice now before we run from two to nine,
and here we have a whole bunch of conflicts here.
So that's gonna make this run through the algorithm
a little more interesting.
So we start with the minimum weight edge here.
We could pick any of them,
but we'll pick this one, ac,
and we add that to our minimum spanning tree.
And then we check the next one is ad.
So can we add that?
Yeah, sure, we can add that, that's fine.
Now ch, ch is this one here.
Yeah, that's safe to add.
So we'll add that one.
Now, oh, we got a problem.
Dh, dh is the next one on the list.
But if we were to add dh, that would create a cycle,
and we wouldn't have a tree anymore.
So we're just gonna throw that one out.
We're gonna chuck it, cross it off the list.
Now what's the next one?
Aj, aj that looks like that's safe to add.
So we'll add that one to our minimum spanning tree
and we're getting close to the end here.
What's next? Dj.
Dj, oops, that forms a cycle.
See, that would form this cycle here.
So we gotta throw that one out.
So we'll throw that one out.
And now what's next on list?
Cd, cd, that would form a cycle.
See this one, this would form a cycle here like this.
So we can't use cd.
So we throw cd up.
What's next on our list?
Bh, well, we can add bh.
That's safe.
It doesn't create a cycle.
And so now we've completed our minimum spanning tree.
There's an edge incident to every node in the graph.
And we found a subset of edges that has a minimum weight.
And I don't know about you,
but I think that's a pretty cool algorithm.
It's very simple in concept.
So here's some pseudocode.
We start off.
This is our function kruskals
and it takes G as a parameter.
And we initialize our edge set E prime to the empty set.
And then we take a little extra time.
We sort the edges in V,
and we can use a sorting algorithm and sort a vector
or we can pop them into a min heap
and let the min heap do the work for us, either is fine.
And then as long as the size of this edge set E prime
is less than the number of edges that we need,
that's the cardinality of V minus one.
If the next edge in the sort or the heap
does not create a cycle,
we add this edge to E prime and that's our while loop.
And as soon as we hit the condition
where the cardinality V prime equals
the cardinality of V minus one,
we know we're done and we return
and we return the node set
and the subset of the starting edge set E prime.
And that's it.
That's all there is to it.
Now you may have noticed that I kind of swept
a little detail under the rug.
And what is that detail?
The detail is how do we know that we formed a cycle?
Well, this is where the study
of algorithms gets really interesting
as far as I'm concerned,
because we can combine things that we've learned already.
And there's a data structure and a procedure
that makes this almost work like magic,
and that's using disjoint sets find and union.
So how does this work?
We have, again, this is a revised pseudocode.
We have Kruskal's takes in G,
and we're gonna do this using disjoint sets find and union.
And so we let E prime equals the empty set.
And again we sort the edges in E.
we can use a sorted vector or min heap.
We make singleton sets out of all of the nodes in V.
Remember that's how disjoint sets find and union works.
We start off with singleton sets,
and then we take the union of sets as we connect components.
And so for each edge in E,
if find u not equal find v,
this is how we're detecting
whether there's gonna be a cycle formed.
If this query returns false,
then we know that u and v are in the same set already.
And if we add an edge between them, we'll create a cycle.
So only in the event that find u not equals find v,
we add the edge to E prime.
So that gets added here.
We take the union u and v.
And we just keep doing that.
You know what?
This should be indented.
I'm gonna fix that right here on the front.
Oh, no, I'm gonna fix that here.
Sorry, I bet.
So for each edge u, v in E, we do this check.
If this turns out to be true,
then we add the edge, we take the union,
and then we just keep exploring our edges.
And that is a very elegant, I think,
that's a very elegant way of solving this problem,
where we use disjoint sets, we use a min heap,
and we get a minimum spanning tree
in just the fewest lines of pseudocode here.
And implementing this in C++ or Java or Python
or any other language is just dead simple.
So the question, is it greedy?
Yup, it's greedy, why?
Because we grab the edge that we can add
without forming a cycle.
And we never reconsider that edge.
We never take it out.
Once make that decision, we've glommed onto it, we're done.
What is the worst case complexity here?
Well, the worst case complexity is big O
of the cardinality of the edge set times the log
of the cardinality of that edge set,
and that's presuming that we're going to use min heap.
The biggest cost is in sorting the edges by the weights.
And so that's the most costly part.
So if we use min heap to order everything
and then just pop them off the heap,
that gives us a big O of the cardinality
of the edge set times the log of the cardinality
of the edge set.
And that, my friends, is Kruskal's algorithm.
And I think that's a really cool algorithm.
So this concludes our discussion of minimum spanning trees.
And this is the last topic we're formally going to cover
in these video lectures.
So everything else is going to be posted on the discussions
and the review questions that we have for the final exam
in their own section on Blackboard.
So that's all for now. Thanks. Bye bye.