4 Graph Types: Undirected vs Directed, Weighted vs Unweighted

Neural Lantern

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  graphs, graph types, data structures, computer science, undirected graph, directed graph, weighted graph, unweighted graph, graph theory, vertices, edges, nodes, algorithms, coding tutorial, programming, binary search tree, network topology, pathfinding  =-=-=-=-=-=-=-=-=  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

Transcript

00:01Hello there, let's talk about four different types of graphs that you can use and how they

00:06relate to computer science. Okay, so you can see like I've got like a blank little graph paper up

00:18here. I'm going to talk about graphs and just the very basic idea of graphs in general and then show

00:24you the four different types of graphs that we have. In future videos, we're going to talk about

00:28how to implement graphs inside the machine, time complexities, maybe graph algorithms, and a whole

00:34bunch of stuff, terminology, everything. Okay, so the first thing is, I guess I'm going to assume

00:39probably most of you have sort of seen a graph before and you kind of understand a little bit

00:42about it already, but I'll say that a graph is basically a collection of nodes, also known as

00:48vertices or vertexes, and edges, which are the lines that connect nodes to each other. This screen right

00:55here that you see, this is a valid graph. I'm not talking about the graphing paper, it's just an

01:00empty graph, there's nothing there. So it's still valid, it's just blank. Okay, so then what I want

01:06to do is start drawing some nodes. What are the nodes again? Those are just vertices, those are just

01:12like little data structure objects you can imagine in the code. I don't want to get too far ahead of

01:19myself. But imagine that you have a class called graph. This is just one way to imagine we have a

01:24class called graph and then a nested class inside of a graph called a node or a vertex, if you

01:30want

01:30to be more fancy. So the vertex class itself, by the way, this is not always going to be the

01:36way that

01:36you actually do this in your code. The other representations that we'll talk about sooner, a

01:41little bit easier, but the vertex class itself needs to basically hold some data. Depending on your

01:48implementation, it might know about who it's connected to, maybe the graph knows that instead. In my

01:53implementations, the graph is going to know everything. But the vertex or the node itself needs to hold one

01:59piece of data. That's kind of the whole point. So I'm going to say that the data type that these

02:04nodes

02:04hold are just integers. So I'm just going to put like a six in here, just to indicate we have

02:08one node, and

02:10the templated data type that it holds is an integer. And the specific integer for this specific node is just

02:18the

02:18number six. You can have any template type if you really want to, you can people put floats in there,

02:23you can

02:23put a custom custom class in there, whatever you want. But I just want to show you that we have

02:27a class called

02:29vertex or node. And inside of it's got a template type, maybe just to make this a little bit more

02:33clear. I'll say you

02:35can imagine inside the vertex class, there is a template type, and we'll call it to I don't know node,

02:43node value type or

02:44something, we'll call it data. And then up here, we have to I'm doing C++ up here, we have to

02:50kind of define the

02:51whole graph class as a template class. Now, of course, you could define the vertex class as the template class.

03:00But if you

03:00define the graph class, as a template, then it all kind of falls through. So I'm just gonna say class

03:05node value type. And so if

03:07you've written template classes before in C++, now, you know, that the user can instance the graph. And at the

03:13same time, specify what is the data type of the stuff that the nodes hold, we do the same thing

03:18for edges

03:18too. But notice how there are no nodes that are connected to each other. So we have no edges in

03:23this

03:23graph. This is still a valid graph. But we could just sort of copy a node just for fun and

03:29say, Alright, we've got

03:30two nodes now, two vertices, they could have the same value if you want. Graphs are supposed to, you know,

03:37support duplicate values in the nodes, but I'm just going to change the value here. This is also a valid

03:42graph, you don't really need edges to have a valid graph. This is just something called a something

03:48called a graph that is not connected, we'll talk about all that terminology, and how to detect it in

03:53a future video. For now, I'm just gonna say we have like a little graph here, which is kind of

03:57boring, but I'm

03:58going to add an edge. An edge is basically just, you know, a little mini data structure that connects

04:03two nodes. Depending on the way you represent this in the machine, which we'll talk about in future

04:08videos, the edge could be represented in a whole bunch of different ways. You could imagine this as

04:15a full fledged class, although that's not always going to be the way that we represent an actual edge.

04:20But so imagine that we have a nested class called edge. And inside the edge class, we've got

04:28some stuff. We could have a weight, which means the cost of traveling against the edge. We could have

04:35many other properties. For now, I'll just try to keep it simple. I just want you to see that the

