How to Represent Undirected Weighted Graphs Using Edge Lists

Name: How to Represent Undirected Weighted Graphs Using Edge Lists
Uploaded: 2026-08-26T07:39:52+00:00
Duration: 23 min 21 s
Channel: Neural Lantern

00:01Hey there. Uh, hello there. Hey there. In the last video we talked about

00:08representing an unweighted and undirected graph using the edge list

00:11representation inside your machine. Now let's talk about how to do that exact

00:16same thing with undirected weighted graphs.

00:27Okay, so what you're seeing on the screen right now is, uh, is basically the last diagram that I drew

00:31on my previous video

00:32where we talked about how to represent unweighted undirected graphs in the machine.

00:37You don't necessarily need to watch that video to understand this video, but you probably want to watch

00:41a few of my other previous graph videos to know the basics of graphs and edge lists and edge-based

00:48paths

00:48and node-based paths and all that stuff. So for now I'm just going to continue from this document.

00:54So let's see. I'm going to duplicate this real fast. I am going to just kind of modify the captions

01:02here

01:02because we're not going to do unweighted anywhere. We're going to say a weighted undirected graph.

01:07Did I get that backwards? I think sometimes people say undirected and then the weighted part after.

01:12So I'm just going to change it. So it's still undirected, which means the edges don't have arrows,

01:17so that's fine. But it's going to be weighted now, which means I have to assign a cost of traveling

01:22along every single edge. So I am going to just sort of like erase a bunch of this stuff real

01:28fast.

01:29Erase these notations. Uh, you know what? I'm going to erase all of this because I want you to,

01:34you know, see it from start to finish. Okay. So now I'm going to add weight costs on every single

01:41edge.

01:42Um, in the last video, what I mentioned is that the, the edge list representation of a graph in the

01:48machine, uh, is basically your graph is a tuple. That's the orange markings up here. Your graph is

01:55a tuple where the tuple consists of a vertex list and also an edge list. So we'll, we'll do that

02:01from

02:01scratch together again. But, um, let me get the weights on there first. What color do you want?

02:06I don't know. I'm going to put arbitrary numbers, uh, on all the edges just to say that every edge

02:10has

02:10a cost. Remember in a graph, when you travel along an edge, if the edge has a weight, then you

02:16consider

02:16that weight to be part of the cost usually, um, of traveling there. So like if this was a network

02:21diagram, maybe, uh, these weights represent, uh, pings or lags or bandwidth cost or something like that.

02:29If this is like an airport diagram, maybe the weights represent gasoline or time or something like

02:34that. So I'm going to do like a four there. We can repeat, uh, weights if we really want to.

02:39I'm going to line this up a little bit better. That 12 looks gross. Okay. I think we're okay now.

02:44I have 14. All right. Did I forget anything? Raise your hand if I forgot something.

02:51Oh, I forgot. Okay. Did you raise your hand? Okay. I'm going to do the 13 and six. Uh, let's

02:57just put a

02:57two weight there. You could put ones everywhere if you wanted to. I mean, any, any number is fine.

03:03Um, also in an unweighted graph, you kind of can consider the number of hops to be a path cost,

03:09which means you can kind of consider every, uh, edge to just have a weight of one.

03:13But for now, we're just gonna say this is the weighted graph.

03:17Okay. So the first thing we need to do, uh, after that is make a vertex list. So our vertex

03:23list

03:24is just going to be a list of all of our vertices, all of our nodes in the graph.

03:28How do we list them? So for starters, like we usually say vertex list, but for me personally,

03:35this, this particular data structure, just that we're going to type up on the bottom,

03:39I usually like to consider that a vector, uh, or an array at least, uh, because you can jump into

03:45a specific index in constant time, which is really, really fast. If you don't know, uh,

03:50big O and time complexities, check out my other videos, but, um, it's just really,

03:54really fast to jump to an index, uh, when you're using an array or a vector,

