How to Represent Undirected Weighted Graphs Using an Adjacency Matrix

Neural Lantern

In this video we cover how to represent an undirected weighted graph with an adjacency matrix. You will see how to place edge weights into the matrix cells and why infinity is used for missing connections so that a real weight of zero stays available. Because the graph is undirected the finished matrix is symmetric across the identity line, which gives an easy way to check your work. We also look at self-connections and at practical ways to store infinity in code such as language sentinels, optionals, or null pointers. Accessing or updating any cell remains constant time, so adding or removing an edge is fast.  00:00 Introduction to Undirected Weighted Graphs 00:41 What Undirected and Weighted Means 01:08 Matrix is Constant Time Under the Hood 02:28 Starting to Fill the Adjacency Matrix 04:12 Using Infinity for No Connection 06:05 Filling the Matrix and Noticing the Mirror 08:24 Using the Mirror to Speed Up Filling 11:21 How to Represent Infinity in Code 14:09 Adding Self-Connections 15:46 The Mirror Along the Identity Line 18:21 Adding and Removing Edges in Constant Time 19:49 Conclusion and What's Next 20:02 Subscribe and Outro  adjacency matrix, undirected graph, weighted graph, graph theory, data structures, algorithms, programming, coding tutorial, infinity sentinel, constant time access, self-loop, graph representation  =-=-=-=-=-=-=-=-=  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://thao.funnymoment.net/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:01Hey there, let's talk about how to represent undirected and weighted graphs in your machine

00:06using an adjacency matrix.

00:15A lot of words, right?

00:17Okay, so in the last video we talked about how to do an adjacency matrix for an undirected

00:21and unweighted graph.

00:22Now we're doing another graph, but it has weights on all the edges, so it's a weighted

00:26graph, and we're going to learn how to do that in an adjacency matrix as well.

00:31If you haven't watched the previous video, you probably should, although I'm going to

00:34kind of do this from scratch anyway, so I think you'll be okay if you don't want to

00:37watch the other one.

00:38Okay, so the first thing to understand is we have undirected and weighted, which means undirected

00:44says there's no direction on any of the edges.

00:47You can see all the edges are just lines, there's no arrows.

00:50Weighted means there's a cost to traveling along every single edge, so that's why there

00:55are numbers on every single edge.

00:57And then we're going to use a two-dimensional matrix to represent this graph inside your

01:02machine, like this is kind of how you would code a graph.

01:06The first thing to understand is that this two-dimensional matrix, it's really a one-dimensional

01:12matrix under the hood.

01:13You know, we have like, I'm going to put like a pound sign for a number.

01:17Imagine we have a whole bunch of numbers in a one-dimensional array.

01:21Okay, we could reorganize those numbers if we wanted to, with, I should have had one

01:26less number there.

01:28We could just reorganize those if we wanted to, to look two-dimensional, but it still

01:33would be a, you know, what did I just do wrong?

01:36I think, oh, I have to hit this 100% thing.

01:40What is going on here?

01:42Uh, F11.

01:43Oh, I forgot to hit the full screen.

01:44Okay.

01:45So, uh, yeah, we can represent this one-dimensional matrix, sorry, one-dimensional array as a two-dimensional

01:51matrix.

01:52You can do this with any number of dimensions.

01:54And what I'm really, what I'm really trying to say is that accessing any particular cell

01:58within the matrix, even though it's like you got to go down, you got to go to the right

02:02as a human, the computer can still get there in constant time.

02:05We'll talk about time complexities in a different video, but just understand it's very fast to

02:10just reach one cell in the matrix.

02:12And that's true even for an N-dimensional matrix, like 19 dimensions.

02:16You can still reach one cell in constant time.

02:18Super, super fast.

02:20Okay.

02:20So now let's try to figure out how we can fill out this matrix so that this graph is, uh,

02:26represented accurately in the machine.

02:28So I'm going to get rid of maybe this first.

02:32And, um, so there's no direction on this graph, which means it doesn't really matter which

02:38node starts and which node ends, you know, what's the source and what's the sink, what's

02:42the beginning and what's the, uh, the end or the finish or whatever you want to call it.

02:45Um, and we're going to end up seeing a mirror in this matrix along the identity line.

02:50So just to let you know, um, half of this matrix is kind of wasted memory.

02:54That's okay.

02:55But, um, I'll show you what I mean.

02:57So what I like to do when I'm filling, um, these matrices out is I like to say that the

03:02start node is the row and the destination node is the column.

03:06I know I just said that that doesn't matter which way you start.

