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
Títulos y certificados

Explorar todo lo que Coursera tiene para ofrecer

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

2.4 Graph as a Data Structure

Loading...

C++ For C Programmers, Part A

Universidad de California en Santa Cruz

4.4 (594 calificaciones) | 91K 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 (594 calificaciones)

5 stars
382 ratings
4 stars
138 ratings
3 stars
31 ratings
2 stars
18 ratings
1 star
25 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

So when we use graphs on computers,

we need to create an internal structure, a data structure for

representing that graph, such as trying to represent K4.

And what we've discovered in computer science, and, again,

I hope for many of you this is a review, if it's trivial,

you can move on, is two major representations.

One's called a connectivity matrix, and

the other is called an edge list representation.

And there are tradeoffs.

With data structures there are always tradeoffs.

So for some algorithms and for some graphs, one representation

would have strong benefits over the second representation.

The typical tradeoffs involve how much data you need to store

and how efficient the algorithm is.

So it may indeed be that

one representation requires too much storage for a particular problem,

and another representation might require too much processing.

So we find that both are extremely useful.

Sometimes in the same problem we wanna use both.

But overall, for those of you who are trying to review this,

probably if you've had experiences largely with the edge list representation,

the edge list representation is typically much better when the graph is not full,

when there's not large numbers of edges, high degrees.

So if you have a graph of, like, size 100, meaning there are 100 vertices or

nodes, and the average degree in that graph is maybe four,

so for the 100 nodes, you're going to have something like 400 edges.

That would be considered sparse.

But if you had a graph in which there were 100 nodes and the average degree was 50 or

60, then you would have a huge number of edges, and that would be dense.

And typically the rule of thumb is dense graphs,

matrix representation is frequently better.

Sparse graphs, edgeless representation is better.

Most real world problems are relatively sparse.

A representation of a directed graph with n vertices can

use a list, for example, an array of n lists of vertices.

So that in list i, you're representing for a node i that you've labeled

with the number i, each vertex that's

directly connected, each vertex that can be reached from i to vertex j.

And then some other terminology is you may also want in that graph

to have not only edges but a weight on the edge or clause on the edge.

So think about going form San Francisco to San Jose.

Roughly speaking, we're talking 60 miles.

I may be a little off there, but I think it's somewhere between 60 and 80 miles.

And that would be a cost.

You're gonna drive in a car.

You're gonna have to drive 60 miles.

That's one way to measure that versus going from

San Francisco to Marin, which maybe is two miles.

So if you have an opportunity to go through one place or

the other for some kind of vacation day

and that cost figured in, you're likely to go to Marin rather than to San Jose.

And, indeed, in route finding, when you try to find, when your onboard computer

in your car tries to find you a route, it's generally trying to find you a least

costly route either based on time or based on distance.

So that's a weighted graph.

An undirected graph, any time you have, is what we were doing with K4,

any time you have a road from, let's use San Jose, San Francisco again.

Any time you can go from San Francisco to San Jose, you can use the same road and

go back.

So a lot of the problem is because we just want to avoid the directed case, but

it's not that much harder to deal with the directed case.

It's we're going to think of two-way roads.

But analogously, one-way roads are perfectly fine, and all of the algorithms

I will be talking about could readily be adapted to the directed case.

So here's a matrix versus a list of a graph.

They're actually the same graph.

And let me draw directly on here what graph is being represented.

I'm gonna have nodes 1,

nodes 2, nodes 3, and nodes 4.

And in this matrix case, it says one linked with one, there is a road.

So that is a special road.

I'm gonna usually not worry about that.

That's a loop.

Most of the graphs I will be talking about will be loop-free,

because loops aren't particularly interesting.

The fact I'm in San Francisco and I can drive around in San Francisco is a loop.

There's also from 1 a road to 2.

There's also from 1 a road to 3.

There's also a road from 1 to 4.

So all those one entries mean that I was able

to drive in this direction between 1 and

2, 1 and 3, 1 and 4.

Now, 2 has uniquely one edge.

It's 2 to 1.

Three has two edges.

3 can go to 2, and 3 can go to 4.

4 can go to 2.

And 4 to go to 3.

So that's the graph that's being represented here.

And you can see in the edge representation the list,

the edge list, the same information.

I now have four lists.

These are the edge, these are the vertex numbers, the node numbers.

And then this is what 1 is linked to.

It's linked to 1.

That's the loop.

It's linked to 2.

It's linked to 3.

It's linked to 4.

2 only has, is a degree 1 node.

Okay.

So you should be able to do what I've just done.

You should be able to generate from a graph.

Here's a graph.

I've actually drawn it here.

We were drawing it in real time.

I'm not a great drawer of graphs, but

you see how the model is.

And, indeed, you should be able to take a graph of this kind and

produce either of those two representations.

So that's an important skill set.

So here's a quiz.

Here is undirected graph, meaning that each edge can go in either direction.

Generate an edgeless representation and a matrix representation for it.

So it has four edges and five nodes, a little crisscross graph.

Okay. Take a second.

And the answer is, here is a matrix representation.

And let's see if this provides it.

Now, notice, in this case we have symmetry.

I'm going to have 1,

2, 3.

All right.

I think I'm gonna want to put 3 in the middle.

I'm gonna put 3 in the middle.

And I'm gonna do 5.

Okay.

I think this will work.

So I have 1 linked to 3.

And notice I have 3 linked to 1.

That's the symmetry.

1 linked to 3, 3 linked to 1.

2 linked to 3,

4 linked to 3, 5 linked to 3, and then 3, there's no loops,

and it's also linked to 1, 2, 3, and 4.

So that's exactly what we just saw.

So all of you should have been able to draw that once you

saw the graph in the previous slide.

And here is the same thing.

And I don't have to change my drawing, but

it's just the edge list, which now,

since this is what we might call a sparse graph,

is degree 1 for each of these nodes.

Each of these nodes is degree 1.

Notice, by the way, that this graph is what we call connected.

That'll be a nice property that'll be of interest to us

when we start working on our algorithms.

And here's 3.

3 has a degree of 4.

All the other have degree of 1.

And these are the undirected case.

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