[SOUND] All right, in this support video, we're gonna write some code. Mia has talked to you about two ways of representing a graph, using an adjacency list, and using an adjacency matrix. And she's also talked to you about the out degree of the vertices in a graph. So, in this video what we're going to do is we're actually going to write a method where we get all of the nodes that are one degree one hop away from a particular node in the graph. And we'll be writing this code for both an adjacency matrix as well as an adjacency list representation. So, by the end of this video, you'll be able to write this code. We're gonna do it together. Not actually in Eclipse. We're just gonna write it out on these slides. And the reason I'm choosing to write by hand, rather than write in the code in Eclipse is that sometimes when you're writing on paper, or on a tablet computer. You're a little bit more thoughtful about what it is that you're doing. Because you're not able to run the code and test it. So, that's why I'm gonna show you this code written out on a tablet. All right, so lets review the Adjacency Matrix Representation for the graph. As you may recall there's a row for every vertex in the graph, so these rows correspond to vertices 1, 2, 3, 4 and 5. 5 and then, in each row there's a 0 in the entry if there's no edge from that vertex to the vertex represented by the column, and there's a 1 if there is an edge. So for example, if we look at this edge right here, we can find that 1 for that edge in row 2. Go over here to entry 3 and there's our edge. There's a 1 there. And 2 doesn't have edges anywhere else, so there are no other 1's in 2's realm. So, we're going to use this information to write the get neighbors method in our graph representation. So, we've got the start of our graph representation there on the screen, we've got our matrix representing the edges in the graph. And our goal now is to write get neighbors. So, let's go on and actually do the writing. Although before we do, let's actually go back for one second and look at this graph and think about, how can we tell what nodes are neighbors of a particular node. Well, all we really need to do is we need to look at the row. So, we just look at this row right here, and if there's a 0 in that entry, then, it's not a neighbor. But if there's a one in the entry, then it is a neighbor, and that's the essence of the algorithm that we're going to use to implement in our method. So, here's the header for our gate neighbor's method. We're going to return a list of integers, and that list of integers is going to contain all the vertex integers that our neighbors of the particular node that we pass in. So, we're taking an int v, which is a vertex in our graph, we're gonna return the integers representing all the neighbors of that vertex. So, let's get started. Well, what's the first thing that we need? We need to return a list, so we're going to need to have a list to return. So, let's go ahead and create that list. And I'll make my list an array list. Okay, now we've got our list, and we're just gonna implement that algorithm just like I described. V is going to be the row of the adjacency matrix that we're looking at. And then, we're just gonna iterate all the way through that row, looking for the ones and adding them to our list to return when we find them. So, we're gonna need a loop. Our loop is going to go as long as I is less than the number of vertices in the graph. So, I should be less than, and I'm saying here we have this getNumVertices method already defined for us. So, I will be less than getNumVertices and then, i plus, plus. All right. So now, what we need to do, we need to check the entry in the particular row that we're looking at, figure out if it's a one, and if it is, we'll add it to our list to return. And, in fact, I'm gonna look to see if it's a 0, and if it's not a 0, then I'll add it to the list just in case somebody's using some non-zero value to represent an edge, like a weighted edge. So, if my adjacency matrix in row v at position I is not equal to 0, then I will add It to my neighbor's list. And that's all I need to do, that'll collect all the neighbors of v and then at the very end of course I need to return the neighbors. Oops. And that's it, that's our implementation of get neighbors for our adjacency matrix. So, let's now look at the implementation for an adjacency list, here's our adjacency list representation of the very same graph. So, let's look at how this works, we have basically a map that's going to map the integers, which are the vertices in the graph, to a list of all of their neighbors. Okay, so you might be thinking, this is actually pretty tricky reveal, all we need to do is look up the index we're looking for and return the list of neighbors, and you'd pretty much right. It really is almost that simple. So, here's again our method header, we return a list. So, now I can just, one idea, is that I can just return the adjacent C list. Map, that's this variable right up here. So, I'll turn adjacency list map.get to get the index v. So, is it really that simple? Is that all I need to do? Take a minute and think about that. Is that an implementation that'll solve this problem? Alright, now that you've thought about it, well the answer is yes, and well not quite. Yes, it actually does return a list of neighbors of the particular node v that we're looking for. But the danger is, it returns the list of neighbors that we're using for internal storage inside our graph. We've just exposed this list that's supposed to be internal to our graph representation. So, anybody out there can now modify this list and change our graph. Structure, and we don't want that to happen. So, we can fix this problem by instead of returning the list that we take right out of this hash map and return it to the user, we can return a copy of this list. So, instead of just returning the list directly, let's just change it slightly so that we return a new list And we can pass it in the thing that we were returning before. That implementation there is just a little bit safer than what we originally had. Both will return the correct list, but one will protect the private data inside our graph.
