[MUSIC] So in the previous video we started talking about graphs as this general data structure where we have nodes and we have connections between them. And what we're going to do now is really hammer down some definitions and see how these definitions come into play. By the end of this video you'll be very comfortable with these basic definitions that are associated with graphs. So as we mentioned, in order to specify a graph all we need to talk about are what the collection of basic objects are, and then what the relationships between them need to be. And the terminology that we use for the basic objects are the vertices or the nodes. And then the terminology that we use for the relationships between them are the edges or the arcs or the links. Now the vertex set is often denoted by capital V. The edge set is often denoted by capital E. And something you wanna keep in mind is that when we're talking with the size of a graph, which is going to be important when we think about performance, the size of the graph really depends on both the size of V and the size of E. The number of vertices and the number of edges. We'll talk more about that as we develop more algorithms. Now think back to the example with the friendship graph. If I'm your friend, you're my friend, we're both friends with one another. It's not like I can be your friend but you can't be my friend back. It doesn't work. In that situation our edges between vertices are undirected. They don't have arrowheads. They don't point from one vertex to another. A way of saying that in math speak is that the edge relationship is symmetric. Now, we have other graphs that ordering really does matter for. And think back to the example we talked about before with dependencies, with task dependencies, and in that situation the arrows really do matter. And so we can have grasped directed which means that for every edge we want to think about it's end points. So we've got two endpoints for each edge, each of the endpoints is a vertex. And it makes a difference whether the edges pointing from one vertex to the other or vice versa. All right, so we've got a notion of undirected graphs, we've got a notion of directive graphs. And then we can also think about enriching these graphs a little bit, and sometimes our edges can carry with them more information. So sometimes we want to label our edges, perhaps with weights that might represent something like the cost of going across this edge. And you'll see the weights coming into play again and again when we develop algorithms in the future modules of this class. So, we've got these vertices, we've got edges, and they're coming together to build up this data structure. So let's start by thinking about the neighborhood relationship of a particular vertex. And so a one vertex is a neighbor of another vertex if there's an edge between them. And so take a look at this particular graph, and think about what the neighbors are of the vertex 4. So let's talk about one more notion that's going to be really important about graphs, and that's the notion of paths. So when we're thinking about a big graph, what often we wanna do is find a way of getting from one part of the graph to another. And so that might be useful in the root planning project that you're doing in this class, but it could also be useful for thinking about global properties of the graph. So a path in a graph is a sequence of vertices and edges that depict, you can imagine yourself hopping along the edges in the graph to get from one place to another. And so I'm only ever allowed to move along edges, from one vertex to another along an edge. So let's think about this particular directed graph, and think about for which pair of these vertices is there a path in the graph that goes from the first vertex to the second. All right, now we're going to tweak this example just a little bit, and see whether things will change when we drop those arrowheads from the edges. So think about the same pairs of vertices, the same underlying vertex set, but now when we've drop the errors on the edges, which pair of vertices can be reached from one to the other? So the moral of those two examples was that directionality really matters, and that when we're thinking about moving along the graph, what we need to think about are those edges, but also the directions on the edges, and as we see any other information that we've encoded into those edges. So in the next few videos, what we're going to do is think about moving away from this abstract depiction of circles and arrows, and think about how do we actually bring this graph data structure to Java?