[MUSIC] All right, so we're ready to bring together some graph properties and implementation decisions and see the trade-offs between them. By the end of this video, you'll be able to implement a method to talk about the neighbors of a vertex in two different ways. Each of those ways depending on the implementation that we have for the graph structure. Now, what will you want to do in this video, is think about the ramifications of the decisions of the implementation. And then how do we build other features of the graph, based on those implementations. Now you'll see more details of the Java code in a support video that comes along with this, and so stay tuned for that. All right, so let's think about what the notion of neighbor is really getting at. And we have our graph example that we've been working with. This is just our toy six-vertex example. And if we want to think about a neighbor in this graph, we're talking about the relationship between one vertex and other vertices. And so a neighbor of a vertex is a vertex which is adjacent to that one. And adjacent here means that there's an edge between them. And so let's focus in on vertex 4 over here, and ask which vertices are adjacent to 4? Now we can see that there's two edges that are related to 4 in some way. There's one outgoing edge and one incoming edge. And so if we drop the directions altogether, then both of the vertices 3 and 5 seem to be related to, or adjacent to, or connected to 4 in the same way. But for directed graphs, where we're going to tease apart the relationship the 3 has to 4 from the relationship that 5 has to 4. And so let's focus on the relationship between the vertex 5 and the vertex 4. And we notice the vertex 5 is the start point of an edge that ends at 4. And so we can talk about the in degree of the vertex 4 as the number of incoming edges to that vertex. And so then, in order to look at all of the neighbors of 4, that are neighbors by virtue of being the star point of edges that end at 4. We want to count all of the incoming edges to 4. We want to count the in degree of that vertex. We could also talk about the out degree of the vertex. We could talk about all of the vertices that we can get to from starting at 4 and just going by one edge over to a new vertex. And so, for example, from 4 we could follow the edge to 3. And now let's start actually thinking about methods to implement finding these in degrees and out degrees. So for the out degree, what we're trying to do is count all of the edges that are outgoing from the vertex 4. And one of our representation for graphs is the adjacency matrix representation. So we have a grid of 0's and 1's, and we have as many rows as there are vertices, we have as many columns as there are vertices. And each entry in the adjacency matrix denotes an edge which starts at the row vertex and ends at the column vertex. And so if we're looking at the number of outgoing edges from the vertex 4, we just need to look into that fourth row of the matrix and see how many edges start at vertex 4. Namely how many 1s are in that row of the matrix. And so we can go along and see that's there's exactly one 1 and so our out degree is 1. All right, we had another representation of graphs as well. A representation in terms of the adjacency list. And so in the adjacency list representation we have a list that's associated with every vertex. And so for the vertex 4 we have a list that contains just 3 and what that denotes is that there's an edge that starts at 4 and goes to 3. And so if we're looking at how many edges start at the vertex 4, what we need to know is the size of the list that's associated with 4 in the adjacency list representation. And so now, what do you think? Which of these representations of graphs makes it easier, or more efficient, to find the out degree of a vertex in the graph? All right, welcome back. Let's now ask the flip question and think about the in degree of a vertex. So if we're thinking about the in degree of the vertex 4. In the adjacency matrix representation things are very symmetric, and the incoming edges are just denoted along columns instead of along rows. And so if we want to think about the number of incoming edges to 4, we need to read off that fourth column in the matrix and look for 1s in that fourth column. Each one of those 1s has four as its endpoint, but in the adjacency list representation we have a slightly different situation. Our markers are indices for which lists we have in the adjacency lists representation are the starting point of edges. And so if we're looking for the incoming edges to 4, what we need to do is look at each one of the lists in the adjacency lists representation, and ask which one of those lists contain the vertex 4? Because a list contains the vertex 4 that means the 4 is the end point of the corresponding edge. All right so we have two different representations, which one makes computing the in degree of a vertex more efficient? All righty now what's next? We've talked about in degrees, we've talked about out degrees we've seen how they both contribute to this notion of a neighbor of a vertex. And now what we're ready to do is implement some of these notions in Java. So in this week we're focusing on the differences in performance based on implementing graphs using a JSON-c matrices and a JSON-c lists. And then in future weeks, you'll build even richer class structures for representing graphs. And you'll wanna take these performance considerations into account as you're building these more complicated structures.
