0:00

[MUSIC]

Â Okay so we're ready to see a different implementation of graphs,

Â this time using something called an adjacency list.

Â So by the end of this video you'll be able to think through the implementation of

Â graphs in Java using adjacency lists and think about comparing adjacency lists and

Â adjacency matrices, which were the focus of the previous video.

Â So let's think back to that example that we keep using of a small graph.

Â Remember this is just a toy example in the project and

Â in all the applications the graphs will be much, much bigger, but just to

Â illustrate some of the definitions and the questions we're gonna keep it small.

Â So our vertices are labeled by integers from 0 through 5 where we have

Â six vertices.

Â And we want to think about representing the edges between the vertices.

Â So we've talked about an adjacency matrix which is our 2D array of 0's and 1's.

Â 0 indicating there's no edge between the vertex in the row and

Â the vertex in the column.

Â And a 1 indicating there is such an edge between these two vertices.

Â Now we talked about how this 2D representation

Â required us to store a whole bunch of information with

Â a whole bunch of edges that might not even be in the graph.

Â And so let's think about a different way of representing these edges.

Â Instead of storing a 2D array of integers, what we'd like to do is say for

Â each vertex what are its neighbors?

Â Where can we get to from that vertex in one hop?

Â We're going to have as our basic data structure

Â in this class a map that associates vertices,

Â labeled by integers, and lists of other vertices, lists of integers.

Â Gives an adjacency list, a list of vertices to which we're adjacent.

Â Okay, and so let's think about how this corresponds to our toy example.

Â So, for example, the vertex 5,

Â ought to have in its list of adjacent vertices both 3 and 4,

Â because there's an outgoing edge, it starts at 5 and then goes to vertex 3, but

Â there's another edge that starts at 5 and goes to vertex 4.

Â Then we can think for

Â each vertex in our graph, what its set of neighbors looks like.

Â Now notice that I said outgoing edges and when we're talking about neighbors we're

Â talking about neighbors that we can get to starting at the current vertex and

Â going out.

Â And because our graph is directed, that directionality and

Â that asymmetry is important and it is going to come into play.

Â And you'll see how in just a little bit.

Â So, first of all notice how we can capture

Â the whole graph relationship just from understanding these relationships.

Â Every edge will be pictured at some point, or will be depicted in this

Â adjacency list collection at some point because we can just look up an edge by

Â saying what's its start point that's going to tell us which adjacent list to look in.

Â And then the end point will show up in the list of neighbors of that starting point.

Â Okay ,now we want to translate this back to Java.

Â And we wanna think about implementing those two abstract methods that we talked

Â about in the abstract class that defines what a graph ought to be able to do.

Â And so for example we want to add a vertex and we wanna add an edge.

Â And when we've got these lists.

Â Well, these lists are easy to change dynamically.

Â And so for example if we want to add a vertex, all we need to do is to put

Â a new association of an integer to a list of integers, in our map,

Â namely our data structures that stores these adjacency lists.

Â And so we just create a new array list of integers.

Â It's going to be the list of neighbors of the new vertex.

Â And we're going to put an entry in the map that says for

Â this new vertex v, associate this set of neighbors.

Â Okay, not too bad.

Â Similarly to add an edge, then we can use in a lot of the built in functionality and

Â say I want to add an edge between v and w.

Â So that means I have to add w to the list of neighbors of v.

Â So I have to get the list of neighbors of v by using that mapped data structure,

Â so I'm going to get the object associated with the key v.

Â And then that object, which is a list, I'm going to add to it the new neighbor,

Â that I'm asserting that w is a new neighbor of v.

Â So I go ahead and do that.

Â So what we're seeing is that it's easy to add and remove vertices,

Â it's easy to add and remove edges.

Â And if we think about the storage requirements for

Â these adjacency lists, they might use a lot less memory than adjacency matrices,

Â especially if we have what's known as a sparse graph.

Â So, a sparse graph is one where there aren't a lot of edges between vertices

Â compared to the maximum possible number of edges.

Â So, if we do a little bit of counting and

Â we think about the number of edges possible in an abstract graph.

Â If we have n vertices then there's n squared many possible

Â edges between them if we allow self loops and we allow

Â an edge to go from any vertex to any other vertex, and not allowing parallel edges.

Â So n squared can get really big compared to n.

Â A sparse graph is one where the number of edges asymptotically is closer to just

Â the number of vertices.

Â And if you think about most applications,

Â most applications do line the realm with the sparse graphs when we're depicting

Â the website graph, which is connected via hyperlinks.

Â Again, most websites don't have that many hyperlinks out to other websites.

Â And so again, that graph is going to be a sparse graph.

Â And then going back to our project with the transportation networks,

Â most cities don't have all that many outgoing roads compared to

Â all possible roads in the world.

Â And so this as well is going to be a sparse graph.

Â And so lists seem to be winning out, and

Â adjacency list representation seems to be winning out really well.

Â But we talked here about easy to add remove and vertices, easy to add and

Â remove edges, and that might be a bit selfish.

Â As programmers it was pretty easy because we were able to use built in functions.

Â But if you think back to performance analysis when we're trying to

Â think about the performance of methods we wanna talk about them being fast, not just

Â how easy was it for the programmer to code-up this particular method.

Â And so we used built-in methods of the map class, and of the Array List class.

Â And so what we have to do is look at the documentation for those classes to get

Â insight into how long those methods actually take, and how much that

Â time scales with the size of the input and the size of those data structures.

Â And so we can do that.

Â We can look up the documentation.

Â And what's really nice is that in this documentation for

Â the ArrayList class it's spelled out right over there that the operations

Â looking for the size of a list, or asking if something is empty, or

Â getting an element from the list, or adding an element from the list,

Â all of these are roughly constant time operations.

Â Therefore the add method, it's a slightly more complicated analysis,

Â it's amortized time is constant.

Â But for our purposes, what we wanna get

Â out of this documentation is that all of these operations are very efficient.

Â And so not only was it easy for us, as the programmers, to write these methods using

Â the built in class methods, those methods that we wrote will also be very efficient.

Â So, why use anything else?

Â And the reason we still like having adjacency matrices in our back

Â pockets is for that algebraic structure that it encodes.

Â And for more complicated analysis, and algorithms about graphs,

Â that algebraic structure turns out to be really useful, and very powerful.

Â And so we'll see a little more of that later on.

Â