Explore
For Enterprise
Join for Free
Log In

artes y humanidades
Negocios
Ciencias de la Computación
Ciencia de Datos
Tecnología de información
salud
Matemáticas y Lógica
Desarrollo Personal
Ciencias Físicas e Ingeniería
Ciencias sociales
Aprendizaje de un idioma
Grados
Certificados

Explorar todo lo que Coursera tiene para ofrecer

Explorar
Buscar
For Enterprise
Inicia Sesión
Únete de forma gratuita

2.3 Graph Theory & Algorithms

Loading...

C++ For C Programmers, Part A

Universidad de California en Santa Cruz

4.4 (617 calificaciones) | 93K estudiantes inscritos

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.

Destrezas que aprenderás

Graph Theory, C++11, C++, Graph Algorithms

Revisiones

4.4 (617 calificaciones)

5 stars
402 ratings
4 stars
138 ratings
3 stars
31 ratings
2 stars
20 ratings
1 star
26 ratings

AK

Jul 04, 2017

I like Prof. Ira a lot and wish to see more courses from him! I wish I was his student at SC. Best Regards to him and the Coursera team for the great work.

PK

Jul 18, 2018

I really loved this course. It is really helpul for my programming aspect. I have managed to develop my logical abilty and this course really helped me.

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

Impartido por:

Ira Pohl
Professor

Transcripción

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

Coursera
Acerca de
Liderazgo
Empleo
Catálogo
Certificados
Certificados MasterTrack™
Grados
For Enterprise
For Government

Comunidad
Learners
Partners
Developers
Beta Testers
Translators

Conectar
Blog
Facebook
LinkedIn
Twitter
Instagram
Youtube
Blog de Tecnología

Más
Términos
Privacidad
Ayuda
Accesibilidad
Prensa
Contacto
Directorio
Afiliados