and how efficient the algorithm is.
So it may indeed be that
one representation requires too much storage for a particular problem,
and another representation might require too much processing.
So we find that both are extremely useful.
Sometimes in the same problem we wanna use both.
But overall, for those of you who are trying to review this,
probably if you've had experiences largely with the edge list representation,
the edge list representation is typically much better when the graph is not full,
when there's not large numbers of edges, high degrees.
So if you have a graph of, like, size 100, meaning there are 100 vertices or
nodes, and the average degree in that graph is maybe four,
so for the 100 nodes, you're going to have something like 400 edges.
That would be considered sparse.
But if you had a graph in which there were 100 nodes and the average degree was 50 or
60, then you would have a huge number of edges, and that would be dense.
And typically the rule of thumb is dense graphs,
matrix representation is frequently better.
Sparse graphs, edgeless representation is better.
Most real world problems are relatively sparse.
A representation of a directed graph with n vertices can
use a list, for example, an array of n lists of vertices.
So that in list i, you're representing for a node i that you've labeled
with the number i, each vertex that's
directly connected, each vertex that can be reached from i to vertex j.