Okay, so let's come back and think about how to finish off this adjacency matrix

representation of the graph.

And in particular,

let's reflect on what properties we've seen as we've built up this class.

So you'll write up some of these other methods as part of the project,

and also we'll guide you through some of them in the support videos.

But as you're writing these methods, you want to think about

the performance implications of the data structure that we've chosen.

So we've chosen a data structure that is very algebraic.

A 2D array,

which we can think of abstractly as a matrix that we can do linear algebra on.

And so it turns out that once we represent a graph as this algebraic

representation, then the linear algebra tools are very powerful.

And you'll see one example of that in a later video.

But as you go on and think about more graph algorithms and more applications of

graphs, you see linear algebra coming in again, and again, and again.

And so, thinking of the adjacency matrix as a crucial representation of the graph

is indeed very powerful.

But it does have a lot of drawbacks.

Because even though it was really fast for us to implement the test for

edges method as you saw in the video quiz.

And even though it's really fast to add and

remove edges because we're just dealing with a single entry in the 2D array.

If we want to change the big structure,

the underlying structure of the graph by adding vertices, that took a lot of time.

And the most important piece that is a drawback for the adjacency matrix is that

when we think about this storage that's required an adjacency matrix, we need to

store a 2D array, whose dimensions, are the number of the vertices.

So that means, that we're storing

n squared pieces of information if n is the number of vertices.

And that can get really, really big.

So think back to what these vertices represent.

These vertices are cities, or they're intersections, or in biological

representations, they might be genomes or they might be little pieces of genomes.

Or if you think back to the World Wide Web analysis,

then each of these vertices is a unique URL, unique website.

Or if you're thinking about social networks,

then each of these vertices is a person.

And in all of these, think in all of these applications, the set of vertices is huge.

Not only is the set of vertices huge, most vertices are not related to one another.

So most people are not friends with most other people in this world.

Our communities don't encompass the whole globe, don't encompass the whole world.

Similarly, most cities don't have