本课程是面向有C语言经验的，并想要学习C++编程的程序员们。涉及到的例子和练习需要有对基础算法和面向对象软件的理解。
4.2 Jarnik-Prim MST
Loading...
來自 University of California, Santa Cruz 的課程
C++ For C Programmers, Part A
480 個評分
從本節課中
Module 4
Prim’s and Kruskal’s algorithms. Use of basic Container Classes. Tripod-Container, Iterator, Algorithm.
與講師見面
Ira PohlProfessor
Computer Science
New topic. we're going to discuss in detail
the Minimum Spanning Tree Algorithm, so the minimum
spanning tree algorithm was actually discovered.
this is found out later, because it was fairly obscure.
It was Czech mathematician named Jarnik, and he wrote a paper where he,
in effect, had this algorithm in 1930. But
engineers and computer scientists attribute the first algorithm that, that
uses this method to Prim, who published and rediscovered the algorithm in
1957. We're going to compare this algorithm to,
a competitor algorithm that was also
discovered roughly at the same time.
by the discrete mathematician, computer scientist, Kruskal.
So I'm going to explain both algorithms, and you'll get a chance to either
implement one or both. They're not completely equivalent.
They're equivalent in the sense that they will give you the right answer,
but in some circumstance, one could be more efficient than the other but.
One doesn't dominate the other completely, and
so it's actually useful to have both implemented.
Prim's algorithm starts with a single vertex.
We could imagine that you pick vertex "a" or.
If you're using a C like notation, you have
vertex zero, you would start with a single vertex.
Look for something that was a minimum weight edge, out of that vertex.
And place it in and build your tree.
So you would start by saying, let's say, we go to node zero.
Look for the minimum weighted edge out of no zero here.
What if there is no edge out of node zero?
No edge out of node zero, then there's no way for
node zero to be connected to the rest of the graph.
If there's no connection to the rest of
the graph, we don't have a minimal spanning tree.
We have what's called.
A disjoint or a disconnected graph.
So I, you should keep that in mind
when you write your algorithm in some instances.
The graphs that you'll be looking at will not have a minimum spanning tree,
and they need to report that somehow.
They need to report that with some other kind of, standard value
like some very large maximum integer, or a sentinel value.
Maybe it would be negative to indicate
that the graph was disconnected, or not a number value.
At any case. It is possible, you have
a graph, doesn't have to be connected, if
it's not connected it won't have a spanning tree.
If it is connected namely any vertex can reach any other vertex or
any node can reach any other node, then there will be a spanning tree.
And if there's a spanning tree there has to be a minimum spanning tree.
So Prim builds the spanning tree. One node at a time,
connecting the node to the existing tree.
So it builds the tree from an existing single component tree.
That's going to be the difference between Prim and Kruskal.
Later on we'll see with Kruskal that it builds the spanning tree potentially by
creating a forest and then as the forest grows out, the forest can
connect
up. And then you end up with one component.
I think the Prim algorithm may be conceptually a little simpler.
Okay, so let's quickly go through how Prim is going to
pick off edges. I'm going to just draw them conceptually
and then keep track of their value. So if the start edge is A.
The start node is "A".
There are basically two places to get to, "E" and "F".
"E" is the
one with the shorter distance. So that means I'm going to go from A to E.
And as we go, we're building a spanning tree.
So we might think of that spanning tree as
the existing, or closed set, much like we built A
shortest path tree (with Dijkstra)
And so we have the existing A, E closed set.
And we're looking for what we can reach so that started with a, a value of 2.
And the thing we can reach now, as we can go to G which is 4, we can go to D
which is 6, we can go to the I which is 4, we can go to the F which is 2.
that two is the best. So, let's pick that
up that gives us a second value of 2, and now we
have we've added F in here,
F gives the some other possibilities. That possibility is after I which is 5
but the best of these is one of the fours. We can pie break
and we can add that 4 in E to G. And,
now we have a new possibility that's
that's actually the lowest value which is 3.
So we would go along G to H, we have H into our
built-up tree, H is 3, we can see that we are
picking things off in what's called the "greedy" manner, I want to point that out.
This is
One of these categories are "greedy" algorithms.
Now, we have G to D, H to D which is 5 but the best is
one of the things we saw earlier H to I which is 4.
And that lets us have an I to D which is also 4, and
now we're done.
We have six edges, we have a full spanning tree and because we did it in this
manner.
Here are all its individual costs and if we add them up we get 4, 8, 11, 15, 19.
So the
total minimum span a tree costs and the
Prim method rises to a spanning tree of 19.
So repeating for Prim, we start at A.
We look for what's the least value edge out of A.
That turned out to be, or we could call it the nearest edge.
That turned out to be E. And then we keep going from what
we built as the set of nodes that are already connected.
We pick the next node
that's not connected to the existing tree.
And we pick the, the smallest edge there, until we
have and minus 1 edges, and then that's our result.
Or until we don't have, we don't have the ability to select any more.
And the, and the graph is disconnected so we can have it disconnected situation.
And you can see from how we've structured it, that there's no way we can get loops.
We never look back into the pre-existent set of nodes that we've already linked.
So, that we, that needs that we'll see in Cresco,
we've to also figure out a way to avoid loops.
We don't want to, even though there might be a small art.
We don't want to end that up with a situation.
Where, if we picked,
you know, something that was 2 here and something that was 3 here and then we can
go on from here or here but this thing was 1, for example.
And let's say this was a minimum, we don't pick this one because these two guys were
already, were already had that, so we don't
look back at the, any of the existing tree.
So we just have to keep track of where we haven't yet gone.
What are the nodes where we haven't yet gone?
If we remember the Dykstra thing, you might call that the Open set.
And Closed set might be
Existing Tree. So we're
[UNKNOWN]
a tree, there's an Existing Tree. And we have to look at nearest
node that's in the open set, that's another way to think of Prim.
Okay, so, now you've seen how to do Prim. You've seen it on
graph that should let you be able to do an arbitrary graph.
But let me give you a little Quiz, just to check your insight on the algorithm.
So, for example, we could have every edge have unit cost, the same cost.
And if there was such a graph where every edge was cost 1, and it had 10
nodes and there was indeed a spanning tree,
what would the minimum spanning tree cost be?
Hopefully you should be able
get that.
And now, you should be able to generalize it.
So, what's the same question if we have an arbitrary sized graph, N?
The graph has N nodes, is connected, has unit cost.
What would its spanning tree cost be? So think about that.
If you remember your mathematical induction you
could even make a proof out of this.
So anything that would have a connected
graph. We would need nine edges in
the ten nodes, therefore nine would be the minimum spanning tree cost.
And then, in general, if we had N nodes, a spanning
tree would have to have N minus 1 edges, and
therefore its cost would have to be N minus 1.