04:39graph is

04:40pretty much a collection of vertices and edges and some sort of connection. What is a graph really for?

04:46Some people at first think that a graph is another way to represent a database. I'm going to erase this

04:51thing over here.

04:53Graphs, you could sort of use them as databases, but they're not very good as databases because

04:59it would be really, really slow to search through the graph to find some piece of data that you're looking

05:04for.

05:04It could be like a linear time database. Much better would be to take this graph and add a bunch

05:10of rules,

05:10as you probably have found in my other videos by now, and turn it into a binary search tree.

05:15A binary search tree is lightning fast. It runs in log time. Hash tables are faster than binary search trees,

05:23but basically a graph is always going to be way slower than a binary search tree, unless the binary search

05:27tree

05:27is severely imbalanced, but that's something for another video. Anyway, so we have a graph and it's not a good

05:35database. What would a graph be good for? Well, graphs are usually pretty good to help you represent

05:40relationships between things. For example, the six and the one, imagine the six is something.

05:48Maybe it's a computer. Maybe it's a city. Maybe it's, I don't know, like a train station.

05:56And the edges could represent connections. So I'm just going to start changing these values on these nodes here.

06:02It is totally valid to have some nodes just kind of hanging out off to the side, not really connected

06:07to anything.

06:08Maybe not great for your particular use case, but like it's a valid graph. So I'm just going to, I'm

06:12just going to

06:12connect this and try to make this into a better graph. That's a little bit more interesting.

06:17So we've got graphs that do a whole bunch of different things. Let me, uh, change these values real fast.

06:25I'll maybe turn that into a 13 and turn that into a 44. I'm just inventing random numbers.

06:31So imagine, uh, that we have like, uh, I dunno, a little connection here and a little connection here, maybe

06:38another connection here and another one there.

06:41And you know, you are allowed to have connections that sort of look weird, like going from this six all

06:46the way around, uh, to this 13.

06:49That's totally valid also. So I've basically just drawn a random graph, random nodes and random edges.

06:56Imagine that every single node here is a computer in a computer network and imagine every edge, which connects the

07:01nodes, uh, is just some sort of a connection.

07:04Let's say a network cable or a wifi signal or something like that.

07:08So if you imagine it that way, then this graph could represent a network topology, a bunch of computers connected

07:13together.

07:14Uh, if these were cities, uh, and this is like, actually maybe these are airports in cities, you could imagine

07:21a graph could represent the relationship between different airports in which planes will fly.

07:25Notice on this graph, just by looking, you can see that the, uh, you know, the, uh, the city number

07:31one, uh, there are no flights connecting it directly to city 44, but you could probably imagine.

07:36Well, if we take a flight to, uh, from city one to city 10, and then from city 10 to

07:4044, then we can get from one to 44.

07:43We just have to be clever about our connecting flights.

07:47Um, let's see. So we could do like road maps, airport maps.

07:50The worldwide web is basically a graph, at least from a certain perspective, electrical circuits that are connected to each

07:56other, uh, even game maps.

07:58What if your character is allowed to stand here in, in space number three on some map and the character

08:06is only allowed to travel to space 13 or space six, but not directly to space one.

08:11Well, it could be a map that helps you understand where your character can go in a game.

08:16Okay.

08:17So that's like the basic idea of, of what a graph is and, uh, how it stores relationships.

08:21But, uh, let's talk about the actual four types of graphs that I'm going to go over in more detail

08:27in future videos.

08:29Let's see what time is it right now?

08:30We get like 10 minutes.

08:33Okay. So I can still kind of make this fast.

08:35So the first type of graph that we're looking at right now is actually something called an undirected, unweighted graph.

08:43Why is it a, let's see, let me write this down first.

08:45It's an undirected.

08:47Whoa.

08:48Whoa.

08:48The caps.

08:50Undirected.

08:50What's going on here?

08:54Undirected, unweighted graph.

08:56So why is this undirected?

08:58Because the edges don't have direction.

09:01Uh, if I was, uh, standing in, you know, city six and I wanted to like drive or fly or

09:06whatever from city six to city three, then I should be able to do it.

09:09Cause this edge that connects them doesn't really say that I have to go in one direction or the other.

09:14I could also go to city three and then just walk right back or fly right back to city six.

09:19There's no direction.

09:20So there's an, this, that's, that's why this is an undirected graph.

09:25Uh, this is an unweighted graph because we haven't specified a cost for traveling along an edge.

09:31For example, if, uh, you know, if you're at city three here and you want to fly to city 13,

