Transcript from the "Pseudocoding the addEdges() Method" Lesson

[00:00:00]

>> Bianca: Imagine now we have our matrixes initialized. We have some stuff in it, and now we want to start adding edges. How do we do that?

>> Bianca: First of all, what would we pass to an add edge function?

>> Male: A starting node and an ending node N1, N2.

[00:00:21]

>> Female: Yeah.

>> Bianca: Let's say V. V1, V2. So that's our two vertices. Some things to think about. Are they directed? Are they weighted? That kind of stuff, right? But we're not going to do that right now. So we're gonna add the edge. We have two vertices. They're already in a 2D array.

[00:00:56] Let's say the value is let's say two and four, and we want to connect them. And it's an undirected graph, which means that they both should be able to get to one another. So I could go from four to two, and two to four, no big deal.

>> Male: So, I mean, visually what that would look like is both the two points that represent two and four would both go from zero to one?

[00:01:28]

>> Bianca: Yeah, so matrix, so let's just say two. Let's see. Let's count. So two, four, and then four- Two. Four, two, yeah, two, four, right?

>> Male: Yes.

>> Bianca: Cool, so we're starting to get a feel here for what's easy to do with an adjacency matrix and what's a little bit more complicated, right?

[00:02:09]

>> Bianca: Adding an edge. Easy, right? Deleting an edge, we can guess. We can extrapolate from addedge. Perhaps it's also easy.

>> Bianca: What's the hard thing? The only other thing that we've done?

>> Male: The-

>> Female: The node?

>> Male: Adding a node.

>> Bianca: Yeah, adding a node. It opens up a lot of questions, right, for us?

[00:02:39] If we

>> Bianca: Have to expand our arrays, our nested arrays every time, think about that. Every array that you have,

>> Bianca: In here, right? So we had to add one to all of these arrays. So we had another row here. But then we have to also add another column.

[00:03:08] So that's a fairly expensive operation for literally adding one node, right? And then if we created the matrix ahead of time, and we don't necessarily know-

>> Female: What the capacity is.

>> Bianca: What the capacity is and then if we have to grow it. Again, these are all kind of some things that we have to think about when we're using adjacency matrix to represent our graph.

[00:03:32] However, adding edges, deleting edges, pretty simple. What about if we wanted to find a path? What if we wanted to know if we could go, and let's look at an undirected graph just for simplicity. What if we wanted to know if there was a path from one to six?

[00:03:58]

>> Female: Look for the binary value one. At one, six or six, one.

>> Bianca: Yeah, so that would be if we had a direct connection. But a path could go from one to three to four to five to six. Or another path might be one to two to four to five to six.

[00:04:17]

>> Female: This was totally an interview that I had to do.

>> Bianca: You had to [INAUDIBLE].

>> Female: Except it was using trains.

>> Bianca: Yep.

>> Female: And connecting cities.

>> Bianca: Yep, yep. Very common type of interview question graph actually.

>> Female: It was a recursive solution.

>> Bianca: Yep.

>> Male: So it was like-

[00:04:38]

>> Bianca: Path.

>> Male: I mean so you could like walk back, so look at the row six. You see all it connects to is five, so then you could move to five and you see that five connects to four and six. So you could move to four and you see four connects to two, three and five.

[00:04:56] So you could just keep following that and then see if you're able to get back to your starting point or do the opposite.

>> Bianca: Yeah. So there's a way to do it, right? It's just really complicated, especially when we have a lot of different connections going all different kinds of ways.

[00:05:15] It's not the most straightforward thing. And finding paths with graphs, pretty important.

>> Bianca: For most, so many graph algorithms are based on that. That's why this is called graphs and paths today.