03:09So you can do it, you know, your own way.

03:11But for me, I like to say that the row number, uh, starts because that helps me later when

03:15we add a direction, uh, to all the edges.

03:18So if I start at node one, let's, uh, here, let me just highlight this real fast.

03:23If I start at node one and I say, how do we fill this out?

03:28Well, I'm just going to go into the matrix and I'm going to say row one, because that's

03:33the start node and, um, column wherever it goes to.

03:38Uh, the one node right now, I'm going to say that the nodes don't connect to themselves,

03:42uh, automatically because I just want the option of a self-connect edge that you can

03:47see.

03:48So right now there's no loop coming out of the one and then going back into the one.

03:52We can add that later, but for now, I'm just going to say by default, there are no self-connects

03:56unless you see it in the diagram.

03:58So the one node going to the two node, you can see that it does connect to the two node.

04:03Uh, so in our, uh, unweighted graph, we just put a one to say there's a connection or zero

04:08for no connection.

04:11We have to upgrade this now.

04:13So because, um, we can add a weight to every single edge.

04:17That means it's totally possible that you might have an edge that has a weight of zero,

04:21which would mean, uh, representing no connection as zero doesn't make as much sense anymore.

04:26So instead of a zero to say no connection, because we can, we can have like negative numbers,

04:31positive numbers.

04:31We could say that an edge costs nothing.

04:33Um, like if you're using a graph to make a game with like decisions or something, maybe

04:37it doesn't cost the character anything to go open the door or whatever.

04:42Let's say that zero cost actually is infinity.

04:45I'm going to say INF.

04:47Uh, maybe that's going to get too big later.

04:49Infinity means no, uh, connection.

04:52It means an infinity cost.

04:53And usually I like to say, have you ever like gone to Google maps?

04:57And you said like, how do I, how do I walk from Florida to China and Google maps is like,

05:03well, I don't know if they do this now, but a long time ago, they would say, jump into

05:07the ocean and swim.

05:08Um, so, you know, what's going to happen?

05:10You're going to die.

05:11So the cost is infinity.

05:12You can't get there.

05:13So if the cost is infinity, you'll never get there.

05:15So infinity cost means no connection.

05:18Is that a dumb joke?

05:19Uh, leave a, leave a comment anyway, but the connection from one to two, we can see that

05:24it exists and there's a seven right there.

05:26So it costs seven to go from one to two or from two to one.

05:31Um, so I'm going to go to node number three.

05:34So from one to three, that is connected.

05:36It's going to cost us nine from one to four.

05:39Um, I see a connection.

05:41It costs 12 can be embarrassing.

05:43If I notice an edge that doesn't have a weight on it, we go from one to five, uh, that

05:48is

05:48connected and it seems to cost one.

05:50And then if we go from one to six, that also is connected.

05:53It costs nine.

05:54I made these graphs too dense.

05:56We go from one to seven.

05:58There's no connection there.

05:59So the cost is infinity because you can't do it.

06:03Okay.

06:03Then we just repeat the process again and again and again.

06:05And eventually we'll start to see a mirror show up.

06:08I'll show you in a sec.

06:10So going from two to one, um, two to one costs seven.

06:14Notice how there's also, there's already a little bit of a mirror happening, right?

06:17Seven here and then seven down here.

06:21Two going to two.

06:22We're going to say again, by default, uh, there's no connection.

06:25Two to three.

06:26Uh, that's a cost of two, two to four, no connection.

06:29So infinity costs.

06:32And then, uh, two to five, getting lost already.

06:36Uh, no connection.

06:37I don't think I see the connection.

06:39And then, uh, two to six.

06:42Uh, uh, nope.

06:43So another infinity.

06:45And then two to seven.

06:48Uh, uh, yeah, there is a connection and it costs four.

06:50Okay.

06:51Almost screwed that one up.

06:53So then we just say, you know, all the other nodes.

06:56I'm going to continue.

06:58From three to one, uh, that's a cost of nine.

07:02Notice how from one to three was also a nine.

07:05We're starting to see the mirror.

07:06The mirror is kind of good for, you know, debugging your, your, your matrix after you make it.

07:11Um, we won't be able to do that with directed graphs, but for now we can.

07:14Three to two is a cost of two.

07:16And, uh, three to three, we'll say no connection by default.

07:19Uh, three to four.

07:21Um, there's no connection, I don't think.

07:24And then, um,

07:26three to five, three to five.

07:29There's a three cost there.

07:31There's a weight of three, three to six.

07:34Um, yes.