09:37how much jet fuel does it cost?

09:39How much time does it cost?

09:41If three is a computer and 13 is a computer and the edges like a network cable, like how much

09:47money does it cost to transmit the data?

09:49Or what is the lag in milliseconds?

09:51You know, you can represent all sorts of things with these edges, but there's no value on these edges, which

09:56means there are no weights to these edges.

09:58So that's why this is an undirected and also unweighted graph.

10:02Uh, the first upgrade that I want to do is just kind of show you what you can sort of

10:08assume about an unweighted graph.

10:10This is not always true.

10:11It just depends on who you talk to and what your application implementations are.

10:15Um, so imagine the, the node that goes from six, sorry, the edge that goes from six to one.

10:21If it's an unweighted graph, you could just probably imagine that every weight is just a one.

10:24The point being that it always costs the same amount to travel along every edge because in an unweighted graph,

10:30we don't differentiate between the different edges in terms of their costs.

10:34So we'll just, we could just put a bunch of ones on all these edges.

10:37And it would still, you know, basically be considered an unweighted graph.

10:41It depends on who you talk to.

10:43Um, maybe all, all the weights are zero, maybe all the weights are 10 or whatever, but you know, usually

10:48I put a one there because I'd like to imagine the cost could just be the number of hops.

10:54So for example, if I wanted to go from, from city six to city 10, I could probably, you know,

11:00start at city six and then go to city one and then hop to city 10.

11:04Uh, how many actual hops did I do?

11:06I did two.

11:08I could also come up with that number by just looking at the sum of all the weights of all

11:12the edges.

11:12So notice how, when I go from six to one, that costs me one weight or one hop.

11:18And then when I go from one to 10, that's another one.

11:20So if you put ones on all the edges in an unweighted graph, then you're kind of saying the total

11:25cost of some path is really just the number of hops.

11:28So it's up to you anyway, that's unweighted and, uh, undirected.

11:33Let's upgrade this to an undirected, but weighted graph.

11:37Um, so, uh, let's see, we have an undirected and unweighted, and I'm just going to duplicate this real fast

11:43and change this to a weighted graph.

11:46So undirected, but also weighted.

11:49And the thing is, as soon as you start putting numbers on a graph on the edges of a graph,

11:54well then it's considered weighted.

11:56So even, even a graph that has all ones on all the edges, you could also call that weighted.

12:01But now you have the freedom since it is considered a weighted graph to just assign different values to all

12:09the edges.

12:09Again, these edges are a class sometimes, or you can think of them that way inside the graph.

12:16And the edge weights themselves are definitely considered a T type, a templated type, which means, you know, right now

12:24I'm clearly typing integers, but you could type some other data type.

12:27You could type floats.

12:28You could type some weird data type, like, like a string.

12:32Uh, whether or not that's going to be useful depends on your program, you know, what you're trying to do

12:37with the graph.

12:38But, uh, let's see, I think I've added custom numbers to every single edge.

12:42So now this is definitely an undirected, but weighted graph.

12:45That's the second type of graph, uh, that we're talking about.

12:49Okay.

12:50What's, what's cool about a weighted graph?

12:52Well, imagine again, that this is an airport map where we're representing relationships between, you know, cities, like where can

12:58we fly and stuff.

12:59We're basically saying at this point that if you fly from city six to city one, it's going to cost

13:05you 44 of something.

13:06Maybe this is a graph representing jet fuel, um, or time or frequent flyer points or something like that.

13:15If you consider your edges to be custom classes, you could even put a whole bunch of different types of

13:19values, uh, in your graph, uh, at the same time to make it a little bit more flexible.

13:24But for now we'll just say there's one template of type, which means, um, if we go back up to

13:30this code real fast, where was that code at?

13:33And we had, you know, our rough idea of, you know, what the, what the graph holds, you know, holds

13:39like vertices and edges.

13:41We could upgrade this just a little bit to say that there is a, a, an edge value type.

13:47So I'm going to say class edge, uh, value edge weight type, something like that.

13:58Um, how about like type for the edge so that I can save characters.

14:02And then here I'll change this to a type for the node.

14:06This is why we call it T type.

14:07There's like, we put the keyword template here in C plus plus.

14:10And then sometimes people just use T's here for these tokens.

14:14So I'm just going to say, uh, the type of data that a node can hold is going to be

14:18the T node.

14:18And then the type of data that the edge could hold would be the T edge.

14:22We'll call that data.

14:23Or we could call that weight because usually that data comes into play when you're traveling along an edge, right?

