How to Represent an Undirected Unweighted Graph with an Adjacency Matrix

Neural Lantern

Learn how to store an undirected unweighted graph inside a computer using an adjacency matrix. In this video we build a matrix of ones and zeros where each cell shows whether an edge exists between two nodes. Rows represent the starting node and columns represent the ending node. Because the graph is undirected the matrix ends up as a mirror image across the diagonal. We also cover how to add or remove edges by simply changing a cell value, how self-loops appear on the diagonal, and why this representation lets you check any connection in constant time. The computer only needs the connection data, not the physical layout of the nodes. Perfect if you are learning graph theory, data structures, or preparing for algorithm interviews.  adjacency matrix, undirected graph, unweighted graph, graph representation, graph theory, data structures, algorithms, adjacency matrix tutorial, graph algorithms, computer science, coding interview, edge list vs adjacency matrix, self loop graph, matrix graph, graph data structure  0:00 Introduction to Adjacency Matrix 1:16 Arrays as Two Dimensional Matrices 2:20 Ones and Zeros Represent Edges 3:44 Filling the Matrix for Node One 6:20 Completing the Remaining Nodes 10:38 Finished Matrix and Practice Advice 11:02 Computer Stores Only Connections 11:40 Mirror Property of Undirected Graphs 14:17 Adding and Removing Edges 17:31 Parallel Edges Are Not Supported 18:50 Conclusion and Future Topics  =-=-=-=-=-=-=-=-=  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:00Hey there! Let's talk about representing an undirected unweighted graph in your machine

00:05using an adjacency matrix.

00:17All right everybody, so I hope you've been watching my previous videos.

00:20I just did some videos on edge list representation. Before that, I talked about like the basics of

00:27graphs and like terminology and stuff like that. You don't need to watch the edge list videos if

00:31you're not interested in representing using an edge list, but you should probably at least watch

00:35the graphing video basics if you haven't. Okay, so what are we looking at right here? I've just made

00:41a graph. I made a random graph and I kind of like, you know, wired up a bunch of edges

00:47to make it kind

00:48of complicated. I then spent a whole bunch of time making this very beautiful two-dimensional matrix

00:55just for you. I'm sorry you couldn't watch me write it. You know, sometimes I'll have people

01:00say that they like when I yell at myself while I'm drawing something. Sorry, it took too long.

01:06But anyway, what we're going to do is take these concepts and put them together and we'll say

01:11this is how we can represent a graph inside of the machine. So what am I even talking about?

01:16Well, the first thing is imagine an array in your machine, right? An array of integers,

01:21like an array of, I don't know, doubles, you know, an array of whatever. So I'm gonna say like 5

01:26.4 and

01:27like, you know, 7.7 and 8 and, you know, like whatever. So I'm just like making an array of

01:32numbers.

01:32Probably a lot of you like this notation. But inside your machine, an array that is one-dimensional

01:39could be interpreted as a two-dimensional array. So this matrix up here on the top right of the screen,

01:46that's really a one-dimensional array inside of the computer. It's just that we choose to treat

01:51it as a two-dimensional array. And it's important to understand that you can jump to any cell in

01:56constant time, just like you can with the one-dimensional array, because getting to a

02:01certain cell is really just a simple mathematical formula. I think I'm going to do time complexities

02:06of this in a different video. So for now, I'm just going to say, here's how we represent the diagram.

02:13First off, let me label this so I don't forget. This is definitely... Where the heck is that?

02:19How come that's not working? Okay. This is definitely an undirected, unweighted graph.

02:29Trying to type with the pen in my hand. I have to change my brain. Okay.

02:34So this is an undirected and also unweighted graph.

02:39So for the purposes of this particular graph, if it's unweighted, that means in the cells,

02:44um, we're just, we're not going to put weights because there's no weight in the graph. I mean,

02:48you could, if you wanted to, just say that every edge was a weight of one if it was unweighted.

02:53But I'm going to say, let's forget about, you know, what is the actual value of an edge,

02:57because we don't really have that in this graph. And we'll just say that if an edge exists,

03:02then, uh, we'll put a, we'll put a one there. And if an edge does not exist, we'll put a

