In this section, we are going to start talking about the graph.
Data structure and graphs are an important data structure for us to understand because it allows us
to begin implementing an algorithms such as the Dijkstra algorithm breadth first search and depth first
search, which we will see in the coming sections.
But for us to be able to understand how graphs work, there is some terminology that we need to first
go over, such as what a what the vertices are and what edges are.
So if we create a simple graph, we have nodes as such.
And so these are going to be our.
Vertices.
So our vertices can also be just called nodes.
And so what edges are going to do is they're going to connect the vertices.
So we can have an edge and we'll give these labels A, B, C, and D so we can have an edge going from
A to B, from B to D, from D to A and from A to C.
So all of these are R edges and I'll label them E for edge.
So you can see where this might be useful for us in a real world scenario.
So assume that our vertices here is a city and then we have an edge and it's a road.
So we have a bunch of cities and we have a bunch of edges, a.k.a. roads.
So if these are our roads and these are our cities, so we'll say C, C and C, and then r, r and R
for our roads.
Well, now we can create or use an algorithm to figure out the quickest way to get from this node or
this city to this city, because this road and this road might have more traffic than taking these three
roads.
So that's just one use case for a graph, right?
So think of it as cities and then you take the edge a.k.a the road to get to the next city and so on
and so forth until you're able to hit your desired destination.
So we have some additional terminology that we can go over.
And what we have is we have adjacent, vertices
adjacent.
Vertices.
And this is the what connects the nodes.
So a direct edge.
Between the nodes, a.k.a. the vertices.
We have the degree degree of a node.
And this is the number of edges going to a vertex.
So in this city.
Note up here.
The degree would be two because we have two edges going into this city.
We have the path and this is how to get from one.
Node to another.
Oh, there you go.
How to get from one note to another.
We have our connected graph.
And this is the path.
This means that our graph has a path between.
Every two nodes.
And we also have a complete graph.
And this means that there is a direct edge.
Between.
Any.
To.
Protects.
So if we created a very simple graph with three, three nodes and we did this, this would be a connected
graph because we have a path between every two vertices we can get from any vertices here to another
vertices.
And then if we add it in this edge, will we now have a complete graph because we have a direct edge
between any two vertices.
So in this case we can any, any node can get to any other vertex directly.
So that is what a complete graph is.
So now we have different types of graph.
And there's quite a number types of graphs that we can talk about.
And we have an undirected graph.
And undirected means that you can go from one node.
To another.
And it's always both ways.
We have a directed graph.
And in this case only the A node can go to the B node.
So.
And here the edge only goes.
From Node A to B?
Right.
So that's the difference here between our undirected and our directed and the undirected.
We can go either from A to B or B to A, but as soon as we have A directed, we can only go in this
case from A to B, we cannot go from B to A.
We also have an unweighted graph.
So that means we can go from a
I don't want to have a directed.
We can go from A to B to C, and there are no weights associated with any of these edges.
So you can imagine a weighted graph is the counterpart to this.
And if we have A, B, C, and this is still an undirected graph, we can have a weight of five and
we can have a weight of three.
So from A to B, it's going to cost us five and from B to C, it will cost us three.
So an easy way to think of this is think of weights.
As distance.
Or time.
So if we go back to using a city for an example, so we have City A city B, city C, and we'll say
City D.
But we have, say, six.
Three.
Two, and let's add one here and we'll say that this is one.
Well, for us to get from A to DH.
Yeah, let's change it from one.
Let's make it.
Five just that way.
It's not as obvious for us to get to a2d here.
We would go from A to C, so A to C where our weight is equal to five and then we would go from C to
D, where our weight equals two.
So our total weight for that path would be seven.
Whereas if we went A, B, C to D, then we would have six plus three plus two obviously, which is
nine.
So that would not be the most efficient path for us to take in this case to get from A to D.
So think of that back to the going from city to city you could think of these weights is how much traffic
there may be.
So how much time it will take if we go a certain route.
So we want to find obviously the most optimal path which we can do.
Using algorithms such as Dijkstra's or breadth first and depth first.
So the last thing that we can do is how we can represent a graph data structure.
And what I'm going to do is use an adjacency matrix to represent.
Nodes and our edges.
So let's imagine that we have A, B, C, and D for our nodes.
So what we can do is we can create A matrix, A, B, C, and D, and then we can also have a.
B, C, and D here and inside we create our matrix.
And that was not what I wanted to do.
So in here, we're creating our matrix.
And so so that we can visually represent this.
Let's do A, B, C, and D, and we'll create our graph from above.
So we see that we go from A to B so we can put a one and we go from A to C.
So we put a one.
And since there is nothing, there's not a path from A to a meaning.
This is what that would look like.
So we don't have that.
So now we can go to the B node we see we connect to from B to A and also from B to C, C connects to
B and C connects to D, and then D only connects to C, And this is an example of an unweighted undirected
graph, and this is how we were able to represent this very simply with what nodes connect to what other
nodes via the edges.
So our representation in here is our edge if it exists or not.
Otherwise everything can be initialized to zero to indicate that there are no edges between those two
nodes.
So now that we have a good understanding of how graphs work and how we can represent a graph, we will
begin implementing in our own graph and the next lecture.
And if you have any questions at any point, please feel free to ask them in the Q&A section.