Loading...

4.2 Jarnik-Prim MST

Prim’s and Kruskal’s algorithms. Use of basic Container Classes. Tripod-Container, Iterator, Algorithm.

This course is for experienced C programmers who want to program in C++. The examples and exercises require a basic understanding of algorithms and object-oriented software.

查看授課大綱

您將學習的技能

Graph Theory, C++11, C++, Graph Algorithms

教學方

Ira Pohl
Professor

腳本

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.

推薦視頻

關於 Coursera

Courses, Specializations, and Online Degrees taught by top instructors from the world's best universities and educational institutions.

Join a community of 40 million learners from around the world

Earn a skill-based course certificate to apply your knowledge

Gain confidence in your skills and further your career

Coursera 致力於普及全世界最好的教育，它與全球一流大學和機構合作提供在線課程。

© 2019 Coursera Inc. 保留所有權利。

通過 App Store 下載

通過 Google Play 獲取