Adjacency Matrix

[00:00:00]
>> Bianca Gandolfo: And we're gonna talk about the implementation, right? I asked you guy to think a little bit about how this might look in code. And we're gonna break it down.
>> Bianca Gandolfo: Okay, so what data needs to be stored? Two main things, right, we need you to have the objects.

[00:00:21]
And the relationships, right? So the object is being our food or our people and or our people and the relationships being the lines or edges.
>> Bianca Gandolfo: Cool, we're gonna be using numbers to simplify, but you can imagine that this could be anything. Some data structures you need the value to be comparable, right?

[00:00:48]
So we can compare like greater or less than something like that. And those numbers are important for that. But in a graph, we're still flexible but we just use it for simplifying a label. Okay, so there are three main ways to represent a graph. I'm going to tell you about two, and I'll give you a recommendation about which one to use in an interview setting.

[00:01:19]
And I also want you to be open minded, like I've been saying this whole time. That this is computer science, there are many ways to solve lots of different problems. And it's up to you to think critically about your particular problem that you're solving. Whether it's on the job, or at work, or whatever it may be in your mind, I don't know, to model it to suit your needs, cool.

[00:01:44]
So the first one is the adjacent matrix and we're going to use that to create our graph, right? Because we can't code just circles and lines we have to deal with what we have access to. Right, we have ones and zeros, and we have, you know, one through five as well, but that's not what this is.

[00:02:13]
This is a matrix. Have you guys worked at all with matrices? Yea, a little bit. Like in math class, maybe. So the adjacency matrix, a matrix is basically an array inside of an array, right, when we get down to it. It looks something like this. I like this picture better though.

[00:02:39]
And so how we are modeling the relationships here is with the ones and zeros, okay? How we're modeling the data itself is through these vertices. So one is one. So one does not have a relationship with itself. So is zero okay. 2 is connected to 1, as we can see here with this line.

[00:03:04]
So we add a 1 here, and we also add a 1 here. And so on and so forth. So here our Edges. Here are our Vertices.
>> Bianca Gandolfo: Cool? Yeah.
>> Speaker 2: So 3 is connected to 0?
>> Bianca Gandolfo: So 3, we can look at 3 is connected to 2. 3 is also connected to 4.

[00:03:34]
>> Speaker 2: I see. Okay.
>> Bianca Gandolfo: And that's it. Yeah.
>> Speaker 3: So shouldn't 1 and 1 should also be 1? I mean, that's called a self loop and in this case we don't have self loops.
>> Bianca Gandolfo: Yeah.
>> Speaker 4: I'm kind of confused where did we lose the people in the whole equation.

[00:03:59]
>> Bianca Gandolfo: Yeah. Where did we lose the people? We'll get there. We're gonna start with this and then the people will be back. You have a question.
>> Speaker 2: This is a dumb question, but oaky, one is connected to, okay I get it. Now I get it. Never mind.
>> Bianca Gandolfo: Okay, cool.

[00:04:20]
>> Bianca Gandolfo: All right, so Adjacency Matrix. Here's the code. Awesome, okay. So now that we know that this is a 2D array, we wanna add an edge, and an edge is a relationship. How do we represent an edge again? With the number One or zero?
>> Speaker 3: One, one is the edge zero is the lack of an entrenched.

[00:04:46]
>> Bianca Gandolfo: So we'll pass like a couple of vertices and we will set it to one. So our adjacency matrix, we can call it this, we have v1 at v2, right? Equals to 1. Of course this is not exact, this is a little bit naive. Right, there's a little bit more that needs to happen here, right?

[00:05:08]
Because this is actually the 0th index for example, it's not 1. But you can imagine, right? It's pretty simple, right? We're just kinda toggling these values to add an edge.
>> Speaker 4: So the v1 is this way, v2 is that, down this way?
>> Bianca Gandolfo: So the v1 and the v2, these are just variable names so we could.

[00:05:44]
For example, call this, I wish this is, it used to let me edit this.
>> Speaker 2: Why do you wanna add an edge? I mean, maybe there's.
>> Bianca Gandolfo: Why you wanna add an iedge? Like what if, for example, like I suddenly started to also like eggs.
>> Speaker 2: Okay.
>> Bianca Gandolfo: And then I wanna have that relationship represented.

[00:06:05]
>> Speaker 2: Maybe I'll, afterwards.
>> Bianca Gandolfo: Yeah, do you wanna add an edge. So what if like, I wanted to, say this was a map, right? This is a city, and these are like intersections and these are roads. And actually let's say these are points of interest and these are roads between them.

[00:06:23]
Let's say that it's approved and we're gonna build a row between these two points of interest. So we wanna add a new Edge to connect these, yeah.
>> Bianca Gandolfo: And another thing that we'll talk about soon is, what if we wanna add another point of interest? So that would be adding a node to our graph.

[00:06:47]
Another interesting thing, is that you can add a node to a graph, even if there's no edge. So you can have sort of like these disconnected components. That's kind of fun, so we'll talk more about that. Okay, so we add in an edge, this is just adding an edge and removing an edge, very similar, we set to zero.

[00:07:11]
Again, don't copy and paste this, this is not actual code, it's just kind of demonstrating, right? Like we don't [INAUDIBLE] actually isn't defined, you're gonna get errors but this just. To get the gist. Do you guys get the gist? Is it working? Okay, awesome, all right, time complexity for adding an edge.

[00:07:37]
>> Speaker 3: Constant time.
>> Bianca Gandolfo: Constant time, removing an edge?
>> Speaker 3: Constant.
>> Bianca Gandolfo: You guys are good at this. All right, so that's adjacency matrix.