implementation, much less efficient, that would make it unusable for, the huge
graphs that we see in practice. Another one is called the adjacency matrix
representation, Here we maintain a 2-dimensional v x v
array, It's a boolean array, 0-1 or true or
false. And for every edge v-w in the graph you
put true for row v in column w and for row w in column v.
So it's actually two representations of each edge in an adjacency matrix graph
representation. S, you can immediately, give a v and w
test whether there's an edge connecting v and w.
But that's one of the few operations that's efficient with this representation
and it's not very widely used, because for a huge graph, say with billions of, of,
vertices, You would have to have billion squared
number of entries in this array, which is going to be too big for your computer,
most likely. So this one actually isn't that widely
used. A, The one that is most widely used in
practice, and the one that we'll stick with, is called the adjacency list
representation. And that's where we keep a vertex index
array where, for every vertex, we maintain a list of the vertices that are adjacent
to that. So, for example, vertex four, Has, five,
is connected to five, six, and three, so its list has five, six, and three on it.
Now, on lower level representations we've talk about using linked width or array for
these, But actually in modern lingo with the
background that we'd built with algorisms what we're going to use is an abstract
data type. Our bag representation for this, which is
implemented with a linked list, but we don't have to think about it when we're
talking about graphs. we'd keep the vertices,
Names of, numbers of the vertices that are adjacent to each given vertex in a bag.
And we know that we can implement it, such that we can iterate through and time
proportional to the number of entries and the space taken is also proportional to
the number of entries,, And that's going to enable us to process
huge graphs. So here's the full implementation of the
Jason C, List graph representation.
So, the private instance variables that we're gonna use area the number of
vertices in the graph and then a array of nags of integers. so data the types and
set of values, set operations on those values, so those are the sets of values
for a graph. So here's the constructor of an empty
graph with V vertices. We keep the value v in the instance
variable as usual. Then we create.
An array of size V. And, of bags of integers.
And, store that array in, [inaudible] as the adjacency array of the graph.
Adjacency lists array. And then, as usual.
When we create, a, a, an array of objects. We go through.
And for every entry in the array, we initialize with, a, empty object.
So, after this code, we have the empty bags.
And so that's the constructor and then the other main engine and building graphs is
at edge and so, to add an edge between V and W, we add W to V's bag, and we add V
to W's bag. That's it.
And to iterate through all the vertices adjacent to a given vertex we simply
return the bag which is iterable. This is a nice example, illustrating the
power of abstraction. Because we did the low level processing,
for, that, that's involved, with our bag implementation in one of the early,
lectures. And now we, we get to use that to give a
very compact implementation, and efficient implementation, of the, graph data
structure. So it's really important to understand
this code. And you should make sure, that you study
it. So, as I mentioned in practice.
We're gonna be using this adjacency list representation.
Because all the algorithms are based on iterating over the vertices adjacent to V.
And this gets that done in time proportional to the number of such
vertices. So that's number one and number two, in
the real world, the graphs have lots of num, lots of vertices,
But a pretty small vertex degre. so number one, we can afford to represent, represent
the graph when we use the adjacency list representation because basically our space
is proportional to the number of edges. And number two, we can afford to process
it because our time taken is proportional to the number of edges that, that we
examined, with the ray of edges representation in the adjacency matrix
representation it gets very slow for some very simple task,
But, mostly, it's very slow for iterating over the vertices given to, adjacent to a
given vertex. Which is the key operation.
A list of edges, you have to go through all the edges to find the ones adjacent to
a given vertex. Adjacency matrix, you have to go through,
all possible, vertices adjacent and that's just going to be much too slow in
practice, Because adjacency list gets it done, in
time proportional degree of v, which is much smaller, for the huge graph that we
see in the real world. So that's our basic API.
Next, we'll look at some algorithms that are clients of this API.
