Skip to main content
Neural Lantern
  • 14 hours ago
Learn how to represent a directed unweighted graph using an adjacency matrix. We cover why a two dimensional matrix is really just a one dimensional array under the hood, making cell access and updates extremely fast. For directed graphs the starting node is the row and the ending node is the column. A zero means no connection and a one means an edge exists. Self connections are not implied by default. Adding or removing an edge is constant time. Directed graphs do not produce a symmetric matrix like undirected ones. This is one practical way your program can store and work with a graph. If you have been following the previous videos on undirected graphs this builds directly on that. The next video will cover directed weighted graphs with an adjacency matrix. Thanks for watching and I hope you picked up something useful.

00:00 Intro to Directed Unweighted Graphs
00:01 Matrix Stored as Contiguous 1D Array
03:09 Building the Adjacency Matrix
04:25 Filling Outgoing Edges Node by Node
09:43 Directed Graphs Are Not Symmetric
10:36 Adding a New Edge
11:08 Adding Self-Connections
11:53 Removing an Edge
13:04 Adding Bidirectional Edges
15:28 Next Video and Outro

adjacency matrix, directed graph, unweighted graph, graph representation, data structures, graph theory, algorithms, computer science, adjacency matrix tutorial, directed graphs

=-=-=-=-=-=-=-=-=

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:00Hello there! Let's talk about representing a directed, unweighted graph inside your machine using an adjacency matrix.
00:08It's going to be fun!
00:20Okay, sorry about that. Anyway, um, so I hope you've been watching my previous videos.
00:24We covered already how to do an undirected weighted graph and also unweighted graph using an adjacency matrix.
00:31We're going to basically represent a graph inside of the machine.
00:35Like, this is one of the ways that your machine can do it.
00:38We're not going to talk about code exactly, but, you know, kind of allude to code.
00:41But this is a really good way to, you know, get started in practicing the concept.
00:45Okay, first thing I want to say, I've said this in my previous videos, I'm sorry if you've been watching
00:50all of them,
00:51is that this matrix, this two-dimensional matrix, it's really just a one-dimensional array.
00:56Think about this, we have some numbers in an array. I'm going to put six numbers in there.
01:01We could just as easily represent this as a two-dimensional matrix, a two-dimensional array, right?
01:08It's the same amount of numbers.
01:10What's really happening under the hood when you have a two-dimensional array,
01:13is your computer just has it as a one-dimensional array.
01:16Okay, so the question is, why is that useful?
01:22Oh, hang on.
01:23Okay, anyway, so what I wanted to say is that you see a two-dimensional matrix,
01:27but really what's happening inside your computer is a one-dimensional matrix.
01:30I'm just going to make a one-dimensional matrix.
01:32I'm going to say we're putting numbers in the matrix.
01:34I'm just going to put like, you know, six hashes or pound signs or hashtags in the modern era.
01:41So a one-dimensional array could be represented as a two-dimensional matrix if we just reformat it a little
01:48bit.
01:48Notice how I'm just, you know, placing, you know, the last part of that first array on a second line.
01:54That's what's happening in the computer.
01:56Even if you're working with a two-dimensional array in your computer,
02:00it's still just a one-dimensional array under the hood,
02:02which means it's incredibly fast to access one particular index.
02:07Not necessarily to scooch things, remove things, and add things.
02:10But if I wanted to go to index three in a one-dimensional array,
02:14if you know time complexities already, that's really fast.
02:17That's constant time.
02:18We'll do time complexities in another video.
02:20But if I wanted to access, you know, a certain row in a certain column,
02:25intuitively you think, well, I got to like scan down and scan to the right.
02:28So maybe it's slower, but it's not because it's still just going to be math to find exactly the right
02:33offset
02:34in your two-dimensional matrix because it's really a one-dimensional array.
02:38All of the items in this array, I didn't say this in previous videos,
02:43all the items in this array are contiguously allocated.
02:46So all we really have to do is compute an offset from some starting memory location.
02:50So it's incredibly fast to read a cell in this matrix and to modify a cell in this matrix.
02:57You'll see in a second, well, you'll see in several minutes why that's one useful feature of an adjacency matrix.
03:04Okay, so adjacency matrix.
03:07Suppose you're presented with this diagram you see right here.
03:10This is a graph.
03:11It's got direction on all the edges.
03:13I really hope I didn't forget any particular edge.
03:15I think I've got arrows on all of them.
03:18We've got nodes and edges, and I just need to figure out how can I put that into a matrix
03:21so my computer, my program understands the graph and it has a representation of the graph.
03:28So with directed graphs, the start row, sorry, the start node and the end node actually matter a lot.
03:35In my other videos where we talked about undirected graphs,
03:37we could just easily swap the row and the column in this matrix and it didn't really make a difference
03:42because the whole matrix was going to end up being a mirror anyway.
03:45But that's not going to happen this time.
03:47So what I'm going to say for the way that I like to do things is the starting node is
03:52the row
03:53and the ending node is the column.
03:55So this is also an unweighted diagram, an unweighted graph, so we don't really need to store floats
04:02or infinities or anything like we did in the other video.
04:05We can just say that no connection means no connection is a zero and yes connection is a one.
04:11Of course you could still do that with floats if you want to, but whatever.
04:15You could have a matrix of booleans if you really wanted to, like true and false and true and false.
04:19But you know, for this diagram we're going to say zero and one.
04:22So I'm going to start with node number one and node number one therefore is going to be the source
04:28node
04:28and I'm going to see where does it go out to, what edges are outbound from the number one.
04:33So the start node is the one, that means the row is one that I'm working with
04:37and the destination nodes or the end nodes or the sync nodes, those will be the columns.
04:42So I'm not really going to look at how six is coming into one
04:46because I'm only interested right now in what one starts in terms of an edge.
04:53You know, what edges come out of one.
04:55So one, forget about the six and the two, those are incoming edges.
04:59I'm just going to look at the outgoing edges.
05:01So one goes out to three and four and five.
05:05So by default in our diagrams, at least at this point, we're going to say that self connections are not
05:11implied.
05:13Meaning by default, if I don't see an actual edge on the diagram going from one back into one,
05:19then I'm going to say one is not connected to itself.
05:22So I'm going to put a zero to say there's no connection.
05:27One going to the two, that's not happening because two is actually going into one.
05:33So I'm going to put another zero then there.
05:36One going to three, that is happening.
05:38So I'm going to put a one.
05:39So one does have an outbound connection or an edge to three.
05:42So I'm going to put a one in that row and column.
05:45One going to four, yes.
05:47So I'm going to put a one.
05:48One going to five, yes.
05:51So I'm going to put a one there.
05:53One going to six, no.
05:57So I'm going to put a zero there.
05:58I should have put, you know, edges that go back and forth to make this more interesting.
06:03But you can probably imagine.
06:05Well, I'll add that maybe later in this video.
06:08So one going to seven, nope.
06:11So I'm going to put a zero.
06:13So that's the first row.
06:14We represented all of the outbound edges from one to some other node.
06:19And we used a zero to say it doesn't exist and a one to say it does exist.
06:23So then we just move on to the two.
06:25So if I'm focusing on the two node, then I'm on the two row and its outgoing connections are going
06:31to be represented in the columns.
06:33So does two go to one?
06:35Yes.
06:35I'm going to put a one there.
06:36Does two go to itself?
06:39Self connections are not implied at this point.
06:41And then, hang on a second.
06:45Does two go to three?
06:47Nope.
06:48Because three goes into two and not the other way around.
06:51We'll add those other edges in a second.
06:54Does two go to four?
06:55Nope.
06:57Does two go to five?
07:00Nope.
07:01Does two go to six?
07:04I don't see that.
07:06So I'm going to say nope.
07:06Nope.
07:07And then does two go to seven?
07:09Yes.
07:10I'm going to put a one.
07:11So now we're done with the two.
07:13This is a directed graph by the way.
07:15So like I said about my previous videos, we will not see a mirror.
07:20At least we won't necessarily see a mirror.
07:21We might accidentally make a mirror depending on what the graph is, but we're not going to see a mirror.
07:26So we have to do this whole graph with no shortcuts.
07:29So the three, does it go out to the one?
07:32That's a no.
07:33Does it go out to the two?
07:36Where the heck is the three?
07:37Oh yeah, it goes out to the two.
07:41No implied self-connections.
07:43Three goes to the four?
07:45Nope.
07:47Three goes to the five?
07:49Yes.
07:51Three goes to the six?
07:54Nope.
07:56Nope.
07:56Three goes to the seven?
07:58Nope.
07:59Okay.
07:59So now we're done with the three.
08:02And then we'll say now does four go to the one?
08:05I'm looking at the four.
08:06Where the heck is the four?
08:06I'm losing the four.
08:07Oh, four doesn't go anywhere except for the seven.
08:09So I can actually just put like zeros in this whole thing, just to save a little time.
08:16Hmm.
08:19Oh God.
08:21Okay.
08:22There we go.
08:23But the four does go to the seven.
08:24So I'm going to put a one right there.
08:25Okay.
08:26So, uh, the five, um, it has outbound connections.
08:31I'm going to, I'm going to be cheap here.
08:32I'm going to be cheesy.
08:33The five goes to six and seven.
08:35So I'm just going to put zeros everywhere else.
08:37So, whoops.
08:40In fact, I probably could have just copied that whole row of zeros.
08:45And then just overwrote the last two, but I guess.
08:48So the five goes to the six.
08:50That's a yes.
08:51The five goes to the seven.
08:52That's a yes also.
08:54And then we're ready for the six.
08:55The six has three outbound connections.
08:58One, three, and seven.
09:00So I'm just going to, you know what?
09:02I'm just going to copy a whole row.
09:03I wish I had a whole row of zeros.
09:05And I'm going to maybe change that to a zero real fast.
09:09And then I'm going to say, all right, where does, where does six actually connect to?
09:12Let's change those zeros to ones.
09:14Six connects to the one and the three and the seven.
09:22Okay.
09:22So one goes to one, three goes to one, and seven goes to one.
09:29Okay.
09:30Then the seven has no outbound connections.
09:33So this is indeed a row of zeros.
09:36Maybe I could have done that one first.
09:37It would have been fun.
09:38Oh, well.
09:39Notice one more time that there's no mirror.
09:41So if we like, you know, if you trace your eyes along this identity line right here,
09:46and you were expecting to see a mirror, you would be sadly disappointed.
09:50Because what would actually happen is not a mirror.
09:54Let me do the highlighter here.
09:56And we'll say we have like an identity line that goes down the middle.
10:00And then I'll just try to highlight some stuff.
10:03Let's see the three, four, five, six over here on row one and those columns.
10:08Let's go now to column one and notice how it's like not the same three, four, five, six.
10:16So that's not a mirror because those numbers don't match.
10:20So there's no mirror in directed graphs in terms of the matrix.
10:24Anyway, let's see.
10:27I'm going to get rid of these little pound signs, these hashtags.
10:32The next question is, let's do a self connect.
10:35How do we add an edge?
10:36Like if I wanted to add an edge from a, you know, one to seven, for example, actually, let
10:43me duplicate this first.
10:44And then we'll work on it.
10:45If I just wanted to add a brand new edge going from one to seven, then I just have to
10:52make sure that I look at the row one and then look at the seven column and then just change
10:57that value to a one to say, did I do that?
11:01Yeah.
11:02To say that the edge now exists, right?
11:04So that's pretty easy to add a brand new edge.
11:06Let's look at self connects.
11:08Now, just in case, if I wanted to say that four connects to itself, I have to do an arrow,
11:14by the way.
11:14Did I do an arrow on the last one?
11:17Yeah.
11:18Okay.
11:19Four, we're saying now it connects to four.
11:21So before we assumed that there were no self connections by default.
11:25So all the nodes had no self connections, but the four, we just added a self connection.
11:29So that means right here, that zero is going to change to a one.
11:33Pretty easy and fast to add an edge.
11:36And by the way, how fast was it to just access a cell and modify a value?
11:40It's constant time.
11:42Again, big O is going to happen in other videos, but this is lightning fast for adding
11:47and removing edges.
11:49Okay.
11:49So then the other thing is, let me see, can I do, oh, I got to get rid of that.
11:56How do we remove an edge?
11:57Oh, bro.
11:59Bro.
12:01What's happening here?
12:02Can I just select that?
12:04Oh, how do we remove an edge?
12:07Uh, we talked about this in other videos, uh, for our adjacency matrix, but it's pretty
12:11easy.
12:11We just say, all right, suppose I just want to kill this edge going from three to two.
12:15So now there's no connection, no edge going from three to two.
12:19Um, well, I just have to go find the appropriate part of the matrix and that's it.
12:24So row three, cause three was the start node or the source node, row three, and then two
12:29is the destination node.
12:30So I'm just going to like overwrite that with a zero.
12:33And now we have effectively removed an edge.
12:35Remember the computer doesn't actually see this diagram that you're looking at on the
12:40left.
12:40The computer just has the matrix.
12:42The computer doesn't really even need to know that the, that the three is on top visually.
12:46It just needs to know what the three is actually connected to.
12:49At least most applications of graphs, there are some where it's more visual.
12:54And so there needs to be like some coordinates, but just the easiest and most simple way right
12:58here with an adjacency matrix doesn't need that.
13:01Okay.
13:02So then the next thing I want to do is, um, I want to add edges that kind of like
13:08point
13:08towards, you know, two nodes that sort of point towards each other.
13:12Like, you know, opposing, this is going to work.
13:15Yeah.
13:16Opposing, uh, edges.
13:19That's not a technical term.
13:20So suppose for the sake of argument that you're looking at the three and you say, well,
13:23the three can go outbound to the two, but can the two go outbound to the three?
13:28Yeah, totally.
13:29I'm going to draw an edge to represent that.
13:31That's the case.
13:33Okay.
13:33So I now have two edges, each going in a different direction between the three
13:37and the two.
13:37And by the way, in your mind, you might be thinking, Hey, isn't that what, what undirected
13:42graphs are doing?
13:42Yeah.
13:42Basically you have just an edge that goes in both directions.
13:45Here we have to draw two separate edges.
13:48Then we just have to update the matrix to match.
13:51So I added an edge going from three to two.
13:53So I'm going to go row three and then column two.
13:56And, um, oh, sorry, sorry.
13:59Row three was the source originally, which worked from three to two.
14:02That's why, that's why there's a one there.
14:04But now I just added an edge from two to three.
14:06So we look at row two and then column three.
14:09And then I update that, uh, to match.
14:12So that zero became a one and it did become a little bit more like a mirror.
14:16If we went ahead and added these like, you know, opposing edges on every single pair of
14:21nodes, uh, then the matrix would start to look like a mirror.
14:26Anyways, what else can I talk about?
14:28We're at about 16 minutes and I've lost my mouse cursor.
14:32What the heck?
14:33Oh, there we go.
14:34I need, I need accessibility controls.
14:37You know, it's true.
14:38Actually, I really need glasses.
14:39I've needed glasses for a couple of years, maybe like five years.
14:43And for some reason, I just can't get myself to go.
14:46So what's happening now is when people show me memes on their phones, my face goes, it goes
14:51backwards like this.
14:52It's like a, it's like a repellent for my face.
14:55If you show me a meme, I'm like, not, not fun to live that way.
15:01So I got to get glasses.
15:02Should I get a chain?
15:03I want a gold chain that's like studded and like blinged out.
15:06And then like, I have the glasses here only when I need to read.
15:08And then it hangs the rest of the time and it maybe it plays music or something.
15:12I don't know.
15:14I don't think I'm going to go that far.
15:16So when we did undirected, unweighted, I'm just trying to make sure that I didn't forget
15:19anything.
15:20There's no cheesy broccoli in this video directed and unweighted.
15:24Yeah, I guess that was it.
15:26Okay.
15:26So we're at the end of this particular video.
15:28I'm going to do one more before we shift topics.
15:31The next one is going to be how to represent a directed and weighted graph inside the machine.
15:38Using an adjacency matrix.
15:40Okay.
15:41Thank you for watching this video.
15:42I hope you learned a little bit of stuff and had a little bit of fun.
15:45I'll see you soon.
15:47I'm going to go have a burrito.
15:50No, I'm not.
15:50I'm just going to keep recording.
15:53Hey everybody.
15:54Thanks for watching this video again from the bottom of my heart.
15:57I really appreciate it.
15:58I do hope you did learn something and have some fun.
16:00If you could do me a please, a small little favor.
16:03Could you please subscribe and follow this channel or these videos or whatever it is you
16:09do on the current social media website that you're looking at right now.
16:12It would really mean the world to me and it'll help make more videos and grow this community.
16:17So we'll be able to do more videos, longer videos, better videos, or just I'll be able to keep making
16:22videos in general.
16:23So please do me a kindness and subscribe.
16:27You know sometimes I'm sleeping in the middle of the night and I just wake up because I know somebody
16:31subscribed or followed.
16:32It just wakes me up and I get filled with joy.
16:34That's exactly what happens every single time.
16:37So you could do it as a nice favor to me or you could you could troll me if you
16:40want to just wake me up in the middle of the night.
16:41Just subscribe and then I'll just wake up.
16:44I promise that's what will happen.
16:47Also if you look at the middle of the screen right now you should see a QR code which you
16:51can scan in order to go to the website which I think is also named somewhere at the bottom of
16:55this video.
16:56And it'll take you to my main website where you can just kind of like see all the videos I
17:00published and the services and tutorials and things that I offer and all that good stuff.
17:07And if you have a suggestion for clarifications or errata or just future videos that you want to see please
17:14leave a comment.
17:15Or if you just want to say hey what's up what's going on you know just send me a comment
17:19whatever I also wake up for those in the middle of the night.
17:21I get I wake up in a cold sweat and I'm like this it would really it really mean the
17:27world to me I would really appreciate it.
17:28So again thank you so much for watching this video and enjoy the cool music as I fade into the
17:36darkness which is coming for us all.
17:39happy now.
18:06So thank you so much.

Recommended