03:07zero in there

03:08at the corresponding cell. We'll talk about what cells mean, you know, what edges in a second.

03:12The other thing is because it's, uh, undirected, um, it doesn't actually matter

03:18whether we're describing a start node or an end node with an edge because it goes in both directions.

03:23So actually what's going to happen is this graph is going to be a mirror.

03:26I'll show it to you in a second, but, uh, for now we'll just say it's not going to matter

03:31what,

03:31what the direction is. Um, I like to do starting nodes as the rows, even though I just said that

03:37doesn't matter. It's just the way that I like to do things because it makes it easier to remember

03:41how to do this when you start to add direction to the graph. So one by one, I'm going to

03:46look at

03:47every single node and I'm going to chart what exactly is going on with that node in the two

03:51dimensional matrix. So I'm going to start, uh, I guess I'm going to go numerically because that's

03:55kind of easier. I'm going to start with a node index one. So I'm going to go here

04:01at row one, because I'm going to say that's my start node. And, um, where does the one node

04:06connect to? It connects to node number two. So, um, let's see, actually, I think I'm going to say that

04:14it is, uh, not self-connected. Some, I mean, if you, if you consider your graph to have by default,

04:19every node is connected to itself, you could put a one there across that little diagonal line that

04:24you see, but I'm going to put a zero saying that these nodes are not connected to themselves,

04:28unless we do a little loop from a node to itself. Maybe I should add that later. But, um,

04:34so node number one is connected to node number two. I'm going to write a one there to say that

04:38there is a connection. What do I mean by that? Just to clarify, um, this, uh, let's see, the one,

04:47two edge, that edge that I just highlighted in pink, that corresponds to this cell.

04:53So the, uh, start node, I'm going to do that in maybe orange, the start node is the row number.

04:59And maybe I'll do like, uh, I don't know, light blue or something, baby blue,

05:03for the destination node. And that's going to be the column number.

05:08So basically just like the row number is where the node, where you start, what node you start at,

05:13the column is what node you end at. Um, and then if you see a zero or a one in

05:19that particular cell,

05:20at that particular row and column, it'll tell you whether there's an edge there or not.

05:24So I'm going to duplicate this real fast so I can erase the markings I just made.

05:29And I'm going to say, oops, whoa, whoa, what's happening here? I want to get, dude,

05:38are you kidding me? Can I just erase it like that? Yeah. Okay. I keep thinking these are lines.

05:45I actually made a diagram in a different program. So these are not even lines. I can't even erase

05:48this. It sucks. So, um, we did the, uh, the two node. So I'm just going to quickly say the

05:55one is

05:56connected also to the three. Yes or no? Yes. That's a one. Uh, then the, uh, one node is connected

06:01to the

06:01four. Uh, yes. So I'm going to put a one. The one node is connected to the five. Yes. So

06:07I'm

06:07going to put a one, a lot of connections. This is pretty good. Uh, and then also to the six

06:11and

06:12not to the seven. So if it's not connected to the seven, I'm going to put a zero there.

06:16Okay. We do the same thing for the two node. So I'm going to start at the two node.

06:21Actually, let me duplicate this. Start at the two node. And I'm going to say,

06:26okay, we're now looking at the two node. Oh my gosh. Okay. Um, okay. I'm going to put a question

06:34mark, I guess we're looking at the two node and, um, well, is the two node connected to the one

06:42node?

06:43Yes. We just saw that was true. Uh, is the two node connected to itself? We said in this particular

06:48graph, there are no self connections by default because I want to be able to draw them. Uh, if that

06:53ends up being true, uh, is the two connected to the three? I see a connection there. I see an

06:57edge.

06:58So I'm going to put a one. Is it connected to the four? I don't see an edge. I'm going

07:01to put a zero

07:02to the five. Uh, yes, to the six. Uh, yes. And to the seven. Um,

07:12whoops, what did I just do? Uh, the two is not connected to the six. I was thinking of the

07:15one,

07:16uh, the two connected to the seven. Yes. Okay. So we just basically do this over and over and over