03:58but it's kind of slow when you're using an actual linked list or some other data structure

04:02that makes you scan through it. So I'm going to say that my, uh, vertex list

04:06is actually a vector, but I'll keep calling it a list.

04:12Anyway, so we got the vertices, uh, we have to start naming them. Okay. So the first thing is

04:17I'm going to do, we got the three there and we got the 13 and we got the six and

04:21the 12 and the 15.

04:22I'm just naming all of the nodes in my graph. I like to go from left to right,

04:26because that makes it easier for me to debug what I'm doing. Um, you probably in your code,

04:31I said this in the last video, you probably don't want to store the actual value in your vertex list.

04:35You probably actually want to create an object of type node or of type vertex and give it the template

04:41data type of, in this case integer, and then set the 13 inside of the class.

04:47It's not as fast and memory efficient as just putting a number there, but, uh, you know,

04:51for me, I like more flexibility and I like to be able to do more powerful things with my

04:55stuff. So I'm going to say that 13 and all of the other nodes, really that represents to me,

05:01I made a brand new instance of a class called node or vertex, and then I set it up however

05:06I wanted.

05:07And one of the things I did to set it up was stick the number 13 inside of the class,

05:11but for the, for the diagram, it's fine like this. Okay. So we have our vertex list. That's the V.

05:18If you're looking at the, uh, you know, the V comma E, the V part. Now we need to do

05:22the edge list.

05:23So I'm going to say, here's my edge list. And we're going to use the edge list representation,

05:28like I talked about in previous videos, which is basically a tuple where one tuple, uh, describes

05:34one edge. So, uh, in our graph that we have right now, we definitely need a starting point and an

05:42ending point. So let me just start by looking at, uh, the three node. And I want to describe one

05:46of the

05:46edges for the three. So the three goes to, uh, the 18 and the 13 and the 12. I'm going

05:52to scan my eyes

05:53from left to right to make it a more, a little more simple. So the three, uh, node, it connects

05:59to the 13 node. So I'm going to put a three comma 13. Uh, the order of the nodes doesn't

06:05matter in an

06:05undirected graph. So I could have easily put 13 and three. It's fine. You don't want to duplicate it

06:10by putting 13, sorry. You don't want to put three comma 13 and then later put 13 comma three.

06:15You don't want to double it up. Uh, cause that would be like representing two separate edges.

06:20I'm just going to sort it in my mind before so that I don't have to sort it again later

06:24when

06:24I'm reading the graph, which makes it faster for read operations. But so three goes to 13,

06:30and then we have to represent the weight. So the tuple gets a little more complicated

06:33than the last video. Just by a little bit, I'm going to say three comma 13 comma the weight,

06:39which is just a one here. And I think I mentioned this in my other videos like a while back,

06:44but, uh,

06:45the weight doesn't have to be integer. It could be a float. It could be any data type you wanted,

06:49really. As long as your algorithms support it and you have, you know, your operator overloads

06:54all done and all that, uh, it could be a full class just for the weight if you wanted to.

06:58But for this video, it's just going to be the weight is an integer. So that's the cost of traveling

07:01along that one edge. So notice how all of our tuples have three items each. It's a triple tuple.

07:08So I'm going to continue trying to represent, uh, what the three touches. So the three,

07:12uh, it touches the 13 and it also touches the 12. So I'm going to say three goes to 12.

07:18What does that edge cost? It costs a six because that's the little

07:22pink six there. We're done with that tuple. So what else does three touch?

07:27Uh, it touches the 13 and then it touches the, uh, 12 and then it touches the 18. So

07:33I'm going to put an 18 there. What does that edge cost? It costs a four

07:37because there's a pink little four at the very top of the graph.

07:40I'm surprised you didn't know that. Okay. So then, uh, I'm sorry, we're going to move on to the next

07:46node. So we did the three already. So I'm done with that. I'm going to look at the 13.

07:50Where does the 13 connect? It connects to the three, but that's to the left.

