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.
2.4 Graph as a Data Structure
Loading...
Del curso dictado por University of California, Santa Cruz
C++ For C Programmers, Part A
531 calificaciones
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.
Conoce a los instructores
Ira PohlProfessor
Computer Science
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.