07:23again until you have a giant matrix of ones and zeros, which can very efficiently store, um,

07:30a graph. I mean, this is pretty much it. This is all you have to do. I want to do

07:34a, let's see,

07:34three is connected to, I'm going to say one, one and a two, and it's not connected to itself by

07:44default.

07:46Put a zero. It's connected to the four. Nope. It's connected to the five.

07:53Oh gosh. I got to make that even connects to the five. I'm losing my brain here. Uh, yes. And

07:59then,

08:00uh, three connected to the six, right? Three connected to the seven. Uh, no. Okay. Somebody

08:07leave me a comment, uh, if you have a correction. And then for the four, um, let's see, dude,

08:13this is getting out of control. For the four, um, I guess, I'm just going to look at the diagram.

08:23Pretty soon we're going to start realizing something fun about an undirected graph

08:27in that it is a mirror in this matrix. So technically you only have to do like one half

08:32of the matrix in your code if you wanted to. So I'm going to say the one exists, um,

08:38one. You know what I should have done? I should have just filled this whole thing with zeros

08:42and then change the zeros to ones. Um, okay. So the four is connected to the two. Yes or no.

08:48Nope.

08:49The four is connected to the three. Nope. Or it's connected to the, uh, four. We're going to say no

08:56by default. Or it's connected to the five. Nope. It's only connected to two things. Uh, it'll just be

09:04the seven, I guess. Okay. So we're going to put a nope there and then a yup for the seven.

09:08Okay. Then the five,

09:11uh, is connected to one, two, three, four. What if I just did a whole bunch of zeros and then

09:17I

09:17overwrote only the, the ones? That would probably be a little bit faster. Except for this first time

09:23I'm doing it. Okay. All right. And then I'll just copy paste this. Copy past. Okay. I should have done

09:30this. Should I edit that out of the video? I don't know. It's fun to watch my mistakes.

09:35So five to one. Yes. Five to two. No. Five to three. Yes. Uh, five to four. Nope. Five to

09:47five.

09:48We say no by default. Five to six. Yes. Five to seven. Yes. Okay. I think that was a little

09:54bit

09:54faster. Let's see how fast it is this time. Uh, the six is connected to the five. Well, let's say

10:00it's the one.

10:02And then, uh, the one, the three of five and a seven, right? Six, one, three, five, and seven. Okay.

10:10So I'm gonna be one, three, five, seven. That's probably right. Again, leave me a comment. If I

10:18screwed something up, I did not practice this. I'm just kind of winging it. The seven is connected to, uh,

10:23five, six, two, four, five, six. Okay. So I'm gonna do two, four, five, six. Whoops.

10:33That six didn't happen. Let me just do it again. Okay. All right. So now we have it. This is

10:39a, uh,

10:40an adjacency matrix that represents the graph that you see on the left. Um, keep in mind that if you

10:46saw

10:46a matrix, I mean, in general, you should probably practice doing this both ways, like look at a

10:51graph and then you, you know, generate the matrix, uh, that corresponds to the graph you're looking at,

10:56but also maybe you're presented with a matrix and you would draw the graph, uh, that the matrix

11:01represents. Try to remember that your computer, uh, in almost every program, it doesn't really know

11:05where these nodes are unless it's a drawing program or something. If we're just talking about

11:09relationships, which is what graphs are kind of good at, um, then your computer doesn't really care

11:14that the three is on the top. It doesn't really know that. Definitely not with this adjacency

11:18matrix representation. Uh, the three in the computer's mind could just be anywhere. It doesn't

11:23really even think of where the nodes are. It's just this node is connected to that node and that node

11:27is connected to that node and so forth. We just position the nodes somewhere because we're humans

11:32and it's fun to look at diagrams, but really this is all your computer knows. Just all these, you know,

11:38little connection numbers here. So, um, let me duplicate this and I'll show you something funny about an undirected

11:44uh, graph real quick. Let's see how much time 12. That's not too bad. So, if I do, let's see,

11:53I want to do a little highlighter here. I don't get a chance to do that very often. I'm gonna

11:56do a

11:57highlighter across this identity line, you know, the little diagonal. It's all zeros for self-connects.

