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: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.
