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.
Leo PorterAssistant Teaching Professor
Mia MinnesAssistant Teaching Professor
Christine AlvaradoAssociate Teaching Professor
