OK, so now we are getting into the meat and bones.
This new subsection of the course, which is going to be about algorithms that are focused on being
used with graphs, so they're not only going to be graphs stuff, but the majority of what we're going
to talk about with these algorithms is going to be associated with graphs.
OK, so what kind of grass are we talking about?
That's what we need to go over in this first lecture is kind of get some things out of the way as far
as explaining what these graphs really are, so we can understand the algorithms that we're going to
go over after this.
So what kind of graphs are we talking about?
Well, you might have used some graphs before and some certain math classes or something where you have
like an x and y axis and some Cartesian coordinates.
We're not talking about those graphs, really.
We're talking about something more aligned with what most people would refer to as graph theory.
And so that is just a collection of vertices and edges.
So you see, we have vertices in green here and edges in blue.
So these are also kind of synonymous with nodes and like the connections between nodes like we did trees,
you know, so we have like a node and then we had like a left and right connection of the binary search
tree to another and another node, you know, like the left child and the right child.
So they're kind of synonymous with that.
You know, here's like a node and here's a connection to another node.
So another important thing is differentiating between directed and undirected graphs.
So here's an undirected graph.
We can basically go from this guy A to B and B to A and then B to C and C to be.
So it's kind of bi directional.
This is not like that, though.
The directed graph, we can go to A to B, but we can't go B to A.
It has some directionality for this edge here, you can see.
And then same thing b c, but not C to be.
And another couple of things.
There are some things called cycles and circuits, a cycle is basically a path where you know, you
choose some kind of starting node here, and that will be the first and last node.
And as you traverse the edges and come back to that node that you will visit, you know you only use
the edges once.
So something like this A to B to C to D to A.
On this, you could also have a cycle if it was like C to B, to A, to B to C, and you don't necessarily
have to have like a square here you could like if you get rid of this edge and this vertex and this
edge and just draw an edge to here.
So it's like a triangle, you know, that would also be a cycle if you want A to B to C back to A.
If we had an inch there and then a circuit is basically like a directed cycle, so we can do that to
restore that.
I just talked about A to B, to C, to D to A.
But we definitely can't do something like C B, a DC because there's directionality to it here.
So basically in directed cycle, this also doesn't have to necessarily be the whole graph like the whole
graph doesn't have to look like this or be, you know, like the whole graph is a cycle.
We can just be a subsection of the graph and we can be talking about a cycle so you can imagine some
more edges and vertices over here.
And this would still be something like that we would refer to as a cycle.
So you might be thinking, Well, is this just like basically trees?
Because we just had, you know, nodes with connections for trees and you pretty much would be right.
The only difference is that a tree is just a graph without a cycle.
So here I'm using that same cycle.
But you know, a tree we could not.
It doesn't necessarily need to be a binary tree.
So, you know, this kind of looks like a binary tree.
We could have like another edge here or something like that.
Or I could even, you know, you could rotate it.
I could even like, make it edge in a vertex like this.
Like, I put a red.
Edge here in another Vertex up here.
And that could still be kind of like a binary choice, even though it looks weird.
But if I draw another line, let's say we have, you know, an edge in a vertex here like I just talked
about, but I draw another edge back to here that could make a cycle going.
You know, you could go A to B to whatever this is back to a that's no longer a tree because it has
a cycle.
So that is the difference between grass and trees.
So how do we represent this in code?
Well, I have a little example graph up here and we're going to be talking about two ways of putting
it in code and adjacency list and an adjacency matrix.
So when I say adjacency, we are talking about something like this.
So a if we start a, we can get from A to B and we can get from A to D.
So B is reachable from A and reachable from A.
We would then say that B and C are adjacent neighbors of A.
So if you look down here.
And I have basically something that is like an array right here.
And then I have linked lists coming off of each one of the indices of disarray.
And so when I look at a for example, again, I have this link list coming off the array and I have
B and which were the adjacent vertices to A.
So that's how the adjacency list is organized is basically you can see here, for example, See has
more neighbors as the B, D, B, E and F.
So that's why we have a link list with all of those adjacent neighbors coming off of this index here
for C.
An adjacency matrix is a great it's a matrix.
So which could be like a two dimensional array or a two dimensional vector or something like that.
It basically says, like, hey, so we're looking again.
I have this column of A. And I'm going to look at all these, I have all of these, all the other vertices
right here.
I put it as zero as in false, if you know, like, for example, here.
A and C.
So C is not adjacent to A..
So for that, I would put a zero for false, but we do have a one here because B is adjacent to a.
Same thing with D D is adjacent a.
So in this cell for Ro D column A. We have a one there for true for C row C column.
We have a zero because a C is not reachable from him.
So same thing with all the rest of them, you know?
See here again, we have B, D, E and F. So B, d e f are all reachable.
That's why those are ones in here.
So why would you choose one over the other?
Well, I'm going to talk about basically two benefits and drawbacks.
Here there are some other ones we can look at, but this is these are the two things that we're going
care about really in the next section, we're doing our algorithms.
So the adjacency list takes up less space, and you can almost just see that visually that it takes
up less space.
So if we're looking at it more specifically, we can say that the adjacency list takes Bigo of the number
of vertices space.
So for a space complexity, it would be big of the number of vertices.
Whereas The Matrix, you know, we see we have a like.
All of our resources right here and all of our resources right here, so we're trying to get the number
of cells in this grid.
It would be this number and this number, which is the same number of times each other.
So this number of times, this number over here, which is basically, you know, this is the number
of vertices.
So it's going to be the big show of the number of vertices squared for our space complexity of the matrix.
So that is a worse complexity and adjacency less.
Therefore, it takes up less space.
Let's look at time complexity, though, so we're talking about searching a given thing, so we want
to know like, hey, like, you know, is C or yeah, let's say.
Let's say is f adjacent to C?
Well, if we go here to the adjacency list, we basically need to be like, OK, you know, maybe we
have this implemented as like a hash table or a hash map or something.
You know, we could be like, All right, I'm a I'm a head of C, so I can jump to see right here cost
and time operation is index it or something like that.
Then I'm like, OK, is f neighbor of C?
Is that adjacent to see?
Well, I have to go through this whole link list and the F is over at the end here.
So ends up boiling down to the adjacency list, having a time complexity for searching for adjacency
of a given.
Vertex being big of the number of vertices she might just have to have, like all of them here in the
linked list, all of the vertices, whereas the adjacency matrix is just constant time because we can
just subscript it.
So, you know, we just have row and then column and it immediately gives us the cell and it's either
one or zero.
So that is then going to be referred to as big of one, which is constant time.
So that's just a basic overview of this.
And that's pretty much all you're going to need to know for this next little section as far as grass.
And then the next video will start getting into some algorithms that not only traverse the graphs,
but have quite quite a few interesting applications as well.
So with that, I will see you in the next lecture.