07:35With the cost of seven and then three to seven.

07:39Um, I don't see a connection.

07:41So I'm going to put infinity costs.

07:43Okay.

07:44Uh, going from four to one.

07:45Notice the mirror.

07:47It should cost 12.

07:48And then from four to two.

07:50Uh, nope.

07:51Infinity four to three.

07:54Nope.

07:55Infinity.

07:56Infinity four to four.

07:57We'll say no self connections by default.

08:00Infinity four to five.

08:03Nope.

08:05Four to six.

08:07Uh, nope.

08:09And then four to seven.

08:11Yes.

08:11At a cost of 13.

08:13And do the same thing.

08:14All right.

08:14For the five.

08:16Okay.

08:16So the five, um, is connected to the one.

08:19Yes or no.

08:20Yes.

08:21With the cost of one.

08:22The five.

08:23I could just look at the mirror if I wanted to.

08:25Like, like, by the time you get further down in the graph.

08:27Here's a trick.

08:28By the time I'm all the way down here at the five.

08:30I can just start looking at the columns.

08:32I can say, well, what's going on with column five.

08:35I could just say, well, column five has a one in the one row.

08:38And then infinity in the next row.

08:41And then a three in the next row after that.

08:42And then another infinity.

08:44And I can, I could double check this right now just to make sure.

08:46But the five is connected to the one at a cost of five.

08:50Right.

08:51And then the five is not connected to the two.

08:53And the five is connected to the three with a cost of three.

08:56And it's not connected to the four.

08:58Notice how that matches.

08:59So the further down I go, the further I can sort of just look back at the previous rows

09:05or the previous, previously done columns.

09:09So I don't have to think.

09:10Which I just, I really like not having to think sometimes.

09:13Five and six.

09:15I do like to think it's fun.

09:16It's going to be five.

09:18Okay.

09:18So then five to seven is going to be a two.

09:21And then we'll move on.

09:22So I'm going to do that trick again.

09:23I'm going to look at the six column and I'm just going to start copying stuff.

09:27So we have like a nine and then infinity.

09:31And then seven.

09:32Oops.

09:33Seven.

09:34And then infinity.

09:36And then five.

09:39And then I'll just double check it since this is supposed to be a professional tutorial video.

09:44Six going to nine.

09:48What?

09:49No, no.

09:49Six going to one is nine.

09:50Yeah.

09:51Six going to one is nine.

09:53And then six does not go to two.

09:54And then six goes to three with seven.

09:58Yes.

09:58And then six goes to, does not go to four.

10:01Correct.

10:02Six does not, six goes to five with a cost of five.

10:05Okay.

10:05So then I have to think now.

10:08We'll say no self connections.

10:09And then six going to seven.

10:13I see that there's a cost of six there.

10:15Okay.

10:17We're making progress.

10:20I'm going to duplicate this in case I screw it up.

10:23So now let's look at the seven node.

10:25So the seven node, I'm just going to copy everything.

10:29I'm actually allowed to do that at this point.

10:30And then I'll double check it.

10:31So look at the seven column.

10:33I'm going to put infinity and then four and then infinity and then 13 and then two and then

10:45six.

10:46And then seven is not connected to itself.

10:49Then I'll just double check this to make sure that I'm okay.

10:54So seven to one, nope.

10:58Seven to two, that should cost four.

11:01Yep.

11:02Seven to three, nope.

11:04Correct.

11:05Seven to four, 13.

11:08Seven to five costs two.

11:10Seven to six costs six.

11:13And then seven self connection.

11:15By default, we say they're not connected.

11:17Okay, so we filled out an entire adjacency matrix.

11:19Maybe there's something else I should mention too before I forget.

11:23How do you represent infinity if we have a double value here?

11:28So like if we're talking about actual code, there's a whole bunch of different ways to

11:32do it.

11:33Like for instance, in JavaScript, you could put NAN, not a number.

11:36There's other ways to do infinity there and also in C++ and Python.

11:42So you'll have to look up doubles on your programming language of choice and find out,

11:47is there a special value that represents, you know, infinity?

11:52The standards sometimes have special values for these kinds of things.

11:56We call them sentinels.

11:57And if you can't figure out what is the sentinel for your particular language using doubles or

12:03integers or whatever, you could just make one up.

12:05Like for instance, if I was stuck using integers and whatever system I was using, there was

12:10no such thing as infinity for an integer, you know, a signed integer, then for me, I

12:17would just say, all right, what's the most negative, the least possible value that I could

12:22ever represent in the negative number?

