本课程是面向有C语言经验的，并想要学习C++编程的程序员们。涉及到的例子和练习需要有对基础算法和面向对象软件的理解。
2.3 Graph Theory & Algorithms
Loading...
來自 University of California, Santa Cruz 的課程
C++ For C Programmers, Part A
470 個評分
從本節課中
Module 2
Review of Dijkstra's shortest path algorithm. C++ Functions and Generics. C++ classes and OO.
Point as an example.
與講師見面
Ira PohlProfessor
Computer Science
So the other thing that we're going to emphasize in this
course is algorithmic graph theory.
That's gonna be the domain we're largely going to use for examples, and
there's several reasons for it.
Turns out that graph theory is an underpinning to
a lot of the discrete problems of interest in computer science.
It shows up all over the place.
In artificial intelligence,
there are search algorithms that are foundationally graph theory algorithms.
Your GPS devices where you're asking your car to find you a route,
you're doing basically very efficient, very complex graph theory calculations.
When you're working on the internet, and you're connecting packets between
machines over the many hundreds of millions of nodes now on internet.
You're basically doing graph theory.
So this is basically a great topic.
It's foundational in computer science.
It requires a lot of careful though in the use of data structures its not
typically an ordinary computer language a built in data type its not
a native data type so one of the things we're going to find with graph theory is
thinking about how to implement graph as a data type.
That's going to be part of our
understanding of using C++ as an object oriented language.
And hopefully you have some of that background.
So you should have some notion of what object orientation is.
Maybe you even have experience with a language like Java or
Python that has object orientation built in, and that experience
will stand you in good stead, but you'll still have to see how C++ uses it.
But again, graph theory, by itself is just a very important topic.
In computational science and applicable all over.
So the first thing I want you to do, since to some extent this is review for you,
is draw the complete graph of four nodes.
And I will give you a definition.
A complete graph if you have forgotten that is a graph in which every
edge exists in that graph in that map,
so if you have San Francisco, Los Angeles,
San Jose and Selinas as cities, that would be four nodes.
Then there's a direct path from each city to
every other city in that graph, and that would be called a complete graph.
So take a second and try to draw it.
So I'm gonna draw it for you, and
we're going to assume that we are using undirected edges so
there are directed edges and undirected edges in graph theory but
most of what I will be doing will be using direct, undirected edges.
And undirected edges are like roads that are two way roads so
you can go in either direction.
So here is city one to city two.
Here is city two to city three,
city three to city four, city four back to city one.
But that's not complete yet.
I could also go from city one to city three.
And I can also go from city two to city four,
and I'll do it with a little cross over.
Are there any other connections that can be made between these?
No.
So you notice a certain property here.
Now in the graph theory world this is called K4, and
you should be able to, if you wanted, K5 now.
That would be five nodes, all edges and five nodes.
K6 and so on, K is just, a notation, meaning complete graph.
So, we have four nodes.
I'm gonna label them, 1, 2, 3, 4.
We could've labeled them, as well, A, B, C, D.
Or you could've labeled them San Francisco, Salinas, San Jose, Los Angeles.
And then the other property I want you to know about,
or another definition, is look at note three.
It has three edges out.
It has an edge between 3 and 2.
I'm gonna notationally write that in between parentheses.
It has an edge between 3 and 4.
It has an edge between 3 and 1.
So it has three edges and this is called degree.
So the degree of any of these nodes, in fact, they all had three edges.
So degree of,
for example, node 1 is 3.
In fact, the degree of any of them is 3.
In fact if I have the graph K4, then
the degree of each node is one less than four, three.
And for K5, what do you think?
It would be four.
The degree of K5 would be four.
The degree of K10 would be nine.
Degree of K a million would be 999,999 though that's going
to take a while to draw, so I'm not going to ask you to draw K a million.
Anyway, that's why we have computers.
So this is our answer.
I just want to give you a little flavor of where this all came from.
This came from in some ways a fancy problem.
Almost a real world problem actually and
graph theory was invented by a very famous mathematician, Euler.
Leonhard Euler, 1735.
Euler was incredibly prolific,
maybe the most important mathematician of the 18th century.
And he was studying a problem in his region, and
it was called the Seven Bridges of Konigsberg problem.
And in trying to solve that problem, he uses mathematical
genius to figure out an abstraction that let him
logically approach this problem of crossing seven bridges.
So let me show you what that problem is.
There was a city, Konigsberg.
There was a river in the city.
Several forks in it, and there were seven bridges crossing the river,
and they are shown here in the slide.
And the typical Sunday afternoon stroll, so if you were young lovers and
you wanted to do something on a Sunday afternoon,
you decided to stroll in a way that got you across all seven bridges.
And that got you into every area of the city.
The conundrum, for the strollers was, can I go and
cross every bridge, once and only once?
And cover all these sections of the city.
Is there a way to do this?
And nobody knew how to do it.
And indeed by converting it into an abstract problem,
Euler was able to show that no such path existed.
That later, a path like that was later called an Euler path in his honor,
That's the origins, a good story, those are the origins of graph theory.
And graph theory was a mathematical concept useful for
many years, used by mathematicians, but
not that important to real world applications Until the 20th century.
The 20th century coupled with computers, many computational problems,
including optimization problems, including deduction problems,
including matching problems, including looking things up and databases,
all could be seen at, you could get incredible insights in these problems
by representing these things as graph theory prompts.
