- Introduction to graphs.
Introduction to graphs.
I've been so excited.
I'm waiting for this part.
And now it's here.
Introduction to graphs.
I love graphs. Okay?
I really do.
So let's get started.
And to be honest, we've already talked about graphs.
Do you remember?
Trees, trees are graphs.
Special kind of graph, but they're graphs.
And when we were talking about trees,
we introduced the terms node,
or sometimes vertex.
I'll use them interchangeably.
The book talks about nodes.
I'm sort of conditioned to say vertex.
So if I mix them up, please forgive me.
I'll try to say node.
We have edges, edges connect nodes.
Each edge has exactly two end points that are nodes.
We can count the number of edges that a node has.
The number of edges that are incident to the node.
That's called the degree of the node.
There are paths in a graph, just like we have paths
in a tree that we can traverse through a number of vertices,
one or more to get from one point to another.
Paths exist in graphs, just the same.
And we also talked about cycles.
Particularly in the context of the trees,
trees don't have cycles, and that's why we brought them up.
That's one of the conditions of being a trees
is you do not have cycles.
So let's go back to some of those slides about trees.
So here we have a lovely tree.
It's a structure consisting of nodes and edges.
And these are the nodes and these are the edges.
Okay?
And so if we take the set of all possible graphs,
trees are a subset of that set.
What's special about trees?
Well, again, they're, acyclic.
What do I mean by that?
Here is a very bad tree.
It has a cycle.
It goes round in a loop like this here.
And you can pick any pair
of nodes on that yellow loop, say A and M.
And we have more than one path that connects A and M.
So we have a path that goes through B and G.
We have a path that goes through D and H.
That's two paths.
Two is not one.
They're supposed to be exactly one.
So that's a bad tree.
But it is perfectly valid graph.
So if we relax the condition
that there must be exactly one path
between any pair of nodes, then we have a graph.
So all trees are graphs, but not all graphs are trees.
Trees are that special case of acyclic connected graphs.
So graphs may or may not contain cycles.
They don't have to, they may or may not.
And graphs may or may not be connected.
So there may be more than one component in a graph.
So it's perfectly fine to have an isolated vertex
or two little trees that have no edges between them.
That's still a graph.
That's fine.
So we need a little notation here,
and I'll keep it to a minimum.
We denote the set of all nodes by the big letter V.
That stands for vertex.
And we denote the set of all edges with a big letter E.
Okay?
And you'll remember when we talked about sets,
we talked about this notation that looks like absolute value
but it means cardinality of a set
when we're talking about sets.
And so if we take the cardinality of the set V,
that gives us the number of nodes in a graph.
And if we take the cardinality of the set E,
that gives us the number of edges in a graph.
And that's I think all the notation to throw at you today.
So we've got this graph here.
Let's figure out what the vertex set is.
Well, it's A, B, C, D, E, F.
So there we go.
A, B, C, D, E, F, that's the vertex set.
And what's the set of all edges?
Well, we need some way to refer to the edges,
and it's perfectly fine if we just refer to them
by their two end points.
Now this is an undirected graph.
We'll get to directed graphs in a minute,
but it doesn't matter.
We can call this edge here BA or AB.
Same edge, okay?
So we're gonna have a set of edges.
That's AB, BC, CD, CF, BF, FA, and so on.
So there's our edge step.
So what's the cardinality of these two sets?
Well, we got one, two, three, four, five, six elements
in the vertex set, or the edge or the node set.
And we have one, two, three, four, five, six, seven, eight,
nine in the edge set.
So we've got six nodes and nine edges.
Now all of these are graphs.
Two of them are trees.
Which two are trees?
This one's a perfectly good tree.
It's got one root, one leaf.
That's fine.
This is not a tree because it's not connected.
This is not a tree because it has a cycle.
This is a perfectly good tree right here.
And we could take all of these together, all nine
of these nodes,
and that constitutes a perfectly fine graph too.
So again, graphs needn't connected.
Graphs can include self loops.
So it's possible in a graph to have an edge
that connects a node to itself.
We're not gonna worry about those,
many problems ignore or prohibits such loops anyways.
But I just thought I'd mentioned that that's a possibility.
So let's talk about adjacency.
What does it mean to be adjacent?
Well, here, A and B are adjacent.
Why? Because there is an edge that connects them.
A and B share a common edge, that makes them adjacent.
Okay?
There is a direct path
that exists from one node to the other.
Now we can also add direction to our edges.
That complicates things a little bit.
So in the case on the top, we have an undirected edge.
A is adjacent to B, B is adjacent to A.
But in the lower figure, C is adjacent to D
because I can get to D from C.
But D is not adjacent to C.
There's no way back.
It's a one-way street.
That's a directed edge.
We're gonna look at directed graphs in a minute.
Well, this is a directed graph here.
We're gonna look a bigger ones.
So this is an undirected edge.
This is a directed edge.
Again, you can think of the directed edges
as one-way streets.
And we don't mix directed and undirected edges
in the same graph.
It's either one or the other.
So think of these as two separate graphs,
one that's undirected, one that's directed.
And we can always add to a directed graph
so that there are two ways to go.
So this is perfectly fine.
We have two directed edges,
one from C to D and one from D to C.
So in the case on top, C is adjacent to D,
but D is not adjacent to C.
But here, C is adjacent to D
and D is adjacent to C.
Now we talked about the degree of a node,
meaning the number of edges that are incident to it.
But when we have directed graphs,
we can also talk about the in degree
and the out degree.
The in degree, as you might expect,
is the number of edges that flow into that node.
And the out degree is the number of edges
that flow out from that node.
Okay.
So when we talk about in degree or out degree,
which we will later, not in this lecture,
but in a later lecture, that's what that means.
So here, we have a connected cyclic graph, right?
There's a cycle here.
This whole big thing is a cycle.
Okay?
And it's connected.
For any pair of nodes, there's some path that connects them,
or more than one path as the case may be.
Now, this is a directed cyclic graph.
It contains a cycle, but it's not this.
This is not a cycle here because I can go
from E to D, to D to A, to A to B,
but I can't get back to B, at least not directly.
This is a bigger cycle here, all the way around
because I can travel in this cycle.
And then there's also a cycle here.
Okay. So this is a directed cyclic graph.
Well, we can also add weights to our edges.
Weights could represent many different things.
They could be distances.
So if this were like a map,
and we'd abstracted some features from a map,
these might be cities and miles between the cities.
They could be capacities.
Let's say these were again, cities,
and this was the flow of electricity or water
to and from different places
in a network of pipes or a network of wires.
They could be great many other things as well,
costs or transition probabilities and so on.
It all depends on the particular problem
that's being modeled.
But the important thing is that we can associate
some scalar value,
some integer or real number, typically with each edge.
Okay. And that's called a weighted directed graph now.
Here's an example.
This is an undirected graph that has weights.
Showing a concrete example
of towns in Vermont and the distances between them.
So here's Burlington, it's three miles
to Winooski and three miles back
from Winooski to Burlington.
It's 67 miles down to Rutland,
and 67 miles back up from Rutland to Burlington.
39 miles to Montpelier and so on.
So this is a case where the weights
of the edges represent distances.
They don't have to, but this one does.
Now, this is an important point,
and it can confuse people sometimes.
And that is it does not matter.
It does not matter how we draw our graph
on a piece of paper or in a PowerPoint
or keynote presentation.
The orientation of the vertices is immaterial.
Okay.
So what we're looking at here are identical graphs.
The graph on the left is identical
with the graph on the right
because we don't care where the vertices are located
on that 2D plane.
It doesn't matter.
Okay. So what's really important here is these two graphs.
Do they have the same vertex set?
A, B, C, D E F.
Yes, they do.
Do they have the same edges?
Go and check.
Yes, they do.
Are are the edges oriented the same way?
For example, does the edge between A and B go from A to B?
Yeah, sure. It does.
Do they all have the same weights?
Yup. Six, six, nine, nine.
You can check.
So it doesn't matter how we draw them.
These are identical graphs.
Okay.
For all of our purposes, these are identical.
So we've got this graph, and this is a course on algorithms.
So we want to be able to do algorithms with graphs.
So we're gonna need some representation for the graph.
So what's a good data structure to use for a graph?
Well, let's think about what properties a data structure
would have to have.
Want to capture the edge set.
It would want to capture the node set.
You'd want to capture
all the adjacency relationships, right?
If it were a directed graph,
you'd want to capture the orientation of all of the edges.
And if there were a weighted graph,
you want to capture all the weights.
So we have to have a way of doing all those things.
Okay?
And it turns out that there are a lot of ways to do this.
And some approaches are suitable in some use cases,
and some suitable in others.
Three common ones are the adjacency list,
the adjacency matrix and the incidents matrix.
But we're only gonna talk about the first two.
I'm gonna save incidence matrix for another lecture.
So let's take a look and see what is an adjacency list.
So we've got this graph over here on the left,
and we're gonna build
our adjacency list over here on the right.
And notice that we have a place, an entry
for each vertex, each node in our graph, A through F.
And so it's pretty simple.
We go take a look at A.
We say what's adjacent to A?
B and D.
So guess what goes there? B and D.
All right, what's adjacent to B?
A, E, and C.
AC, and you go there.
What's adjacent to C?
B, E, and F.
And so on.
And so that's our adjacency list.
And from this adjacency list,
we could reconstruct our graph.
How would we do that?
Well, let's erase our graph and do it.
So if we just look down this column,
we see what our node set is.
We know we've got these six nodes,
so let's go ahead and draw those.
And I'm, yes, I'm drawing them
in exactly the same place as they were in before.
But again, it doesn't really matter how you draw the graph.
If I position these differently,
we'd still get the same result.
So now what do we do?
Now we take a look at the entry for A.
We see that A is adjacent to B and D.
So what do we do?
We draw an edge between A and B,
in between A and D.
And now we check A off the list.
Now we move on to B.
What's on the adjacency list for B?
A, C, and E.
So we've already got this edge drawn here,
so we don't need to draw it again,
but we need do need to draw the other two edges.
So let's put them in and check B off the list.
What's adjacent to C?
B, E, and F.
See, I got, I got this edge drawn already,
but I need to draw these two edges.
So let's do that and check that off the list.
And you just proceed down the list.
And by the time you get the poor, old F here
at the end of the list, you've already drawn all the edges.
So you can see there's some redundancy in an adjacency list.
And at this point, there's nothing else to do.
So we're done.
So we've recovered our graph from the adjacency list.
How much space does this take?
If we were to analyze this in terms of the space complexity,
the worst case would be if we had a number of vertices
and every vertex was connected to every other vertex,
or every node was connected to every other node.
In which case, we'd have a space requirement of big O
of V plus E, or I should say the cardinality of V
and the cardinality of E, okay?
What's the complexity of finding
if two vertices are adjacent?
Well, how would I do that?
Let's say, I want to know, is E adjacent to D?
Well I'd go look up the entry for E,
and then I'd run across here,
and I'd run through this list, which might be a linked list.
And if I encountered D in that list,
I would know that E is adjacent to D.
I wouldn't need to go check the entry for D
and make sure it's there also
because if the adjacency lists is properly constructed,
then the list really represents the edge twice.
DE and ED.
So either one we check, it gives us the right answer.
So the worst case there is we have to run through
an entire list here that could be all the vertices.
So the worst case for a query like that is big O
of the cardinality of V,
the number of vertices that we have.
Now, let's look at another data structure
for representing a graph.
This is called the adjacency matrix.
And here we have a matrix with the rows and columns labeled
with the node labels.
So we have all these columns, A through F,
and all these rows, A through F.
And so with six nodes in our graph,
we'd have a six by six matrix.
If we have cardinality of V nodes,
then we're going to have cardinality
of V squared cells in our matrix.
So what do we do?
We put a zero in each entry of our matrix,
where the two nodes are not adjacent.
And if they are adjacent, then we put a one.
So M here represents the matrix.
I and J subscripts indicate the row and the column.
And so to take an example, if we have A is adjacent to B,
then we'd put a one here.
Okay. So let's do that.
Let's build this out.
So this first row, A is not adjacent to A
because there's no self-loop.
We're going to ignore those for now.
A is adjacent to B.
It's not adjacent to C,
but it is adjacent to D,
it's not adjacent to E and it is not adjacent to F.
Next row.
This is what's adjacent to B, A, and C and E.
A, C, and E, okay?
And similarly for the other rows in our adjacency matrix.
Now, there's some interesting properties
of the adjacency matrix.
The sum of any row or column gives the degree
of the corresponding nodes.
So if I take the sum of this column here for B,
I get three, and sure enough, the degree of B is three.
There are three edges incident to be.
If I do the same for D,
I sum that column, I get two.
And sure enough, the degree of D is two.
So that's a nice property for our adjacency matrix.
And if we sum over all of the elements in the matrix
and divide by two,
we get the total number of edges in our graph.
Now you may have noticed that this table is symmetric
about the diagonal.
So this upper triangle, this is called the upper triangle
of a matrix, and the lower triangle,
are mirror images of one another.
This graph is symmetric.
Because in an undirected graph,
if A is adjacent to B,
B as adjacent to A.
So here's a one here, and there's gotta be a one here
because it's an undirected graph.
So in the case of undirected graphs,
we would expect our adjacency matrix to be symmetric.
So we could really ignore the lower triangle
of the adjacency matrix.
All of the information about the graph
is encoded in the upper triangle here.
So if we wanted to, we could ignore the other values.
And you'll also notice that since this graph
has no self-loops
and then the ones that we're gonna look at,
they're not going to have self loops,
we expect to see zeros along the diagonal.
So no node is connected to itself.
Now, we see that this has a space complexity of big O
of the cardinality of V squared
because this is V.
This is V, the cardinality of V.
And so we take the product and we get V squared.
But what time does it take to perform a query to see
if E and B are adjacent?
We just look up EB, and we get a one.
So we know they're adjacent.
And that's fast.
Just like looking up a value in a vector
takes place in constant time,
looking up in a matrix takes place in constant time.
So this is a constant time operation.
So that's a lot faster than the adjacency list.
It takes more space,
and it may not be as efficient in terms of space,
especially if you have a lot of vertices
and not a lot of edges,
you get a what's called a sparse matrix,
but the lookup is very fast.
So that's nice.
Let's add the complication of directed graphs.
What do we do with directed graphs?
Well, you'll recall that in this graph,
A is adjacent to B,
but B is not adjacent to A.
So in the case of the adjacency list,
it's just gonna be an abridged version
of the adjacency list that we had before.
Before we would have an adjacency from A to B
and from B to A.
Here, we're just gonna have the one.
So A is only adjacent to B.
It's not adjacent to D because I can't get from A to D.
B is only adjacent to C
because this directed edge only goes to C.
There's no way I can get from B directly from B
to any other node in the graph.
C is only adjacent to E and F, and so on.
D is adjacent to A.
E is adjacent to B and D.
F is adjacent to E.
And so that's our adjacency list for directed graphs.
It's very similar, almost identical.
Okay.
Now what do we do in the case of the adjacency matrix?
Well, we put a zero if they're not adjacent,
and a one if they are adjacent.
Same thing as before except now,
we're just gonna have fewer one entries
because we have fewer adjacencies in this graph
because of its directed nature.
So in the case of A,
A is adjacent only to B and zeros for all the other entries.
B is adjacent only to C and zero for all the other entries.
And so on.
Now, unlike the case of the undirected graph,
we wouldn't typically expect the upper lower triangles
of the graph to be mirror images of one another.
In fact, they usually aren't.
The matrix is not symmetrical
because these directed edges are not symmetrical.
I can only go one way along a directed edge.
I can't go back.
So they're not symmetrical.
And so that's reflected in the adjacency matrix.
Now let's look at the case of weighted directed graphs.
And now here are the adjacency list data structure
gets a little cumbersome
because for each entry in the list,
we also have to include the weight.
So our first entry is adjacent to B with a weight six.
Now we have to put B and six
in its own little capsule there.
And C, B is adjacent to C with a weight of nine.
So now we have C, 9.
C is adjacent to two other nodes.
E and F, E with a weight of two
and F with a weight of eight.
Okay. And so on.
So that's kind of inelegant, I think,
but let's take a look and see how we would do the same thing
with an adjacency matrix.
With an adjacency matrix, we still use a zero
if the nodes are not adjacent.
But if they are adjacent, instead of putting a one,
we put the weight.
We put the weight right in the matrix.
So W of I and J represents the weight of the edge
connecting I and J.
The matrix notation is the same here.
So let's fill in some of these.
We've got A is adjacent to B with weight six.
So we're gonna put a six here and zeros elsewhere.
Let's do that.
B, again, has a weight of nine going to C.
So we're gonna put a nine here.
The rest will be zeros.
And so on.
Again, this is a directed graph.
So you would not expect any symmetry here.
And you can see that the upper and lower triangles
are not mirror images of one another.
So which data structure is best?
Well, it depends, depends on a lot of things.
And sometimes adjacency list
is the right data structure to choose.
And sometimes, the adjacency matrix
is the right data structure to choose.
If you take a look at their relative complexities,
we've already said that the space complexity
of the adjacency list is big O of V plus E,
cardinality of V plus cardinality of E.
And for the adjacency matrix,
it's the cardinality of V squared.
We've seen that the query takes in worst case,
big O of the cardinality of V times in the adjacency list.
And it's a constant time operation for the adjacency matrix.
Adding a vertex is super easy for an adjacency list.
We just pop another entry into the list.
But for an adjacency matrix, if we want to add a vertex,
then we have to rearrange our matrix and add row and column.
So that becomes a big O of cardinality of V squared
kind of an operation.
Adding an edge though, is a constant time operation
for both adjacency lists and adjacency matrix.
So if you know the structure ahead of time,
oftentimes, adjacency matrix
is going to be the better choice.
If you don't know the structure ahead of time,
or you're gonna be making changes,
sometimes adjacency list is the better choice.
But again there's no hard and fast rule of thumb.
So that's all for now.
We're going to cover some supplementary topics
in another lecture,
and then we're gonna move on to some graph algorithms.
That's all for now. Thanks.