12:02Maybe I'll change the, change that in a second. I'll make one of the nodes connect to itself, but, uh,

12:08notice how, if I do this in green,

12:12notice, oh, is the highlighter going to be green now? Keep screwing that up. Notice how we have a

12:18mirror happening along the identity line. So we have like some, some ones here, right? Uh, so we have

12:25like two, three, four, five, six in the one row. If we look at the one column, we'll also see

12:30two, three,

12:31four, five, six. It's a mirror. Uh, pick, you know, any other numbers you want. Let's look at the, uh,

12:36the three column. Uh, the three column has a one there, and then it's got another one and a one

12:41down below at the five and the six. So three is hitting two and five and six. Uh, let me

12:47look

12:47at the diagram just to make sure I'm doing this right. Three is hitting, uh, two and five

12:52and six. It should be hitting one also. Oh, right. I didn't highlight that because it was already

12:57highlighted by the other thing. Okay. So then let's look at the three row and see if we see a

13:01mirror also. So there's the, the two and then the five and the six. Notice how it's a mirror. You

13:07just

13:07tilt your head. Uh, and it really looks like a mirror. And sometimes I like to make a joke when

13:12I'm explaining this to people. Uh, you know, if you just kind of like tilt your head a little bit,

13:16it looks like some cheesy broccoli. I'm personally not a fan of cheesy broccoli. I mean, I love cheese.

13:22And if you put cheese on my broccoli, I'm going to be happy, but it turns what's what was healthy

13:29food into junk food. It's like, I'm going to be healthy. I'm going to have broccoli today. Good

13:33for me. Yay. I've earned a double bacon cheeseburger later, but then I put cheese all over the broccoli

13:39and suddenly it's junk food again. And it's like, I do get a little fiber and everything, but it's

13:43like not really being that healthy anymore. So what should I do? I should just get some more

13:48healthy food to make up for the junk food, broccoli. And then I'm going to end up putting

13:54cheese on the other healthy food. And then I just, it's like an endless cyclone. I just keep eating

13:58and eating and eating pretty soon. There's no room for a cheeseburger. I don't know what to tell you.

14:03Anyway. Um, so this is how you make an undirected, unweighted graph, uh, with an adjacency matrix.

14:09We'll talk about time complexities and other stuff in the future. Um, uh, oh, I should talk about how to

14:16modify edges. Okay. So first off, let me, let me create a self loop real fast. I'm going to create

14:20a self connect, but let's say that this four is actually connecting to itself, uh, with like a

14:26little self loop. Okay. So, oh shoot. How can I get rid of all those? Is that going to work?

14:33Yes.

14:34It's going to work. Yes. I should have duplicated this and drawn on the duplicate. Maybe I actually did

14:39that forgot about it already. I don't even know. Okay. Sometimes I have clever ideas and then I

14:46forget what I was doing. Then the ideas are just not that clever anymore. Yes. Okay. What about that

14:53highlighter? Okay. I seem to have screwed up the graph somehow. Nope. Okay. Forget it. Um, we'll just

15:07pretend that it's fine. So I added that four connection. So how do I modify the adjacency matrix?

15:14Well, the four, uh, row starting node with the four column ending node, uh, was a zero indicating no

15:21self connection. Now that I do have a self connection, I'll just put a one there for

15:25and four and that's it pretty easy, right? Let me duplicate this other one. So I don't have to

15:32erase that stuff a second time, a second time. And, um, what would we do if we wanted to, uh,

15:39well,

15:39let me actually, sorry, everybody, let me just do that for one more time. So I think I just erased

15:45the wrong thing. We'll say four and four is a one now. And so how can we say that, uh,

15:52some new edge has been added. Let's add an edge between one and seven. Pretty easy. We just go to

15:57the right spot in the adjacency matrix. Let me add a little orange line here. Adjacency matrix

16:03to connect number one and number seven. That would be, uh, we could do row one and column seven.

16:11So that's going to be a one. And then remember this graph is undirected, so it has to be a

16:14mirror.

16:15So that means, uh, row seven and column one also has to be a one. So it's still a mirror.

