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.
4.1 MST
Loading...
From the course by University of California, Santa Cruz
C++ For C Programmers, Part A
391 ratings
From the lesson
Module 4
Prim’s and Kruskal’s algorithms. Use of basic Container Classes. Tripod-Container, Iterator, Algorithm.
Meet the Instructors
Ira PohlProfessor
Computer Science
[MUSIC]
So we're on a new topic.
Everybody should've completed the Dijkstra's Algorithm which was
our second assignment and really our first major
assignment. so you should have a fair familiarity
without how to process graphs. The notion of turning a
graph into a class structure, an abstract data type,
to getting a lot of benefit from using graphs which are
very, very useful throughout algorithms computer science study, and again,
hopefully for most of you, all of this is review, so we're
using material you should've already learned.
and isn't novel, but if it isn't review or you've forgot a lot of it.
There're excellent articles especially on the Wikipedia on all these
algorithms on the basic graph theory including the
algorithmic graph theory behind things like Dijkstra's algorithm.
Today's algorithm, which we're going to talk about and
will be the basis for the next homework assignment.
So it builds on Dijkstra, so in some sense, it should be easier because now
you've, you've you're past the jitters. You've gotten your,
your programming legs in terms of this complicated aggregate,
and you're just going to add a new algorithm.
And the whole course is structured to build algorithm by algorithm.
Towards the end of the course, we're hoping you're going to all be able to
implement this very interesting game, hex, which can also be
represented largely as a graph.
So, today the main topic is minimum spanning trees, basis
for homework three, and we're also going to study again, object orientation.
How important object orientation is. When we use a language, like C++,
what are the ideas, we bring to the table, to do good C++
programming? C++ is way more than an object-oriented
language. It's got multiple tools in its, in its
bag and it has the ability to do generic programming and it
has the ability actually, to do functional programming
in terms of C++ 11.
So it's multi-paradigmatic, C++ is multi-paradigmatic.
But, a really great strength. And the thing that
has it replacing C was the shift
from ordinary imperative programming that was C.
To encapsulation-based on the object-oriented paradigm.
And we'll see that with, a very
simple but, very useful example called class point.
So, homework three.
You've already built the graph abstract data type.
you hopefully got the Dijkstra algorithm to work.
You got it to work on automatically
generated, graph based on densities and size.
You computed an average length in such a graph.
Saw how all of that could work. And we're going to add this next
major algorithm, again extremely useful. Minimum spanning tree comes up.
In many, many areas in computer science and electrical engineering.
In some sense it's maybe at the heart of
the Internet, the way the Internet works, one wants
to have a minimum spanning tree so that from
particular foci you can get your messages, packets whatever
out to arbitrary other foci.
Minimum spanning tree, a definition. So again, we're going to have a
graph in which an edge has some arbitrary positive cost, an edge.
So we might have
an edge from a to b. With, let's say, cost seven.
And
we have a whole graph built of edges with costs.
First off, we have to know what a spanning tree is.
A spanning tree is just a set of edges, that in effect is a tree.
Remember we, in computer science
frequently use things called, binary trees.
Binary trees would be spanning trees of graphs if the graph
had inside it, a binary tree. So a spanning tree is a set
of edges within the graph that connects all the nodes of the
graph, and where there is no cycles. So an immediate
implication of that is if we have a graph of
n-nodes, a spanning tree is a tree
with
n minus 1 edges. Now,
I'm also going to, in
this homework problem,
assume that edges in the spanning tree can have different colors.
It's going to make it a little more sophisticated and it'll
add to some of the ideas in how you learn C++ programming.
It'll enable you to use, an enum type, or a class enum type.
that, class enum type is yet another novel idea in C++ 11.
So if you have a C++11 compiler we may talk a little bit about a class enum
type, as opposed to the earlier, pure enum type, which remains.
and so we can assume that an edge
can be red. There can be red edges.
There can be blue edges.
There can be green edges. And we might, when
we specify our minimum spanning tree problem, decide on well do
we want a minimum spanning tree in which all the edges are green?
Green and MST?
Or maybe we would have blue
and red and MST.
So for the same graph in which they were colors, we
could have multiple answers to the minimum spanning trees.
So as they say, it just makes the problem a little bit non-standard,
not as easy to copy the code off the internet, adds a little flavor to it.
And actually it'll be a flavor that will
be useful in many later and more complicated venues.
So first let's take a little quiz. If we
have a enumerated type, here's a simple enumerated type, color.
This is different than as I say C++ 11 will have a
class enumerated type. Why were the colors capitalized?
The enumerators have internal values, in this case
what would be the value of green? And if we wanted, and this is a new type.
So again, object orientation is all about adding
types to the basic native types in a
way that, is compatible with the basic native
types, and fulfills the expectation of the C++ community.
And the expectation in the C++ community is
that the IO, the, what you might call pseudo-operators, the, the
operators adopted to in this case, the bit shift operators.
Adapted so that they do IO. can be overloaded.
How would we overload to print red?
So take a few minutes and see how you'd answer those questions.
Well, first off, the reason that we use capital is just a community convention.
So whenever we have things that we think of as constants.
This even goes back to the old C style where when
we didn't have a enumerators, we just did this using macros.
So the minute we see in our C code some big cap,
all caps identifier, we think that must be some
kind of standard constant. In this case,
the values go sequentially 0, 1, and 2, so green
ends up two, and then if we were
to implement the code for overloading the operator,
recall that it has a certain idiomatic format.
We're always going to call
by reference,this complex construct, the ostream.
We call the new type that we want to overload.
And then we're going to return. What do we return here?
Everybody should know that should be return of out.
Why is that again? So that we could properly use C out,
something.
And that in effect,
these are expressions that evaluate to the same ostream so that
you can use that output
repeatedly. Here's some new
novel stuff fresh from the new standard. They are
what we call strongly typed enumerators, enum classes.
We're going to see why we need them. Let's say in the old
style I could've had enum color. And enum traffic.
And then I'd have two specific uses of red as enumerators.
And they can actually get confused because they weren't strongly typed.
In essence,
some kind of integer and they would be comparable if I wanted to.
However, when I turn them into this newly,
strongly typed enum, and that happens by, instead
of just calling an enum, I'm calling them enum class, so it looks somewhat the same.
Except now I have class.
Now, the two enumerators are distinct. They're not comparable.
They're not.
They have type distinction. Since they have type distinction.
They're much safer in code.
We can't get into trouble with conversion opportunities for example.
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2018 Coursera Inc. All rights reserved.
