This course has been updated into a 4 part series! We now recommend you take the A Practical Guide to Algorithms with JavaScript course.

Transcript from the "Adjacency List" Lesson

[00:00:00]

>> Bianca Gandolfo: Adjacency list. This is what we're going to actually use for the things that we're usually interested in like finding paths and things like that, and finding neighbors that aren't just immediate. It's gonna be easier to do this with an adjacency list. So here we have our adjacency list, we have it just the order we put in the list to simplify our life, but we do know that this can represent other data, we talked about that.

[00:00:33] So here is our array, each Value in the array represents what?

>> Speaker 2: Vertices?

>> Bianca Gandolfo: All the vertices that are connected to that one. So we can see we have 1, 2, and 3. Sorry, 1 is connected to 2 and 3, so we have at 1 connected to 2 and 3.

[00:01:07]

>> Bianca Gandolfo: And this is a directed graph, so you can imagine that this might be a linked list, right? Linked list has a direction, if it was weighted we'd have a linked list with some more information in there like another .wait after .net that kind of stuff.

>> Speaker 3: That top line is just the way of saying that one is connected to bullet two and three?

[00:01:31]

>> Bianca Gandolfo: Mm-hm.

>> Speaker 3: Cuz it's looks like to me that looks like one is connected to two, two is connected to three

>> Bianca Gandolfo: Yeah, that's a good observation. So what this is saying is 1 is connected to 2 and 3. From 2 you can only go to 4, from 3 you can only go to 4, from 4 you can only go to 5, from 5 you can only go to 6, from 6 you can't go anywhere.

[00:01:56]

>> Speaker 3: Okay.

>> Bianca Gandolfo: Yeah.

>> Bianca Gandolfo: Okay. Mm-hm.

>> Bianca Gandolfo: All right.

>> Speaker 3: So that thing, that construct on the right is the adjacency list?

>> Bianca Gandolfo: Yep, these are adjacency lists. That's the one that you were looking at that has the nodes in the object.

>> Bianca Gandolfo: Mm-hm, question?

>> Speaker 4: And this table's saying that one connector to two two connector to three, one to two, three two, another graph?

[00:02:29] This shows one connector to two is connector two to three.

>> Bianca Gandolfo: Yeah.

>> Speaker 4: So splitting the

>> Speaker 4: Is that splitting things out cut after one row and just putting 1, 2, 3, but the definition under something is. There is connection to front to two, sorry, as the graph shows.

[00:03:05]

>> Bianca Gandolfo: No, from one to three. So this means, from one, you can either go to two or you can go to three.

>> Bianca Gandolfo: From two you can go to four. From three you can only go to four.

>> Speaker 3: So in this in the adjacency list you only look up.

[00:03:35] You only look at the leftmost number, and then you know everything. So no matter how long line 1 got there, it would only be referring what's connected to 1?

>> Bianca Gandolfo: Yep.

>> Speaker 3: Okay. And this is just a way of talking about what's in a graph?

>> Bianca Gandolfo: Yeah, it's a way of representing our graph.

[00:03:56]

>> Speaker 3: Where do I represent?

>> Bianca Gandolfo: And we'll explore some operations on it and we'll see why we would do it this way.

>> Speaker 3: Okay.

>> Bianca Gandolfo: Yeah.