07:55Meaning because I'm, this is why I like to scan my eyes from left to right. I already know

07:59stuff on the left is handled. I don't have to do it again. So forget about the three. I already

08:03described it up here in the very first tuple 3, 13, 1. I don't want to describe it again.

08:09So forget about the three. Now the 13 connects to the six. So 13, 6. And what does that cost?

08:15It

08:15costed two for our arbitrary labeling. 13 doesn't touch any other nodes. So we're done with the 13 row.

08:21And by the way, I'm doing a line, new lines here. You don't have to do that. I just like

08:26to,

08:26I like to do one, you know, row per, per start node to make it look cooler and nicer.

08:34Okay. So the, uh, 13 is done. Now let's do the six, six touches the 13, but remember in the

08:41previous

08:41row, we just handled that. So I'm not going to do it again. The six to the right touches three

08:46other

08:46nodes. You can see there are three lines protruding on the right side of the six. So, um,

08:51I'm just going to take those from left to right. It's touching the 12 at a cost of 14.

08:56Um, the six is also touching the 15 at a cost of 12, I think.

09:02And the six, you know, if I make mistakes, just leave it in, leave it in a comment. I will

09:06leave

09:07the video up so you can always remember my humiliation, but, uh, I'm going to try my best.

09:12I did not practice this. Six touches the 15 and then the six touches the 18. So six touches 18

09:18and then it costs nine. So now we're probably done with the six. Um, moving on, uh, one node

09:26to the right. Now we're going to look at the 12. Okay. So the 12, it touches three and 13

09:31and six,

09:32but those are already handled. So forget it. The 12 touches the 15. We did not handle that,

09:37right? Yeah. Cause we're going from left to right. Uh, and then it costs us from going from 12. What

09:43am I doing? It doesn't touch the 15. Oh my God. Uh, so the 12 touches the, uh, the three,

09:51which is already handled and it touches the six, which is already handled. And then it only goes to

09:57the right to the 18. Okay. Anyway, you know, when I make mistakes on camera and I say do over,

10:03I always go, I don't know why. So the 12 and the 18, uh, it's going to cost us three.

10:10So then we're done with the 12. So I'm going to go to the next one.

10:13Oh, we'll look at the 15, the 15, six is already handled. 18 is not handled yet. So I'm going

10:19to put

10:1918 there and it costs us 88. And then the, uh, 18 is the last one. There's nothing to do

10:27because

10:27every node is on the left of the 18. If you carefully, if you pause the video and look at

10:31every single node, you'll see it's already represented in a previous node. So we're officially

10:35done, uh, with the basic edge list representation of this graph, this undirected, but weighted graph.

10:44We need to do something else though. I mentioned in the last video, I'm going to repeat it in case

10:47you

10:48didn't watch the last video, but we need to make sure that, uh, oh, I guess I forgot to separate

10:53those two things. That means I have to duplicate the text list over here on the right side too. Okay.

11:00Um, so on the left, this is okay, but it's kind of slow because what if we're trying to look

11:05at, uh,

11:06you know, one particular edge, let's say that we, we want to see what's going on with this,

11:09uh, this edge right here. Let's say the, the three and the 13 edge for whatever reason.

11:14Um, I don't know, green, three and the 13 edge. Okay. So we're looking at that edge.

11:20Maybe for some reason we had just finished scanning. Uh, maybe that's not a fun edge.

11:25Well, what's going on? Hello. Uh, oh, I forgot to set up a thing where you can

11:30make your cursor really visible. Okay. Um, actually, so, so this is not the most fun edge. Let me,

11:37let me see about the 15 and the 18 edge. Excuse me. I had to take a drink of water.

11:43So we're going to look at this edge connecting the 15 and the 18 node. That's a little more

11:47interesting. So you can imagine maybe you were doing a little scan. Uh, if you know, big O complexity

11:53by now, we had to check out every single edge in this edge list until we found the one that

11:58connected