16:21It's pretty much it. And remember you can access these cells in constant time, which we'll talk about

16:25more in a future video. Pretty nice. How do you delete, uh, an edge? Let's pretend that we wanted

16:31to delete, uh, the connection between the five and the three. So I'm going to put maybe like

16:36a little squiggly line right here, squiggly line saying that that, uh, edge is gone. I can't

16:40actually erase that because this is a, I guess I could draw white over it, but you would still see

16:44that the blue lines are covered. So the five and three connection is gone now. How do we do that

16:50inside the adjacency matrix? Again, just look at the, uh, row five, column three, change that one

16:58to a zero and then row three, column five, change that also to a zero. Oops, not a nine. That's

17:05how

17:05you get rid of something. So you add something, uh, by just changing a number, you get rid of something

17:09by just changing a number. Self connects are pretty easy. Um, and then of course, after you make the

17:14matrix, you want to just double check that you did it correctly. I'm not going to do that right now.

17:18Maybe this is a good exercise for you at home. You can just kind of like look and try to

17:23find

17:23my mistakes because that's hilarious, right? Um, what else can I tell you? Uh, this particular

17:29scheme does not support, um, parallel edges or edges that, uh, start at the same start node and

17:36end at the same end node as well. I'm not really describing that very well. Uh, so for example,

17:41what if I had this, uh, three node that is connected to the two node and I wanted to add

17:46a second connection

17:47for some reason, like there are reasons to do that. I want to have another edge going from three to

17:52two

17:52and from two to three. So now this is a parallel edge. It's the same. It's an edge that connects

17:57the same two nodes as some other edge. How can I represent that inside of this matrix right now?

18:02I can't, but, uh, one way to do this is to say that every cell, where's the three and the

18:07two,

18:08there it is. Every cell in your matrix is not a one or a zero integer, but every cell is

18:14its own,

18:14uh, uh, individual linked list or array or vector or something that can hold multiple numbers.

18:21So just to add a little notation here, if, uh, if that's what I mean, then I can say, well,

18:27um, we'll just say that there are two edges by saying, uh, that cell has an array

18:35of two numbers, each number representing a connection, not the, not the greatest way to

18:40represent it, but in our future, uh, videos, we're going to do like under, uh, directed graphs

18:44and weighted graphs. It'll make a little bit more sense, but long story short, this is how you do it.

18:50Let's see. We did 20 minutes for this video. I think I'm feeling okay. There's lots of properties

18:55and other stuff that we can talk about with graphs, but for now, I'm just going to stop right here.

19:00Thank you so much for watching this video. I hope you learned a little bit of stuff and had a

19:03little

19:03bit of fun. Tell your friends and I'll see you in the next video. How do I stop the recording?

19:15Hey everybody. Thanks for watching this video again from the bottom of my heart. I really appreciate it.

19:19I do hope you did learn something and have some fun. Uh, if you could do me a please, a

19:24small little

19:24favor, could you please subscribe and follow this channel or these videos or whatever it is you do

19:30on the current social media website that you're looking at right now? Um, it would really mean the

19:35world to me and it'll help make more videos and grow this community. So we'll be able to do more

19:40videos, longer videos, better videos, or just, I'll be able to keep making videos in general. So please

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

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

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

19:59a nice favor to me or you could, you could troll me if you want to just wake me up

20:02in the middle of

20:03the night, just subscribe and then I'll, I'll just wake up. Uh, I promise that's what will happen.

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

20:12you can scan

20:13in order to go to the website, which I think is also named somewhere at the bottom of this video

20:17and it'll take you to my main website where you can just kind of like see all the videos I

20:22published

20:22and the services and tutorials and things that I offer and all that good stuff. And, uh,

20:29if you have a suggestion for, uh, uh, clarifications or errata or just future videos that you want to see,

20:36please leave a comment or if you just want to say, Hey, what's up, what's going on? You know,

20:40just send me a comment, whatever. I also wake up for those in the middle of the night. I get,

20:43I wake up in a cold sweat and I'm like, it would really, it would really mean the world to

20:48me.

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

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

Category

Transcript

Recommended