[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.
Leo PorterAssistant Teaching Professor
Mia MinnesAssistant Teaching Professor
Christine AlvaradoAssociate Teaching Professor
