2.3 Graph Theory & Algorithms

Loading...

Del curso dictado por University of California, Santa Cruz

C++ For C Programmers, Part A

529 calificaciones

Explore Related Videos

At Coursera, you will find the best lectures in the world. Here are some of our personalized recommendations for you

University of California, Santa Cruz

C++ For C Programmers, Part A

529 calificaciones

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.

De la lección

Module 2

Review of Dijkstra's shortest path algorithm. C++ Functions and Generics. C++ classes and OO. Point as an example.

2.1 C++ Generics and Functions14:13

2.2 Multiple Template Arguments8:48

2.3 Graph Theory & Algorithms9:33

2.4 Graph as a Data Structure11:10

2.5 Dijkstra Shortest Path16:42

2.6 C++ Creating Types5:22

2.7 Enum & Operator Overloading4:04

2.8 Example: typedef days18:39

2.9 Natural Way to Build Widgets6:47

2.10 C++ Point26:58

Conoce a los instructores

Ira Pohl
Professor
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.

Explora nuestro catálogo

Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.

Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.

© 2019 Coursera Inc. Todos los derechos reservados.

Descargar en la App Store

Consíguelo en Google Play