12:23And I'll call that infinity.

12:25And then I'll just tell myself, don't ever set that as the weight.

12:28Maybe in my code, I'll say, if there's no connection, set it to that special sentinel

12:33value, that special most negative value.

12:36But otherwise, if the user of the code is trying to add an edge, my code will just check to

12:41see if I'm accidentally using that sentinel and then, you know, reject the edge if the

12:46user tries to do that.

12:47So then the user just loses, you know, one number that they can assign to the weight of

12:51an edge.

12:52But then you get the ability to do infinity.

12:54Another cool thing that you can do now with C++ is called, I think it's, I think it's called

12:58optionals, you can basically do an, I'm not going to do a C++ tutorial right now, but you

13:04can look it up and you can say the template data type optional, and then the token type

13:10is integer or, or, or double.

13:14And then the optional allows the value to exist or not.

13:18So we could say that there are optional integers or optional doubles all throughout the matrix.

13:23And when an edge doesn't exist, the optional will be null or not on or, you know, null or

13:28whatever.

13:29You could also put pointers to integers or doubles.

13:32You could say every time we fill something out in the matrix, maybe this whole matrix is

13:35actually just a matrix of pointers of double pointers or integer pointers.

13:39Every time we fill out a number, that particular pointer becomes like a real pointer to an actual,

13:44you know, integer or double.

13:46And every time we take away an edge, we'll just set that pointer to null.

13:50There's a whole bunch of different ways you can do it.

13:52But I just wanted you to know about a couple of them.

13:54Okay.

13:54So before we continue any further, I want to, is that a perfect duplicate, BTW?

14:02Why is it, why is it like offset?

14:04That's so weird.

14:07Um, I would like to show you a self-connect.

14:11So how do we do self-connects in this type of matrix?

14:16For starters, we're assuming that there are no self-connections by default in this particular

14:20matrix in this particular diagram.

14:23So that's why I put infinity all along the identity line.

14:26We'll talk about that in a second.

14:27But, um, what if I wanted to suddenly add an edge?

14:30I'm going to say, let's do, uh, seven connects to itself.

14:35And so now we'll drop the assumption that all of the, uh, well, we'll keep the assumption.

14:42We're going to have a different assumption in a different video.

14:44We'll keep the assumption that there's no default self-connects.

14:46But if I actually draw a self-connect, now we could say that seven is connected to itself,

14:51which means we can just go to row seven, column seven, and, uh, give it whatever weight we chose.

14:58Let's do, uh, I don't know, let's do like a four.

15:01And then of course I have to actually draw a four there for the weight.

15:06And so that's how you can just do self-connects.

15:09I'm going to duplicate this one more time and move it down.

15:14Um, let's see.

15:15The other thing I wanted to say, oh, what happened there?

15:16Did you see that?

15:17I lost like a whole row.

15:22I got to get rid of this.

15:23How do I do it?

15:25Is that the rest of the, no, okay.

15:28I'm not happy about this.

15:30I'm not happy at all.

15:31Look at that.

15:35Oh, because I duplicated, I duplicated the slide before I finished it.

15:39Okay, so I guess it's okay.

15:41So now we're doing the fours.

15:43Okay, um, so I'm going to now lose my train of thought entirely.

15:50Um, oh, I wanted to show you that there's a mirror along the address.

15:54Okay, so weighted makes this a little bit more complicated, but undirected is what we did

15:59in the last video.

16:00That's kind of easy and kind of fun.

16:02So watch your eyes real fast over the identity line here.

16:07And I just mean like this diagonal line.

16:08Is it going to highlight in green?

16:12How can I get yellow back?

16:14There we go.

16:15So I'm going to highlight this diagonal, which is like the identity line, meaning one

16:20to one and two to two and three to three and so forth.

16:23If you just kind of like stare at that line long enough, you'll realize that it's a mirror

16:27because we have an undirected graph.

16:30For example, if you see, oh gosh, I'll keep the highlighter.

16:35That's kind of fun.

16:36You see seven, nine, 12, one, and nine in the one column.

16:41So like one is connected to two, three, four, five, and six.

16:45We could do the same thing by just flipping the rows and the columns.

16:48So instead of column one, we'll do row one.

16:51And then we'll say that the columns are two, three, four, five, and six.

16:55So notice how here it's kind of a little mirror.

16:58Um, if we look at column three, it's got entries in nine and 12 and a whole bunch down here.

17:06I guess, well, just these two down here.

17:08Then we do row three and do the same thing for the columns.

17:12Notice how this is also a mirror.