11:59the 15 and the 18. So this was a linear time scan based on the number of edges. So this

12:05is just,

12:06it's scalable, but it's not very fast, right? So we ended up kind of looking at this one right here,

12:12not fast. Um, but what if we want to examine, uh, some properties of the nodes or the vertices,

12:18uh, involved like the 15 and the 18 here in this representation on the left, we have the values.

12:23We have the 15 value in the 18 value. We don't really have a pointer to a full node object

12:28if that's

12:28what you're doing in your code. So, um, how do we get those, those node objects? We're going to have

12:34to do another linear scan. We're going to have to look at this one right here. Oh, that doesn't

12:38match the value of 15. Look at this one. Look at this one. Look at this one. We're going to

12:41have to

12:42scan every single node until we realize that it's those two at the end. This is true even if it's

12:48a

12:48vector holding your vertices, because if we don't know the index, then we have to actually just sweep

12:54through the whole vector. So that's really slow. It's still kind of scalable, but it's not the best.

13:01Instead, let's update the, the representation on the right to have indexes. We did this in the last

13:07video, but basically if you just kind of look at this three node here, the three node, well,

13:12let me, let me copy this one more time. The three node corresponds to index zero, uh, which I forgot

13:18to write down. My bad. Let me write that down for you real fast. Get rid of that. Get rid

13:26of that.

13:28Okay. So I'm just going to update this vertex list to just show you that if we have a vector

13:33or an

13:33array, then every single item has an index. Here's index one, index two, index three and four and five,

13:41and then I guess I'll just copy paste that to the other one since I was too dumb to make

13:48an extra

13:49separated graph there. Um, separated item. Okay. So the, uh, the 15, sorry, no, the 13,

13:58the three and the 13, I guess I got to get rid of that. That's distracting me. The three and

14:02the 13,

14:03those correspond to indexes zero and one in the vertex list, right? So zero and one, that's the three

14:09and the 13. So I'm just going to change the values, the T type values to the raw indexes.

14:16It's going to seem a little weird at first, and I'm going to leave the weight alone because

14:19that's totally fine. We're not going to jump to a weight unless maybe you had a weight list,

14:24a weight vector. If you wanted to make instances of weights, you could do that. I'm not going to do

14:28it.

14:29So then again, the three is a zero. The 12 is index three. Uh, the three is another zero.

14:36The 18 is index five. I'll just do this for every single row. So, uh, the 13 here is index

14:43one,

14:43and then the six is index two. Notice how I'm just looking up here

14:47at the indexes of the vertex list, and I'm just changing the node values to the indexes

14:53where the nodes actually are in the vertex list. So that's a two, and then the 12 is going to

15:00be a

15:00three, and then the six is also going to be a two, and the 15 is going to be a

15:03four,

15:04and then the six is going to be a two, and the 18 is going to be five.

15:08On to the next row, the 12 node is index three, the 18 node is index five,

15:15uh, the 15 node is index four, and the 18 node is index five. So,

15:20whoa, whoa, correct me if I made a typo in the comments, please. I'll release another video as a

15:25thank you. But, uh, now I've converted the whole entire representation on the right side to an index

15:31based, uh, uh, you know, edge list. So I'm going to do this one over here is by value,

15:37and the one on the right is by index. Why is the one on the right better now?

15:42Remember, at some point, we might have been scanning to find an edge.

15:46Whoa, what did I just do wrong? Oh, I clicked over there. Okay,

15:49we might have been scanning to find, you know, some edge. So we're like scanning, scanning, scanning,

15:54scanning, scanning, and then maybe we decide we're trying to figure out what's going on with the two and

15:57the, not the two and the four, the, uh, the six and the 15 node, right? So that's, uh, the

16:02six and

16:03the 15 node. That's basically, you know, this right here. Uh, so now what if we want to do something

16:10with

16:11the nodes? We want to do something with the six node, do something with the 15 node. We don't want

