[MUSIC]

All right, we're ready to implement graphs.

Now that we have their definitions and

some of the motivations behind the graphs out the way.

Let's thinks about how to write some classes to describe graphs in Java.

And so by the end of this video, you'll be well on your way to doing just that.

So, thinking back to what we have to represent in our code.

We have the basic objects, which are the nodes or the vertices, and

then we wanna talk about relationships between them.

But now we have to translate everything into

object that the computer can actually manipulate and work with.

And so we're going to represent our vertices as integers.

And so each vertex is going to be named by some integer.

It's going to be a non-negative integer, zero through some number.

And then we can talk about the relationship between those integers

as those edges.

And so let's start building up our class.

And remember that little icon that we've been using throughout the whole

specialization to indicate a class definition.

And so for our class we're going to have to keep track in a given graph,

how many vertices we have and how many edges.

And so those are going to be our private number fields, and

then as we build up a graph and add more vertices, add more edges we're going

to want to be able to have access to those key properties that we care about,

the number of vertices, the number of edges,

that as we said before will determine the size of the graph.

We need both of those components.

We're going to start by saying any graph needs to tell us information about that.

Now notice that the class that we're defining right now is an abstract class.

And in the abstract class what we're doing is we're saying some data

that's associated with any graph and

some methods that ought to be available whenever we have a graph.

But we're going to leave some of the implementation not completely specified

and we're going to leave it to our subclasses to specify

how we implement some of the key functionalities of the graph.

So, in particular for a graph, we're going to want to add vertices, and

so any graph ought to be able to do that.

So we have a method in our abstract classes says,

we ought to be able to add a vertex.

And notice that there's no arguments to this method because what we're going to do

is just say, however many vertices we have now, those have certain indices.

Now, add a new vertex, and just give it the next available index.

And, how do we do that?

How do we represent vertices?

We'll that's going to be an implementation detail

that's decided by the subclass that we'll write a little bit later.

And so as part of our addVertex method,

the first thing we do is we're going to call the implementAddVertex method,

that at this point we're going to leave abstract.

We're going to say whichever class fills in the specification,

fills in the implementation, will have to tell me how to implement adding a vertex.

But, any graph ought to be able to do that.

And as soon as I've implemented add the vertex,

then I need to increment my count of how many vertices there are by one.

Okay, now we're gonna do a similar process for adding edges, and for our abstract

class definition, we're going to specify that we need at least one other method

that should be available when we have a graph, and that's the getNeighbors method.

Now, why is that important?

Why do we care about getting neighbors?

The reason we have a graph is not just for the nodes and

thinking about them as objects but we care about the relationships, and

so if we have a particular node that we're trying to think about then

we wanna know which vertices are adjacent to it.

And thinking back to the project,

thinking back to the application that we care about.

If our nodes are cities then what we'd like to know is, which other cities

could we get to just by following a single road, or if our edges represent

airplane routes then which cities can we get to just using a non-stop flight.

So the getNeighbors method is a really important method that we would like to

implement in our graph.

And so what our next step will be is thinking about the subclasses that we'll

define in Java to fill in some of those abstract methods and

in particular to make decisions about how to represent our vertices and our edges so

that we know how to implement those methods.