14:29So there's like two different types here.

14:33Anyway, so we had an undirected and unweighted graph.

14:35If we traveled from city six to city one, that costs us 44.

14:39But if you look at the graph a little bit more closely, we could take the longer way around.

14:43We could say go from six to three and then go from three to 13.

14:47And then actually, let me change the color to orange so that you can see there's different paths,

14:53six to three and then three to 13 and then 13 to one, even though we took more hops

14:59and that might've been considered more expensive in an unweighted graph.

15:03You can see that the cost of the, uh, the first path from six to one, that's 44.

15:08And the cost of the second path is, uh, seven plus three, that's 10 and then plus nine.

15:15So that's 19.

15:16So if we take the long way, it actually costs us less of whatever we've determined this unit is, you

15:22know,

15:22less jet fuel, less time, less, whatever.

15:25Uh, these graphs, uh, in the machine are not necessarily going to be to scale because the machine in your

15:30computer,

15:30your computer doesn't really keep track of like the physical positioning of all these nodes and edges.

15:35It just can keep track of the relationship between the nodes, uh, and the edges and the weights and all

15:40that stuff.

15:42So two different paths that we could take to get from six to one.

15:45One of the paths is less expensive, um, or less time costly or just whatever.

15:50And a graph data structure can kind of help us figure that out if we're using an algorithm that understands

15:56weights.

15:56Okay. So undirected and unweighted, let's add direction.

16:01So, um, I'm going to erase this stuff right here real quick.

16:06And in an undirected graph, remember you can just kind of go in either direction along any edge, but in

16:11a directed graph,

16:12every single edge, uh, needs to have a direction.

16:15So as soon as I change, let me change this to just directed.

16:19As soon as I change one of the edges to have direction,

16:22then I must change all of the edges to have direction, uh, as well.

16:26So I'm just saying, okay, as soon as I did that,

16:28now this is an invalid graph because some of the edges don't have direction.

16:33So now I need to fix everything.

16:34So I just, I'm going to arbitrarily and randomly choose a direction for every single edge like this.

16:44Um, and then as soon as I'm done, I'm going to deal, I guess, with that giant edge.

16:50So I'm going to go like that.

16:51So let's see, all the edges seem to have direction.

16:53Now I'm just going to hand draw an arrow, uh, on one side of this giant edge.

16:58Okay.

16:59So this is directed and also weighted.

17:02Um, what can we do with the directed graph?

17:05Well, it just basically tells you which direction you're allowed to travel in.

17:08What if you have an airport where city six can only fly to city one, but city one, for some

17:14reason, never flies the city six.

17:15You got to take like the long way.

17:17You got to go from city one to 13 to three to six.

17:21That's something that a graph could help you represent.

17:23What if your character in your game can only go in one direction, but not the other direction?

17:28Okay.

17:29No problem.

17:29I mean, that's pretty much it.

17:30Uh, you're only allowed to travel in the same direction as the edge points.

17:34But now we, uh, have a graph that is a lot less flexible because for example, before we used to

17:40be able to go from city, uh, 10 to city 44 and then come back again later.

17:45If we wanted in the opposite direction, we can no longer do that because this edge only goes to 10.

17:50It doesn't even go to 44.

17:52We can't even ever actually get to 44.

17:55How do you sort of solve that?

17:56Well, just add another edge in the opposite direction.

17:59In graphs, you are allowed to do something called a parallel edge, which just basically means, you know, two edges,

18:05uh, between the same pair of nodes that just point in the same direction.

18:09You're also allowed to do, uh, you know, opposite facing edges.

18:12So I just added a second edge there going from 10 to 44.

18:15And now if I was, uh, you know, hanging out in city 10, I could just go back and forth

18:19between city 10 and 44 as much as I wanted to.

18:22Oh, I forgot to add an edge weight for that new edge, which means I wrote down an invalid graph.

18:28So I'm just going to save two.

18:30So, uh, maybe the wind is blowing in your favor when you're going from city 10 to city 44.

18:35Maybe it's blowing against you.

18:37If you were talking about city 44 to city 10, you know, whatever, but you just have to have edge,

18:41uh, edge weight on every single edge.

18:45Okay.

18:45So, uh, that's directed and also weighted.

18:49Um, and you can probably imagine previously when we had an undirected, um, graph, when there was just like, you

18:57know, one edge going between, uh, two nodes and there was no direction on it.

19:01Like, you know, 44 to 10, if we just had like one edge with no direction, that would be kind

