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.

Loading...

From the course by University of California, Santa Cruz

C++ For C Programmers, Part A

370 ratings

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.

From the lesson

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 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.

Â Coursera provides universal access to the worldâ€™s best education,
partnering with top universities and organizations to offer courses online.