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

Loading...

来自 University of California, Santa Cruz 的课程

C++ For C Programmers, Part A

457 个评分

本课程是面向有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

So, part of what the course is going to give you expertise in

is algorithmic graph theory, because it's a very, very good subject,

because graphs themselves are widgets, complicated widgets.

That have very different representations in many

ways to try and implement and get efficient

for particular different instances.

And so, we can see a lot of the old ideas and a lot of the uses of C++ effectively.

When we try to implement these algorithms in C++.

But also it gives you some background in doing further

and more complicated programs as this course (...)

progresses.

And one of the classical algorithms in computational, graph theory was invented

by the very famous Dutch mathematician and computer scientist Edsger Dijkstra.

So we're going to see how to use Dijkstra's algorithm and your homework is

going to be to implement Dijkstra's algorithm

and use it on a randomly generated

graph, which you'll also have to implement.

We'll also show you how to do a very similar but simpler

problem based on an algorithm that I invented many, many years ago.

Originally I implemented it in a much earlier programming language call PL-1.

And it's the problem of finding out whether a graph is a simple

connected component graph. And we're also

going to add some drawing lessons. We're going to be drawing

graphs as we go through and simulate these algorithms.

So this is the set of ideas we're going to need, to do the remaining homework.

in this class. So here's an unconnected graph and

that unconnected graph

is a graph of seven nodes. We might label

these nodes 0, 1, 2, 3, 4, 5, 6.

That would be traditional C labelling, namely we start from zero.

We might label these nodes, A, B, C, D. You'll see all these

labellings in the graph literature or might see them

as nodes on graph, maybe this is San Francisco.

And this is Los Angeles.

All of these are possible.

So I'm unconnected because we can't go from any node to any other node.

There's, we don't see any path.

Between, in this unconnected graph, between San Fransisco and Los Angeles.

We just see nodes.

Now, here's what we're going to show as a connected graph.

So I have left the

same labelling and now I'm going to add what are called edges.

So these blue lines are what we call as edges.

The little circles are nodes.

The little blue lines are edges. When you think of edges, think of roads.

So here's a road from San Francisco, going to Los Angeles.

For us who are Californians, that might be 101.

here's another road, from San Francisco to D.

Maybe D is San Jose.

Maybe this is San Diego. So

again, you have familiarity in the, in the ordinary world

with graphs. They're basically just road maps.

And they're road maps in which the cities are nodes and the highways are edges.

Now,

I'll draw a few more edges. If you looked at this connected graph.

The reason it's connected, is, I can find a path between any 2 of the cities.

And 2 of these nodes. Or, another term for nodes is vertices.

So if I want a path from San Francisco to San Diego, I'll use

this little wiggly line and show you here. Oh, there's a path.

So that whole graph is connected and indeed a single component.

Now, how can I get a computer to draw a graph?

Drawing a graph by computer is actually fairly efficient and the critical thing

will be to generate using a representation for the graph, an internal representation

a number of vertices, so we'll have to decide on the size of the graph.

And then we'll have to decide what edges will be placed in the graph.

And this particular algorithm I'm going to show

you, that'll generate a randomly generated graph.

We'll use the heap and create

a two-dimensional representation of the graph.

So let's see what that means.

The overall graph is going to be a pointer That ultimately stores boolean values.

What are boolean values?

They're the values true or false.

If I have a graph

that has edges, let's say they were like What we just saw, zero to 6.

And

I have true in one of the matrix entries. So let's say, in element 3, 4, I've stored

true.

This is going to mean that the edge from vertex three to four exists.

That's what's being created by this little routine.

The way it's created is, I seed the random number generator, I hope this

is all review, otherwise you'll have to

review how a pseudo-random number generator works.

I create a graph,

in this case, of the appropriate size. It's a graph that

is, has seven nodes.

And then, for each node, I have to

have a row, a Boolean row. So these are the rows.

That's what's being created here.

And then these are all capable of storing a Boolean value.

So the heap has allocated off the heap, through this for loop I've

created a two-dimensional array. Whose base pointer is graph.

And now,

I put edges in.

And I'm going to put edges in according to a density.

What do I mean by a density? The

density

is the probability an edge exists.

So that could be 0, or it could be up to 1.

That's what dense, the range of densities are.

0 would mean, that I'm never going to put (an edge in).

If, if this had been 0, no probability would be greater than 0, less than 0.

And so I'd never put in an edge. This is the act

of putting an edge

in. 0 would lead to no edges.

One would lead to every edge, the term here is complete.

A graph that has all its' edges, all its possible edges, is called complete.

So, we have a for loop . The for loop marches through the 2 dimensional graph,

if

i equals j that means if its on the diagonal we automatically put in false.

Otherwise and this is

symmetric this turns out to

be the undirected graph.

If the probability, in our case, we're looking at a density of point one nine.

So, roughly, one in five times I'm going to stick an edge in.

And, probability is just some function I'm computing

using the random number generator you may have to

review that, or you may have to look

at the code that's online for the probability function.

That will generate a randomly generated graph of the given density.

So, here's a few questions.

Density is zero. The graph has no, what?

Density is 1, the graph is what? The C word.

The density is fixed, say, to some size and the graph gets larger.

What can we say about it?

Likely it, how likely it is to be connected.

Take a second to look at that.

Okay.

As we just said already, zero means the calculation says, no chance.

You're never going to stick in an edge.

One means you're always going to stick an edge in.

So it's going to be a complete graph. And now, if the density is 0.1 and we have

a, a size that grows. So let's say we have five

nodes, density is one. 0.1 I should say.

0.1.

That means one tenth of the time in a five node graph, we're going to stick an edge.

Well, that's not going to happen often. Five nodes, that means roughly

speaking we're going to throw in an edge 50% of the time for that particular node.

Well,

that's not going to be connected, so it's very unlikely.

Let's say we go to a 50,000

node graph whose density is 0.1.

So if you're following me, the 50,000 node graph and

we have lots of 50,000 node graphs in the real world.

Just think of the map of all the cities in the United States.

And if you're thinking about the map of all the cities in the United States.

How many roads are there out of an individual city?

Maybe there's 20 rows out of an individual city, that might even be a big city.

So a density of 0.1 on a big map

is not all that, this would mean,

0.1 would mean that on average,

we're going to get 5,000 edges

per node. Here it was an average one half edge

per node.

When half edge per node for a small graph, it's going to leave us unconnected.

5,000 edges out of a 50,000 node graph is

going to leave us with a humongous number of paths

in that graph and it's very likely that, almost

certainly, with probability approaching 1, going to be connected.

So if you have a good intuition, about what we've been talking

about with these randomly generated graphs and this is going to come up

in the homework I'm assigning you, as the graphs get larger, namely

the number of vertices, the number of nodes in the graphs get larger.

Having a particular density makes it more and more

likely that there are paths between all the nodes.