17:14I'm drawing a mirror.

17:15You can see, right?

17:16Tilt your head.

17:17It's a mirror.

17:18Another joke that I like to make.

17:19I'm so sorry if you just heard me say this.

17:21It kind of looks like cheesy broccoli, right?

17:23And I hate cheesy broccoli because it tastes so good, but it makes your broccoli into junk food

17:27again.

17:28I'm not eating broccoli for fun, okay?

17:30I'm eating it to try and be healthy, and I don't want to turn it back into junk food,

17:33and then I have to eat something else healthy.

17:38It's because I have family members.

17:42I'm not going to tell you who they are, but I have family members who just push cheesy broccoli

17:48on everyone, and then every time we go somewhere or we meet up or whatever, it's just like,

17:55stop trying to convince me that cheesy broccoli is a cool thing.

17:58I don't agree.

17:59Give me plain broccoli.

18:00All right.

18:01Anyway, so we have an identity line there.

18:04We've done a two-dimensional matrix.

18:06We've done undirected and weighted, and we're at about 20 minutes for this video already.

18:11So now you know how to make an undirected weighted graph and an undirected unweighted graph,

18:15if you watched the other video, with an adjacency matrix.

18:18Maybe one final thing I want to say in this particular video before we're finished.

18:23This is lightning fast to add an edge or remove an edge.

18:26Remember I said before we could represent this, this is really a one-dimensional array

18:31under the hood, right?

18:32But we can represent it to look like a two-dimensional array or an n-dimensional array.

18:37That means this is just as fast to access a cell as it would be in a one-dimensional array,

18:42which is constant time, which is incredibly fast.

18:44So if you want to add an edge or remove an edge, you just have to change a cell.

18:48I think we just added an edge going from 7 to 7, so we know how to add an edge.

18:53We just go to the appropriate row and column.

18:55But what if you want to remove an edge?

18:57I guess I almost forgot that too.

19:00Let's do remove the edge from the 5 to the 6.

19:05Let's kill this edge, right?

19:06What do we actually do?

19:08We go to row 5 and column 6, and we change that 5 to an infinity

19:15to say that the edge no longer exists.

19:17And then do the same thing for the column 5.

19:20Column 5, row number 6, is going to be infinity, meaning there's nothing there anymore.

19:29So to add an edge, we just went to a cell and modified a value to remove an edge.

19:34We did the same thing.

19:35That's going to be incredibly fast.

19:37That's going to be constant time.

19:38We're going to talk all about the pros and cons in terms of time complexity

19:41of adjacency matrices in a future video.

19:45But for now, I think that's pretty good.

19:47Thank you so much for watching this video.

19:49I hope you learned a little bit of stuff and had a little bit of fun.

19:51I'll see you in the next video.

19:53We're going to do directed graphs, unweighted and then weighted.

19:58Nice.

19:59Sorry.

20:01Hey everybody.

20:03Thanks for watching this video again from the bottom of my heart.

20:05I really appreciate it.

20:06I do hope you did learn something and have some fun.

20:09If you could do me a please, a small little favor, could you please subscribe and follow

20:14this channel or these videos or whatever it is you do on the current social media website

20:19that you're looking at right now.

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

20:25So we'll be able to do more videos, longer videos, better videos, or just I'll be able

20:30to keep making videos in general.

20:31So please do me a kindness and subscribe.

20:36You know, sometimes I'm sleeping in the middle of the night and I just wake up because I know

20:39somebody subscribed or followed.

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

20:43That's exactly what happens every single time.

20:45So you could do it as a nice favor to me or you could troll me if you want to

20:49just wake

20:49me up in the middle of the night, just subscribe and then I'll just wake up.

20:52I promise that's what will happen.

20:54Um, also, uh, if you look at the middle of the screen right now, you should see a QR code,

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

21:03bottom of this video.

21:04And it'll take you to my main website where you can just kind of like see all the videos

21:08I published and the services and tutorials and things that I offer and all that good stuff.

21:13And, uh, if you have a suggestion for, uh, uh, clarifications or errata or just future videos

21:22that you want to see, please leave a comment or if you just want to say, Hey, what's up,

21:25what's going on, you know, just send me a comment, whatever.

21:28I also wake up for those in the middle of the night.

21:30I get, I wake up in a cold sweat and I'm like, it would really, it would really mean the

21:35world

21:35to me.

21:36I would really appreciate it.

21:37So again, thank you so much for watching this video and, um, enjoy the cool music as,

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

Category

Transcript

Recommended