16:15to scan through the vertex list again. We don't want to go scan, scan, scan, scan, scan. That's linear

16:20time. That's not as fast as it could be. So instead, we've already converted here so that we have indexes

16:27so if I look at the two and the four, the two and the four represent indexes, not node values.

16:33So this two tells me that I can go to index two to get the six node and the four

16:38tells me I can go to

16:39index four to get the 15 node. Notice how I did not have to scan the vertex list to figure

16:44out where

16:44those nodes are. And if you're using a vector for your vertex list, then you can jump to every index

16:50in

16:50constant time. So now if we were going to, you know, search and do a bunch of stuff on edges,

16:55we probably

16:55only had to spend linear time on the edge list, but then we only spent constant time to manipulate

17:02each node. Whereas it would have been linear plus linear in the past. Like on the left side, that

17:07would have been, you know, if we're going to do stuff with, with both the edges and the nodes, it

17:12would have been O of linear time based on the number of edges. If we're going to do every, you

17:18know,

17:18something to every single edge plus linear time based on number of vertices. But over here,

17:24it's going to be linear time of the edges plus just constant time, which basically means it's

17:30going to be, you know, big O of just the number of edges. And I'm talking about a, you know,

17:36a fantasy

17:37scenario where we're just going to scan a bunch of stuff. You can imagine there's a whole bunch of

17:41different operations you could do on a graph, and it would be very advantageous and fast if you could

17:46just jump to a node if you wanted to be able to manipulate it directly.

17:52Let's see. So I did, I think, 20 minutes already. So I think this is going to be it for

18:01today's video. And I'm going to do another video after this, where we start working with directed

18:06graphs. So I'm going to do directed, unweighted, and then directed, weighted. So by the time you

18:12watch all four of these videos, you'll know how to represent all four types of graphs in the machine.

18:18Okay, anyway, so thank you for watching this video. I hope you learned a little bit of stuff

18:22and had a little bit of fun. I'll see you next time. Tell your friends, eat a chocolate. Okay,

18:29I'm outie.

18:31Hey, everybody. Thanks for watching this video again from the bottom of my heart. I really

18:35appreciate it. I do hope you did learn something and have some fun. If you could do me a please,

18:40a small little favor, could you please subscribe and follow this channel or these videos or whatever

18:46it is you do on the current social media website that you're looking at right now. It would really

18:51mean the world to me and it'll help make more videos and grow this community. So we'll be able to

18:55do

18:56more videos, longer videos, better videos, or just I'll be able to keep making videos in general. So

19:01please do me a kindness and subscribe. You know, sometimes I'm sleeping in the middle of the night

19:07and I just wake up because I know somebody subscribed or followed. It just wakes me up and

19:11I get filled with joy. That's exactly what happens every single time. So you could do it as a nice

19:16favor

19:16to me or you could you could troll me if you want to just wake me up in the middle

19:19of the night,

19:19just subscribe and then I'll just wake up. I promise that's what will happen.

19:24Also, uh, if you look at the middle of the screen right now, you should see a QR code,

19:28which you can scan in order to go to the website, which I think is also named somewhere at the

19:32bottom

19:32of this video. And it'll take you to my main website where you can just kind of like see

19:37all the videos I published and the services and tutorials and things that I offer and all that good

19:42stuff. And, uh, if you have a suggestion for, uh, uh, clarifications or errata or just future videos

19:51that you want to see, please leave a comment. Or if you just want to say, Hey, what's up, what's

19:55going

19:55on? You know, just send me a comment, whatever. I also wake up for those in the middle of the

19:59night.

19:59I get, I wake up in a cold sweat and I'm like, it would really, it really mean the world

20:05to me.

20:05I would really appreciate it. So again, thank you so much for watching this video and, um,

20:11enjoy the cool music as, as I fade into the darkness, which is coming for us all.

How to Represent Undirected Weighted Graphs Using Edge Lists

Category

Transcript

Recommended