本课程是面向有C语言经验的，并想要学习C++编程的程序员们。涉及到的例子和练习需要有对基础算法和面向对象软件的理解。

Loading...

來自 University of California, Santa Cruz 的課程

C++ For C Programmers, Part A

572 個評分

本课程是面向有C语言经验的，并想要学习C++编程的程序员们。涉及到的例子和练习需要有对基础算法和面向对象软件的理解。

從本節課中

Module 3

Point: Default constructor and initializing syntax. Conversion Constructors. Copy Constructor. List and dynamic memory allocation. Deep Copy.

- Ira PohlProfessor

Computer Science

Okay, so, while I'm assigning you a

homework problem that's Dijkstra's shortest path algorithm.

I'm going to show you the process of

handling the is-connected problem, they're related.

To some extent you could, in fact, uses Dijkstra's shortest path algorithm.

And it's in one form to find whether a graph is-connected or not.

But the simpler one should give you ideas about how to do the Dijkstra's algorithm.

And this goes back to my own work.

Back in 1968 when I was a research graduate

student research assistant at the Stanford Linear Accelerator Center.

And I was being asked to use this very new programming language called

PL1, which is more or less out of favor now but still available.

And the interesting

thing about PL1 was, it was an attempt to get a universal programming language.

PL1 was supposed to IBM's ability to

having to do away with special purpose languages.

And IBM was finding that it was, it wanted

to be a hardware company, not a software company.

It wanted to sell big machines, which generally filled

up lots of space, and cost lots of money.

And software was an, an irritating expense.

So, the fact that they had

to provide machine language comp compilers, macro

preprocessors, COBOL compilers, FORTRAN compilers, sometimes Algol compilers.

That was just a lot of different software they were supporting and they just

felt, well, why can't we get a

universal language, and that will simplify our tasks.

And they tried. And the way

they tried was unfortunately what I call, the kitchen sink approach.

They took everything they had, in all these different languages, threw them all

together There was a lot of redundancy in, in this language.

You could do things in a COBOL manner or Fortran manner.

There wasn't an obvious PL 1 manner to do things.

And that's in a way why PL 1 didn't survive the object oriented revolution.

Object orientation allows you to have a much simpler idea

of what a kernel language is, in our case C.

And, then expanded by letting the programmer add

classes, whenever they needed, yet, a new domain.

A new set of widgets to work with. Now,

the algorithm I'm going to describe goes back to work that

I did and was documented in some reports at SLAC.

But later it was generalized in a very important way by Tarjan

and Hopcroft, and it's a foundational algorithm called breadth-first search.

And you can certainly read about that.

So this is also a vital algorithm that you should be

familiar with, Breadth First Search and you can find it in the Wikipedia.

And

what we're going to do in trying to find out whether

a graph, is connected is we're going to start arbitrarily with some node.

And since everything in C starts at zero, and we'll probably use the labeling system

that says we'll have node zero up to node n minus onee or up to node size minus one.

We will assume that node

zero Think of our map before, San Francisco.

If I'm sitting in San Francisco, I've reached San Francisco.

So San Francisco is automatically connected to San Francisco.

So we're going to have this initial set, and

in that intital set we'll put the node zero.

Then we will look from San Fransiciso and see where

are the next, where are the adjacent cities we can reach.

And this will be what I will call a closed set.

And then waht I'm going to call an open

set, I'm going to put nodes reachable from San Francisco.

So if I could reach node three and node seven,

those will be nodes in the open set.

Now, what if there was no way out of San Francisco?

maybe there's been a huge earthquake and all roads have been busted.

What does that mean? It means the graph is disconnected.

I can't get from San Francisco to San Diego.

I could stop.

So, if I have a closed set automatically with a starting node, and if there's no

edges out, well, then the algorhythm will stop

and report that the graph is not connected.

However, if there are ways to get out of San Francisco, namely I can go

to Los Angeles or San Jose, as was in that early map I showed you.

Those nodes with

their names would go into the open set.

And then each time I would go to the open set and pick off a next node.

Maybe in my algorithm, I pick the node with the lowest number.

Take that node and drag it over.

Place it in the closed set, and look again for what places I can go from node three.

And maybe I can go to node four and node two.

And they would become new entries in the open set.

So, the open set would contain those that can

be reached from what was put in the closed set

with the provisio that I don't need

to go back to something in the closed set.

If there's another way to get back to San Francisco, that's not of interest.

So the open set will only have,

nodes that are not in the closed set.

The calculation will stop, when one of two things happen.

Either, (futer - was further -sic) and this is important

Either I can't reach all the nodes, in which case, the open set

is exhausted, and the closed set has yet to contain size

n nodes, all the nodes in the map. So I'm not connected.

Or all the nodes, the set of nodes, that are now in the closed set,

are, in fact, there are size of them.

And then we can stop and

the graph is connected.

So that's our algorithm. That's what we're going to implement.

We go back and we have our matrix

representation of the graph,

we have it as a Boolean matrix's

representation. We have the size

of a graph and we are going to keep

track of closed and open. And here is where open of zero is true.

That's like saying San Francisco is originally in

the open set and it"ll be the first, since it will be the only thing in the open set.

It'll get automatically selected, placed in the closed set.

So, at this point, the open set has node zero on it.

It could work if any other node is

placed in it, but there's nothing special about zero.

To determine whether the graph is connected or not.

Nothing is yet in the closed set, and each

iteration will add one node to the closed set and

possibly many nodes to the open set, or maybe not.

The open set doesn't get added to.

We're still going to the open set each time as long as there are entries

in the open set, and we've yet not worked out whether the graph is connected.

So add (to) the closed while the, I'm keeping track of

C_size. This is size of the closed set.

The

old size is the C_size.

We then place something in the closed set, meaning.

One element is placed in the closed set, so we ought to increment it.

The closed set has that element being true.

And then, we go and look for things in the open set.

And we got to put into the open set anything that's already in

the open set that stays in the open set or anything that's newly reachable.

Recall this is

just our note this is true if an

edge (i,j)

in the graph and this just logical or.

So, this is the logical or operation.

So, open is true, if open is already true, or.

There is now a new edge that previously couldn't reach j, but now reaches j.

We are done if we have all the nodes in the

closed set, or if no nodes are available in the open set.

If all the here connected, we're connected.

Here we're unconnected, and these are our termination cases.

And keep in mind, how many iterations are we going to do?

We're going to do no more iterations than size.

because, in size, we either get a new node, or we fail.

And if we fail, before then, we fail before size.

And if we keep getting a new node, we get everything up to

San Diego and we're finished so we only have to do this the size of the graph.

So the fairly straight forward algorithm.

Okay.

So, I'm going to explain a lot more about Dijkstra's algorithm, how to

implement it, how to do your homework and that'll be in our next lecture.