In this video we break down the four main types of graphs used in computer science: undirected unweighted, undirected weighted, directed unweighted, and directed weighted.
We start with the basic idea of graphs – collections of nodes (vertices) and edges – and then explore each type with clear examples. Learn how these graphs represent real-world relationships like computer networks, airport routes, road maps, and game maps.
Perfect for anyone learning data structures, algorithms, or preparing for coding interviews.
00:00 Introduction to Graphs
00:19 Basic Graph Definition
00:48 Nodes and Vertices
01:01 Empty Graph Example
01:17 Graph Implementation Concepts
02:02 Node Data and Templates
03:22 Adding Nodes
04:00 Adding Edges
04:44 What Graphs Represent
05:36 Graph Use Cases
06:56 Real-World Examples
08:35 Four Types of Graphs
08:52 Undirected Unweighted Graph
10:40 Unweighted as Unit Weights
11:40 Undirected Weighted Graph
13:32 Weighted Graph Benefits
15:52 Directed Weighted Graph
19:50 Directed Unweighted Graph
20:32 Summary of Four Graph Types
21:19 Closing and Future Videos
=-=-=-=-=-=-=-=-=
Thanks for watching!
Find us on other social media here:
- https://www.NeuralLantern.com/social
- Twitter / X: https://x.com/NeuralLantern
- Rumble: https://rumble.com/c/c-3696939
- BitChute: https://www.bitchute.com/channel/pg1Pvv5dN4Gt
- Daily Motion: https://www.dailymotion.com/neurallantern
- Minds: https://www.minds.com/neurallantern/
- Odysee: https://odysee.com/@NeuralLantern:5
Please show your support!
- Buy me a coffee: https://ko-fi.com/neurallantern
- Subscribe + Sharing on Social Media
- Leave a comment or suggestion
- Subscribe to the Blog: https://www.NeuralLantern.com
- Watch the main “pinned” video of this channel for offers and extras
Hello there! Let’s talk about four different types of graphs that you can use and how they relate to computer science.
Okay, so you can see like I’ve got like a blank little graph paper up here.
I’m going to talk about graphs and just the very basic idea of graphs in general
and then show you the four different types of graphs that we have.
about how to implement graphs inside the machine, time complexities, maybe graph algorithms,
and a whole bunch of stuff, terminology, everything. Okay, so the first thing is, I guess I’m going to
assume probably most of you have sort of seen a graph before and you kind of understand a little
bit about it already, but I’ll say that a graph is basically a collection of nodes, also known as
vertices or vertexes, and edges, which are the lines that connect nodes to each other. This screen
See, this is a valid graph.
I’m not talking about the graphing paper.
It’s just an empty graph.
There’s nothing there.
So it’s still valid.
It’s just blank.
Okay, so then what I want to do is start drawing some nodes.
What are the nodes again?
Those are just vertices.
Those are just like little data structure objects you can imagine in the code.
I don’t want to get too far ahead of myself, but imagine that you have a class called graph.
This is just one way to imagine.
We have a class called graph and then a nested class inside of a graph called a node or a vertex
If you want to be more fancy
So the vertex class itself by the way
This is not always going to be the way that you actually do this in your code the other representations that we’ll talk about sooner a little bit easier, but
The vertex class itself needs to basically hold some data
Depending on your implementation it might know about who it’s connected to maybe the graph knows that instead
instead. In my implementations, the graph is going to know everything, but the vertex or the node
itself needs to hold one piece of data. That’s kind of the whole point. So I’m going to say that
the data type that these nodes hold are just integers. So I’m just going to put like a six in
here just to indicate we have one node and the templated data type that it holds is an integer.
And the specific integer for this specific node is just the number six. You can have any template
any template type if you really want to you can people put floats in there you could put a custom
custom class in there whatever you want but i just want to show you that we have a class called
vertex or node and inside of it’s got a template type maybe just to make this a little bit more
clear i’ll say you can imagine inside the vertex class uh there is a template type and we’ll call
it uh i don’t know node node value type or something and we’ll call it data and then up
I’m doing C++ up here.
We have to kind of define the whole graph class as a template class.
Now, of course, you could define the vertex class as the template class,
but if you define the graph class as a template, then it all kind of falls through.
So I’m just going to say class node value type.
And so if you’ve written template classes before in C++,
now you know that the user can instance the graph and at the same time,
specify what is the data type of the stuff that the nodes hold.
the stuff that the nodes hold.
We do the same thing for edges too,
but notice how there are no nodes that are connected to each other.
So we have no edges in this graph.
This is still a valid graph,
but we could just sort of copy a node just for fun and say,
all right, we’ve got two nodes now, two vertices.
They could have the same value if you want.
Graphs are supposed to, you know, support duplicate values in the nodes,
but I’m just going to change the value here.
This is also a valid graph.
You don’t really need edges to have a valid graph.
edges to have a valid graph. This is just something called a something called a graph that is not
connected. We’ll talk about all that terminology and how to detect it in a future video. For now,
I’m just going to say we have like a little graph here, which is kind of boring, but I’m going to
add an edge. An edge is basically just, you know, a little mini data structure that connects two
nodes. Depending on the way you represent this in the machine, which we’ll talk about in future
well, a whole bunch of different ways.
You could imagine this as a full-fledged class,
although that’s not always going to be the way that we represent an actual edge.
So imagine that we have a nested class called edge.
And inside the edge class, we’ve got, you know, some stuff.
We could have a weight, which means the cost of traveling against the edge.
We could have many other properties.
For now, I’ll just try to keep it simple.
is pretty much a collection of vertices and edges and some sort of connection.
What is a graph really for?
Some people at first think that a graph is another way to represent a database.
I’m going to erase this thing over here.
Graphs, you could sort of use them as databases,
but they’re not very good as databases because
it would be really, really slow to search through the graph
to find some piece of data that you’re looking for.
It could be like a linear time database.
better would be to take this graph and add a bunch of rules as you probably have found
in my other videos by now and turn it into a binary search tree.
A binary search tree is lightning fast.
It runs in log time.
Hash tables are faster than binary search trees, but basically a graph is always going
to be way slower than a binary search tree unless the binary search tree is severely
imbalanced.
But that’s something for another video.
Anyway, so we have a graph and it’s not a good database.
What would a graph be good for?
would a graph be good for? Well, graphs are usually pretty good to help you represent
relationships between things. For example, the six and the one, imagine the six is something,
maybe it’s a computer, maybe it’s a city, maybe it’s, I don’t know, like a train station,
and the edges could represent connections. So I’m just going to start changing these values
have some nodes just kind of hanging out off to the side, not really connected to anything.
Maybe not great for your particular use case, but like it’s a valid graph. So I’m just going to,
I’m just going to connect this and try to make this into a better graph.
That’s a little bit more interesting. So we’ve got graphs that do a whole bunch of different
things. Let me change these values real fast. I’ll maybe turn that into a 13 and turn that
So imagine that we have like a little connection here, a little connection here, maybe another
connection here and another one there.
And you know, you are allowed to have connections that sort of look weird, like going from this
six all the way around to this 13.
That’s totally valid also.
So I’ve basically just drawn a random graph, random nodes and random edges.
Imagine that every single node here is a computer in a computer network and imagine every edge
every edge which connects the nodes is just some sort of a connection let’s say a network cable
or a wi-fi signal or something like that so if you imagine it that way then this graph could
represent a network topology a bunch of computers connected together if these were cities and this
is like actually maybe these are airports in cities you could imagine a graph could represent
the relationship between different airports in which planes will fly notice on this graph just
that the uh you know the uh the city number one uh there are no flights connecting it directly to
city 44 but you could probably imagine well if we take a flight to uh from city one to city 10 and
then from city 10 to 44 then we can get from one to 44 we just have to be clever about our connecting
flights um let’s see so we could do like road maps airport maps the worldwide web is basically a graph
at least from a certain perspective electrical circuits that are connected to each other
are connected to each other even game maps what if your character is allowed to stand here in
in space number three on some map and the character is only allowed to travel to space 13 or
space 6 but not directly to space 1 well it could be a map that helps you understand where your
character can go in a game okay so that’s like the basic idea of of what a graph is and uh how it
actual four types of graphs that I’m going to go over in more detail in future videos. Let’s see,
what time is it right now? We got like 10 minutes. Okay, so I can still kind of make this fast.
So the first type of graph that we’re looking at right now is actually something called an
undirected, unweighted graph. Why is it, let’s see, let me write this down first. It’s an undirected,
undirected, unweighted graph. So why is this undirected? Because the edges don’t have direction.
If I was standing in, you know, city six and I wanted to like drive or fly or whatever
from city six to city three, then I should be able to do it because this edge that connects
them doesn’t really say that I have to go in one direction or the other. I could also go to city
three and then just walk right back or fly right back to city six. There’s no direction. So there’s
no direction. So there’s an this that’s that’s why this is an undirected graph. This is an
unweighted graph because we haven’t specified a cost for traveling along an edge. For example,
if you know, if you’re at city three here, and you want to fly to city 13, how much jet fuel
does it cost? How much time does it cost? If three is a computer and 13 is a computer,
and the edges like a network cable, like how much money does it cost to transmit the data?
transmit the data or what is the lag in milliseconds.
You know, you can represent all sorts of things with these edges,
but there’s no value on these edges,
which means there are no weights to these edges.
So that’s why this is an undirected and also unweighted graph.
Uh, the first upgrade that I want to do is just kind of show you what you can
sort of assume about an unweighted graph. This is not always true.
It just depends on who you talk to and what your application implementations are.
So imagine the node that goes from six, sorry, the edge that goes from six to one.
If it’s an unweighted graph, you could just probably imagine that every weight is just a one.
The point being that it always costs the same amount to travel along every edge,
because in an unweighted graph, we don’t differentiate between the different edges
in terms of their costs.
We could just put a bunch of ones on all these edges.
And it would still, you know, basically be considered an unweighted graph.
It depends on who you talk to.
maybe all the weights are zero, maybe all the weights are 10 or whatever.
But, you know, usually I put a one there because I’d like to imagine the cost could just be the number of hops.
So, for example, if I wanted to go from city six to city 10,
I could probably, you know, start at city six and then go to city one and then hop to city 10.
How many actual hops did I do? I did two.
I could also come up with that number by just looking at the sum of all the weights of all the edges.
all the edges. So notice how when I go from six to one, that costs me one weight or one hop. And
then when I go from one to 10, that’s another one. So if you put ones on all the edges in an
unweighted graph, then you’re kind of saying the total cost of some path is really just the number
of hops. So it’s up to you. Anyway, that’s unweighted and undirected. Let’s upgrade this
see we have an undirected and unweighted and i’m just going to duplicate this real fast and change
this to a weighted graph so undirected but also weighted and the thing is as soon as you start
putting numbers on a graph on the edges of a graph well then it’s considered weighted so even even a
graph that has all ones on all the edges you could also call that weighted but now you have the
freedom since it is considered a weighted graph to just assign different values to all the edges
to all the edges. Again, these edges are a class sometimes, or you can think of them that way
inside the graph. And the edge weights themselves are definitely considered a T type, a templated
type, which means, you know, right now I’m clearly typing integers, but you could type some other
data type. You could type floats. You could type some weird data type, like a string.
Whether or not that’s going to be useful depends on your program, you know, what you’re trying to
you know, what you’re trying to do with the graph. But let’s see, I think I’ve added custom numbers
to every single edge. So now this is definitely an undirected, but weighted graph. That’s the
second type of graph that we’re talking about. Okay, what’s what’s cool about a weighted graph?
Well, imagine again, that this is an airport map, where we’re representing relationships between,
you know, cities, like where can we fly and stuff. We’re basically saying at this point,
it’s going to cost you 44 of something.
Maybe this is a graph representing jet fuel or time or frequent flyer points or something like that.
If you consider your edges to be custom classes,
you could even put a whole bunch of different types of values in your graph at the same time
to make it a little bit more flexible.
But for now, we’ll just say there’s one templated type,
which means if we go back up to this code real fast, where was that code at?
Where was that code at?
And we had, you know, our rough idea of, you know, what the, what the graph holds, you
know, it holds like vertices and edges.
We could upgrade this just a little bit to say that there is a, an edge value type.
So I’m going to say class edge value, edge weight type, something like that.
for the edge so that I can save characters. And then here, I’ll change this to a type for the
node. This is why we call it T type. There’s like, we put the keyword template here in C++.
And then sometimes people just use T’s here for these tokens. So I’m just going to say
the type of data that a node can hold is going to be the T node. And then the type of data that
the edge could hold would be the T edge. We’ll call that data. Or we could call that weight,
because usually that data comes into play when you’re traveling along an edge, right? So there’s
traveling along an edge, right? So there’s like two different types here. Anyway, so we got an
undirected and unweighted graph. If we traveled from city six to city one, that costs us 44. But
if you look at the graph a little bit more closely, we could take the longer way around. We could say
go from six to three, and then go from three to 13. And then actually, let me change the color
to orange so that you can see there’s different paths, six to three, and then three to 13,
and then 13 to one, even though we took more hops,
and that might have been considered more expensive
in an unweighted graph,
you can see that the cost of the first path
from six to one, that’s 44.
And the cost of the second path is seven plus three,
that’s 10, and then plus nine, so that’s 19.
So if we take the long way,
it actually costs us less
of whatever we’ve determined this unit is.
You know, less jet fuel, less time, less whatever.
less whatever these graphs in the machine are not necessarily going to be to scale because the
machine in your computer your computer doesn’t really keep track of like the physical positioning
of all these nodes and edges it just can keeps track of the relationship between the nodes and
the edges and the weights and all that stuff so two different paths that we could take to get
from six to one one of the paths is less expensive um or less time costly or just whatever and a graph
data structure can kind of help us figure that out if we’re using an algorithm that understands
weights okay so undirected and unweighted let’s add direction so um i’m going to erase this stuff
right here real quick and in an undirected graph remember you can just kind of go in either
direction along any edge but in a directed graph every single edge needs to have a direction so as
I change one of the edges to have direction, then I must change all of the edges to have direction
as well. So I’m just saying, okay, as soon as I did that, now this is an invalid graph
because some of the edges don’t have direction. So now I need to fix everything. So I just,
I’m going to arbitrarily and randomly choose a direction for every single edge like this.
And then as soon as I’m done, I’m going to deal, I guess, with that giant edge
that giant edge. So I’m going to go like that. So let’s see, all the edges seem to have direction.
Now I’m just going to hand draw an arrow on one side of this giant edge. Okay. So this is directed
and also weighted. What can we do with the directed graph? Well, it just basically tells
you which direction you’re allowed to travel in. What if you have an airport where city six can
only fly to city one, but city one, for some reason, never flies to city six. You got to take
take like the long way you got to go from city one to 13 to three to six that’s something that
a graph could help you represent what if your character in your game can only go in one direction
but not the other direction okay no problem i mean that’s pretty much it you’re only allowed
to travel in the same direction as the edge points but now we have a graph that is a lot less
flexible because for example before we used to be able to go from city uh 10 to city 44 and then
then come back again later if we wanted in the opposite direction. We can no longer do that
because this edge only goes to 10. It doesn’t even go to 44. We can’t even ever actually get to 44.
How do you sort of solve that? Well, just add another edge in the opposite direction.
In graphs, you are allowed to do something called a parallel edge,
which just basically means, you know, two edges between the same pair of nodes that just point
in the same direction. You’re also allowed to do, you know, opposite facing edges. So
edges so i just added a second edge there going from 10 to 44 and now if i was you know hanging
out in city 10 i could just go back and forth between city 10 and 44 as much as i wanted to
oh i forgot to add an edge weight for that new edge which means i wrote down an invalid graph
so i’m just going to say two so uh maybe the wind is blowing in in your favor when you’re going from
city 10 to city 44 maybe it’s blowing against you if you’re talking about city 44 to city 10 you
you know whatever but you just have to have edge uh edge weight on every single edge
okay so uh that’s directed and also weighted um and you can probably imagine previously when we
had an undirected um graph when there was just like you know one edge going between uh two nodes
and there was no direction on it like you know 44 to 10 if we just had like one edge with no
have two edges each going in the opposite direction so we have directed and weighted i think the last
thing that we didn’t do was directed and unweighted right so we have let me just double check real
fast here we have undirected and unweighted and then we had undirected and weighted and then
directed and weighted okay so now let’s do um i’m getting lost already oh my gosh i can’t believe i
I saw undirected and unweighted so we did undirected twice already undirected so we’re
going to do directed and unweighted next okay so the next graph a little bit less useful than
what we’re looking at this this type of graph is a little bit more useful we’re going to do
directed and unweighted oh my god okay directed and unweighted so directed and unweighted you
Directed and unweighted, you can imagine, just means we get rid of all these weights.
And then we keep the direction on all the edges.
So this means we can keep track of where we’re allowed to go, if we’re pathfinding or just whatever.
But we don’t really know what it costs to travel between the different graphs.
So that’s directed and unweighted.
Let’s see here.
I’m going to just duplicate this or just make a new blank slide.
Okay, undirected, oh gosh, I’ve got pink letters.
Let’s see, undirected plus unweighted.
And we’ve got undirected plus weighted.
And then we’ve got directed plus unweighted.
I don’t think I’m writing these down in the same order,
but that’s okay.
And then we’ve got directed plus weighted.
So basically, you know, four types of graphs
that we can talk about.
In future videos, we’re going to go over graphs
in more detail.
We’ll talk about graph terminology,
maybe some pathfinding algorithms.
And yeah, so this is just a basic intro.
How much time do we spend already?
Oh God, we spent so much time.
Spent like 22 minutes.
Dang, man, even the smallest thing takes time.
So I’ll see you in a future video
when we talk more and more and more about graphs
and other data structures concepts.
Thanks for watching this video.
I hope you learned a little bit of stuff
I hope you learned a little bit of stuff and had a little bit of fun.
I’m out of here.
Go.
Hey, everybody.
Thanks for watching this video again from the bottom of my heart.
I really appreciate it.
I do hope you did learn something and have some fun.
If you could do me a please, a small little favor,
could you please subscribe and follow this channel or these videos
or whatever it is you do on the current social media website that you’re looking at right now,
it would really mean the world to me.
And it’ll help make more videos and grow this community.
So we’ll be able to do more videos, longer videos, better videos,
or just I’ll be able to keep making videos in general.
So please do me a kindness and subscribe.
You know, sometimes I’m sleeping in the middle of the night
and I just wake up because I know somebody subscribed or followed.
It just wakes me up and I get filled with joy.
That’s exactly what happens every single time.
So you could do it as a nice favor to me or you could you control me if you want to just wake me up in the middle
And I just subscribe and then I’ll just wake up. I promise that’s what will happen
Also, if you look at the middle of the screen right now
You should see a QR code which you can scan in order to go to the website
which I think is also named somewhere at the bottom of this video and
It’ll take you to my main website where you can just kind of like see all the videos
I published and the services and tutorials and things that I offer and all that good stuff and
and if you have a suggestion for clarifications or errata or just future
videos that you want to see please leave a comment or if you just want to say hey
what’s up what’s going on you know just send me a comment whatever I also wake
up for those in the middle of the night I get I wake up in a cold sweat I’m like
it would really it really mean the world to me I would really appreciate it so
enjoy the cool music as as I fade into the darkness which is coming for us all.
Thank you.
I’m going to go ahead and get started.
Thank you.
Hello there.
Let’s talk about the four types of…
Hello there.
