[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?