- [Instructor] And now we're gonna move on
to the very last topic that we're going to cover.
The last new material that we're gonna have in this course,
which is the minimum spanning tree.
And here in this video, we're gonna present
what's called Prim's algorithm, which is one algorithm
for finding a minimum spanning tree in a graph.
And in a subsequent video, we're going to present
another algorithm called Kruskal's algorithm,
both named after their inventors.
But before we talk about minimum spanning trees,
let's just do a quick review of trees.
So, what is a tree?
You'll recall that a tree is an acyclic,
connected, undirected graph.
Now here's an example of a tree
and let's check its properties.
Is it acyclic?
Yeah, we can see that there are no cycles.
A cycle exists when there's more
than one path connecting any two nodes in a graph.
And here we can see that for each pair of nodes
there is not more than one path connecting them.
In fact, there's exactly one path.
It's a property of a tree.
Is it connected?
Yep, for each pair of nodes in the graph,
there is some path that connects them.
So we have a tree and not a forest.
Is it undirected?
Yes, the edges are undirected,
and so this graph has all the properties of a tree.
Here are some counterexamples.
We can see on the left here, this is not acyclic
because we have a cycle here, so that's not a tree.
This is not connected
because we have this disconnected node here, b.
It's a perfectly fine forest because a, c, d
and h form a valid tree and b by itself,
a single node I should say, is also a perfectly fine tree.
So this is a forest, but not a tree.
And this graph is directed and so not a tree.
Some people might quibble with that last one
but that's the way we're gonna roll.
Another reminder here is that if we have a tree on n nodes,
it's gonna have exactly n minus one edges.
It's gotta have exactly n minus one edges.
If it has fewer than n minus one edges,
then it's not connected, some edge is missing.
And if it has n or more edges, then it has to have a cycle.
For example, if we look at this tree here,
there is no way we can add another edge.
We have one, two, three, four, five nodes
and we have one, two, three, four, n minus one edges.
If we add any edge, anywhere else in this graph,
we're gonna create a cycle,
we have to, ch, cb, bd, ah, dh, they'll all form cycles.
So, if we have a tree on n nodes,
it's gonna have exactly n minus one edges.
So now we can move on to the topic
of what is a spanning tree.
We'll do that before we get to a minimum spanning tree.
So, given some graph like we have here,
we have this graph that is node set, V and an edge set, E.
We say a spanning tree of the graph
consists of the node set, the node set is the same.
And some subset of the edge set, we'll call it E prime,
such that we have a spanning tree.
So, what does that look like?
So here we have the starting graph here G,
is the node set and the edge set.
And we have this spanning tree we call G prime,
which has exactly the same node set
but it has a different edge set,
but the edge set is a subset of the edges in this graph.
And we wanna pick a subset of the edges,
such that every node is incident to some edge
and the edges themselves, you know, form a tree.
So this is a spanning tree of this graph.
The tree touches every node in the graph,
that's what it means to span.
There may be more than one spanning tree in a graph.
As a matter of fact, there will be more
than one spanning tree in a graph.
So, here's another perfectly good spanning tree.
Again, we have G prime, the spanning tree,
which is has the same node set as the original graph
but it has a subset of the edges that form a tree
such that all of the nodes are connected.
There's exactly one path between every pair of nodes.
And so that's another spanning tree.
Now you've probably figured out
where we are heading with this.
What if the graph G is weighted?
Well, finding a minimum spanning tree
is the problem of finding a spanning tree
with the sum of the weights minimized.
So given this graph with this node set and this edge set
and the edges are weighted,
we wanna find this spanning tree, G prime,
with the same node set and this edge set, which is a subset
of the original sets such that G prime is a tree.
And we minimize, argmin just means we're just trying
to minimize this big, old sum here.
We've got a sum of all the weights
for every u,v in this edge set we sum the weight
that corresponds to that edge.
And we wanna find the set of edges that minimizes this sum.
So, that's a minimum spanning tree.
Here's a minimum spanning tree, okay?
And this, the sum here of all of these edge weights is 12.
And that's the subset of edges
that yields the smallest possible sum.
Maybe we can't swap any edge, for example,
here's this one with weight three.
If we swap it for this one to connect b to h,
we'll get a sum of 13, so we can't do that.
There's no edge that we can substitute in
that would give us a lower sum.
So this is a minimum spanning tree.
But what are some applications of minimum spanning trees?
Well, there are lots of them.
They're used in telecommunications, in taxonomy
and phylogeny, computer networks, electronic circuit design,
computer vision, process control, any situation
where we have a network and we wanna find
the smallest weight or smallest distance tree
that touches every point in the network.
I'm gonna start the discussion
of Prim's algorithm with the pseudocode.
So here we have this function, prims
and it takes in this graph which we call G.
And we start by initializing this subset of edges
that we've called E prime to an empty set.
And then we can pick any starting node, S, in the node set.
And we have this node set here, V prime, which we will build
until it is the same as the original V here
but we'll start that off with this randomly chosen node
as the starting node.
It doesn't matter which node we pick,
every node is gonna have to be touched by an edge
so we can start at any point.
But as long as the cardinality of this node set here
for the graph that we're building,
the minimum spanning tree that we're building
is less than the cardinality of the node set
of the underlying graph, we keep doing something.
What is it that we keep doing?
Well, we find the minimum weight edge
with exactly one endpoint in this set, V prime.
We add this edge to E prime.
And then we add the endpoint of E
that's not already in V prime to V prime.
And we do that until these two numbers are equal.
And then we return and we returned with the node set
which is going to be identical
to the input graph and this subset of edges.
So, let's walk through that and see how that works.
So, here is a graph and we're gonna perform Prim's algorithm
on this graph.
And we have the graph consists of this node set a, b, c,
d, j and h, and this edge set ab, ac, ah, and so on.
And we start with these sets initialized to the empty set.
And the first thing we're gonna do
is we're gonna pick a node at random
and we're gonna add that to V prime.
Okay, so we've added a to V prime.
I could have chosen any node, it doesn't matter,
but we just chose a.
Then what we're gonna do is we're gonna find
the minimum weight edge that has exactly one endpoint
in V prime.
So what's the minimum weight edge
that has exactly one end point in V prime?
Well, it's this one right here.
This one, this weight is two.
So what we're gonna do is we're gonna add this edge
and this node, so let's see how that works.
There's the edge and so we add the edge ac to E prime,
that's our subset of edges that will form our spanning tree.
And we add c two V prime, okay?
That's our first step.
Now we do this again.
We ask ourselves, okay, here's the new V prime.
What is the smallest weight edge
that has exactly one end point in V prime?
And again, here, we can find this one here is three,
this one here is four, nine, seven, eight.
It's gotta be this one, right?
So, at the next step, we add the edge cj to E prime
and we add j to V prime.
And then we do it again, because, you notice the cardinality
of V prime hasn't reached the cardinality of V yet.
So, what now?
If this is our new V prime,
these three nodes here, what is the smallest weight edge
that has exactly one end point in V prime?
Well, this one here, okay?
So we're gonna add that.
So now b is added to V prime, the edge ab is added to E.
Remember how I said that a tree on n nodes
has exactly n minus one edges,
it's should come as no surprise
that as we're building this for whatever n we have
in V prime, we're always gonna have n minus one edges here.
So I just wanna make that observation.
Then we iterate again,
what's the next edge that we add?
The smallest weight edge
that has exactly one endpoint in V prime.
It's this one here, this edge bd.
And so we add that one, we add bd to E prime,
we add d to V prime, and we have one more edge to find
because we're missing one node in this node set.
And so we find, again, this is gonna be
the smallest weight edge
that has exactly one endpoint in V prime.
And so we add that to V prime,
we add the edge to E prime and now the cardinality
of these two sets is the same.
And that's our condition for exiting that while loop.
And so the algorithm terminates yielding this V prime
which node is exactly the same set
as the original V and this subset of edges.
So that's finding a minimum spanning tree
by Prim's algorithm.
Now, it might be the case that we have more
than one minimum spanning tree for a given graph.
Here these two trees have exactly the same weight,
so we're not guaranteed to find
a particular minimum spanning tree,
we're just guaranteed to find a minimum spanning tree.
And how does that work?
Well, if you take a look here
and we say the green colored nodes are our V prime
and we're looking for the minimum weight edge
that has exactly one endpoint in V prime,
we're gonna find these two edges.
These both have a weight of three.
And so we could add either one to our minimum spanning tree,
it doesn't matter.
And so in the case of the algorithm,
there might be some order that's already present
in the underlying data, or we could toss a coin,
it doesn't matter.
We're gonna pick one or the other.
But if we pick this one,
then we gonna get one minimum spanning tree.
And if we pick this one, we're gonna get
a different minimum spanning tree.
So if we pick this one, we're gonna get one tree.
If we pick this one, we're gonna get another.
And that's why Prim's algorithm doesn't guarantee
that it's gonna find a particular minimum standing tree,
just a minimum spanning tree.
So, let's get more into the details
of how this algorithm works in practice.
I've done a lot of hand wavy stuff about looking
for the edge with exactly one end point in V prime
that has the smallest weight,
but how do we actually do that in practice?
And so here, we've got this graph
and we're gonna do Prim's algorithm
with a little more detail looking under the hood.
And here we have, does anybody remember what this is called?
This is an adjacency matrix.
And why haven't we included the lower left triangle?
Because this is an undirected graph.
And so this is just gonna be a mirror image over here.
So the only information that we need to keep track of
is what's in this upper triangle here.
And we also have this auxiliary table.
So what's going on here?
Well, let me show you how this works.
We're gonna run Prim's algorithm now.
We're gonna pick b this time again,
I could choose any node, it doesn't matter,
but we'll pick b just for variety's sake.
And let's see what happens.
So we've chosen b and whenever we add a node to V prime,
see b is in V prime now, we update this table.
And for each node not in V prime, we keep track of the node
in V prime connected by the lowest weight edge
and we store that weight.
So here, b is the only node in V prime
and we have the lowest weight neighbor
and the edge weight for all other nodes adjacent to b.
So, for example, we have a, it has a weight of two,
b, we don't include, there's no self loop to b,
so that's off the table.
We have, c, let's see, c the smallest
weight edge here is seven.
There's only one right now.
For d, we have this connection to b,
which has a weight of three.
J we can't get to b yet, there is no connection
from j to V prime yet.
'Cause j is only connected to c, a, d and h.
So one of those nodes would have to be in V prime
for j to be connected to it.
So we have no entry for j
and then we have this entry for h, which is this entry.
That's how this table works.
And we update that every time we add a new node to V prime.
We can see from this table here
that we could choose either of two edges for our next step.
We could add either this edge here or this edge here.
And we just know that by looking in this table
and finding the minimum weight,
and we find two with the minimum weight.
And it doesn't matter which we pick.
So let's pick a, right?
So we're gonna pick a.
So now we've added this edge ab into E prime.
Let's add a, and so now we need to update this table
on the right.
And now a and b are both in V prime.
So we update the values that we need to update.
And the only one that we need to update
is this one here highlighted in yellow.
Since we now have a lower weight edge into V prime,
which is ac, which this one here.
We had this one here, which was of weight seven,
but now that we've added a to V prime,
now we have this other lower weight edge,
which is represented here.
And so we update that table on the right.
So now we have a four here where before we had c seven.
So, next step, do the same thing again.
What's the lowest weight edge into V prime?
It's this one here with weight two, that's this edge here.
So we're gonna add that edge.
And now we add h to V prime
and now we need to update that table.
So we're gonna find that this needs
to be updated now, all right?
And so the entry for c doesn't change
but the entry for d does change from b
with weight three to h with weight two here.
So we no longer need the entry for h,
so we'll just erase that.
You wouldn't erase it in practice but for the demonstration,
it's easier to read table if we exclude values
that are no longer needed.
So what's next?
The table tells us to add d.
So, that's the minimum weight in the table.
We add d, we add this edge dh to E prime.
We add d to V prime, and now we need to update the table.
Now the entry for c needs to change.
It was a with a weight of four
and now it becomes d with a weight of two, okay?
So, we update the table.
And we don't need the entry for d anymore,
so we can kill that.
The entry for j is unchanged,
so we see now that the next choice is c
that has the, this edge here.
No, that's not right.
That's this edge here, my mistake, okay?
So this is the edge from c to d, has a weight of two.
So we're gonna add that.
We add the edge cd to E prime.
We add c to V prime, and now we update the table.
We no longer need this entry,
so we can delete that or just strike it out.
And the entry for j is unchanged, this doesn't change.
There's no lower weight.
So we're just gonna leave it as it is.
And so now we only have one choice,
it's easy to finish up.
We choose this edge that is weight three, connecting j to a
and we add the edge and we add j to V, and now we're done.
And so there's our minimum spanning tree.
And so this is one way of implementing Prim's algorithm
in a little more detail.
So, is Prim's algorithm greedy?
Yes, it is greedy, okay?
Because it's always finding the minimum weight edge
and adding it and it never goes back
and reconsiders that edge.
Once it goes into the solution, it's there for good.
So that's a greedy algorithm.
What's the worst case complexity?
Well, it's big O of the cardinality of V squared.
We have V minus one edges that we need to add.
And in the inner loop, we have to iterate
through all the nodes not in V prime
to recalculate the lowest weight edges to V prime.
So yeah, that number gets smaller as we iterate
but we're still talking on the order of big O
of the cardinality of V squared.
That is, of course, if we use the adjacency matrix.
There is an implementation using min heap for fetching
the lowest weight edges.
And if we use min heap,
then we get a runtime complexity of big O of E times log
of the cardinality of V, and this is a mistake.
This should say cardinality of E, forgive me.
So, the adjacency matrix is best
if the graph is dense, if there are a lot of edges.
If there's a high ratio of the edges to the nodes.
And the min heap is best if the graph is sparse,
that's when there's a low ratio of edges to nodes.
But either one will work and they produce similar results.
So that's Prim's algorithm
for finding the minimum spanning tree in a graph.
And in the next video, we'll look at alternative approach
called Kruskal's algorithm.
That's all for now.