19:06of the same thing as saying you have two edges each going in the opposite direction.

19:11So we have directed and weighted.

19:13I think the last thing that we didn't do was directed and unweighted, right?

19:18So we have, um, let me just double check real fast here.

19:21We have undirected and unweighted, and then we had undirected and weighted and then directed and weighted.

19:28Okay.

19:28So now let's do, um, I'm getting lost already.

19:34Oh my gosh.

19:34I can't believe I just forgot what I saw undirected and unweighted.

19:40So we did undirected twice already undirected.

19:44So we're going to do directed and unweighted next.

19:47Okay.

19:48So the next graph, uh, a little bit less useful than what we're looking at this, this type of graph

19:52is a little bit more useful.

19:54We're going to do, um, um, directed and unweighted.

20:00Oh my God.

20:01Okay.

20:02Directed and unweighted.

20:03So directed and unweighted, you can imagine just means we get rid of all these, uh, weights.

20:08So, and then we keep the direction on all the edges.

20:11So this means we can keep track of where we're allowed to go if we're pathfinding or just whatever.

20:18Uh, but we don't really know what it costs to travel between, uh, the different graphs.

20:23So that's directed and unweighted.

20:26Um, let's see here.

20:28I'm going to just duplicate this or just make a new blank slide.

20:31And I'm just going to say undirected.

20:33Oh gosh.

20:34I've got pink letters.

20:36Let's see.

20:38Undirected plus unweighted.

20:40And we've got undirected plus weighted.

20:44And then we've got directed plus unweighted.

20:47I don't think I'm writing these down in the same order, but that's okay.

20:51And then we've got directed plus, uh, weighted.

20:53So basically, you know, four types of graphs, uh, that we can talk about in future videos.

20:58We're going to go over graphs in more detail.

21:01We'll talk about graph terminology, maybe some pathfinding algorithms.

21:07Um, and yeah, so this is just a basic intro.

21:10How much time do we spend already?

21:11Oh God.

21:12We spent so much time.

21:14Um, spent like 22 minutes.

21:16Dang, man.

21:17Even the smallest thing takes time.

21:19So, uh, I'll see you in a future video when we talk more and more and more about graphs and

21:24other data structures concepts.

21:26Thanks for watching this video.

21:28I hope you learned a little bit of stuff and had a little bit of fun.

21:32I'm out of here.

21:34I'm out of here.

21:36I'm out of here.

21:37Go.

21:38Go.

21:40Hey everybody.

21:42Thanks for watching this video again from the bottom of my heart.

21:44I really appreciate it.

21:45I do hope you did learn something and have some fun.

21:48Uh, if you could do me a please, a small little favor, could you please subscribe and follow, uh, this

21:54channel or these videos or whatever it is you do on the current social media.

21:57It's a website that you're looking at right now.

21:59Um, it would really mean the world to me and it'll help make more videos and grow this community.

22:04So we'll be able to do more videos, longer videos, better videos, or just I'll be able to keep making

22:09videos in general.

22:10So please do do me a kindness and, uh, and subscribe.

22:15You know, sometimes I'm sleeping in the middle of the night and I just wake up because I know somebody

22:19subscribed or followed.

22:20It just wakes me up and I get filled with joy.

22:22That's exactly what happens every single time.

22:24So you could do it as a nice favor to me or you could, you could troll me if you

22:27want to just wake me up in the middle of the night, just subscribe and then I'll, I'll just wake

22:31up.

22:31Uh, I promise that's what will happen.

22:34Also, uh, if you look at the middle of the screen right now, you should see a QR code, which

22:38you can scan in order to go to the website, which I think is also named somewhere at the bottom

22:42of this video.

22:43And it'll take you to my main website where you can just kind of like, see all the videos I

22:47published and the services and tutorials and things that I offer and all that good stuff.

22:52And, uh, if you have a suggestion for, uh, uh, clarifications or errata or just future videos that you want

23:01to see, please leave a comment.

23:02Or if you just want to say, Hey, what's up? What's going on? You know, just send me a comment,

23:06whatever.

23:07I also wake up for those in the middle of the night. I get, I wake up in a cold

23:10sweat and I'm like, it would really, it really mean the world to me.

23:15I would really appreciate it. So again, thank you so much for watching this video and, um, enjoy the cool

23:21music as, as I fade into the darkness, which is coming for us all.

26:31Hello there.

26:32Let's talk about the four types of.

26:38Hello there.

26:42Hello there.

26:43Hello there.

Category

Transcript

Comments

Recommended