Check out a free preview of the full Data Structures and Algorithms in JavaScript course:
The "Implement a Graph Solution" Lesson is part of the full, Data Structures and Algorithms in JavaScript course featured in this preview video. Here's what you'd learn in this lesson:

Bianca walks through the solution to the Implementing a Graph exercise. While she does not cover each method in the solution, the full codebase for the solution is located on the "solutions" branch in the Github exercise repository.

Get Unlimited Access Now

Transcript from the "Implement a Graph Solution" Lesson

[00:00:00]
>> Bianca Gandolfo: Here's a solution for the implementation of our graph with an addNode and addEdge. We are representing our adjacency list as an object. This allows us to do constant time look up on permanent values so you can save numbers, you can save strings and such. Here and just look it up in real time versus when we were using our example with an array, right?

[00:00:30] It constrains us to only using numbers, asterisks, not 100% true but let's go with that. So, object is better, we have a little more flexibility there.
>> Bianca Gandolfo: Great. So, we are going to, add a node, we have just a catch here, it's under final return. Otherwise, just like we would do in our pseudo code, we are going to add,

[00:01:07]
>> Bianca Gandolfo: A key to our object.
>> Bianca Gandolfo: And have it equal either itself, if it exists, or an empty array. Let's break that down a little bit. We´re gonna say myGraph = newGraph. Right, we´re just gonna initialize that. If we did a console.log, of our graph right now, it would look something like this.

[00:01:43] Does that surprise anybody? No? Okay, good. So, we say myGraph.add, no, add node and we're gonna add the node asdf. Let's use some strengths to mix it up. I have to see a circle with a number in it, a line, again it's gonna make me go crazy. [LAUGH] I don't know.

[00:02:16] Okay, so now what does our adjacency list look like? It's gonna look like this. We have asdf, right. And this is what we are doing here on line seven. So we're looking at notes value, right? We're just doing a look up on the object and we're saving a value here which will either be node set value, right, we do a look up, there is no asdf.

[00:02:48] So we're gonna go to the right and we're gonna initialize it as an empty array. So we see here we have asdf and then we just put an empty array right there. And so that's our adjacency list with one item in it, no edges. Okay, so now let's add,

[00:03:11]
>> Bianca Gandolfo: Actually, who has pets here? Who loves animals? Who is capable of making up names for pets? All of us, I'm glad we have an inclusive game here. Okay, so this is gonna be our pet name list. Some of them are going to be friends, and we'll just have our relationships between them.

[00:03:34] Instead of add edge, we can call it make friend. So every edge we add is when you go to the dog park and they sniff each other and stuff and then they become lifelong friends. I think that's the process. We can pseudocode that one out later, but anyway, I think you get the picture.

[00:03:53] We're gonna add pickle so pickle. I think pickles is a better name for an animal plural. Okay so we have pickles, and then who's got a pet? What's their name?
>> Speaker 2: Dobby.
>> Bianca Gandolfo: Dobby like from Harry Potter? Okay and that's a great name. So now our adjacency list looks like this nodes.

[00:04:27]
>> Bianca Gandolfo: Pickles, comma, there we go. Dobby, and then since Dobby does not exist yet, we just initialized it, it's just empty. Who here has a pet named Pickles? No one, who else here has a pet name, any pet name?
>> Speaker 3: Gibson.
>> Bianca Gandolfo: Gibson, you guys have good names.

[00:04:58]
>> Bianca Gandolfo: Gibson, and so now our. What could be a social network for animals like pawbook or something, I don't know.
>> Speaker 3: Pawbook's good.
>> Bianca Gandolfo: Pawbook or furbook, furbook, furbook.
>> Speaker 2: What if they don't have fur? Well, what if you don't have a face? [LAUGH] You know? [LAUGH] I'm really good at these insult wars.

[00:05:33]
>> Bianca Gandolfo: Really though, you don't have to have a face to part of Facebook. [LAUGH] I think we're all so tired. Okay, so here we are. We're adding nodes and if we were to sort of draw this, we would just be drawing circles and space because they're not connected.

[00:05:57] Least useful graph ever.
>> Bianca Gandolfo: Okay, so that's where the addEdge comes into play. So here we are.
>> Bianca Gandolfo: Let's add some edges. So who do you think Pickles,
>> Bianca Gandolfo: Makes friends with first?
>> Speaker 3: Probably Dobby, Gibson's kinda stand-offish.
>> Bianca Gandolfo: Okay, we're at the dog park, or at the cat park, and Dobby and Pickles meet, and they become life-long friends.

[00:06:35] Because we don't have a remove edge in this graph.
>> Speaker 3: [LAUGH]
>> Bianca Gandolfo: So once you become a friend, you're always gonna be a friend forever. So that's okay, there's something sweet about that. Okay, I'm gonna move our picture down as well. Okay, what does this do? We're gonna have dobby and pickles.

[00:06:57] We have value1 and value2. So,
>> Bianca Gandolfo: If for whatever reason these things don't exist yet,
>> Bianca Gandolfo: Then we are gonna say this is invalid,
>> Bianca Gandolfo: Yeah? We might even wanna say, hey, why don't we add the one that doesn't exist yet? We could maybe initialize it, I don't know, maybe.

[00:07:24] So, this is undirective, so we're gonna add both of these values into the other person's list, okay? So value one dobby, right? So this is the lookup, and we're gonna pushing pickles into dobby's friends list, okay, for a book. So who do we, dobby, pickles, okay. So here we go Pickles is there, and then we also do the opposite.

[00:08:03]
>> Bianca Gandolfo: So now we know that pickles and dobby have a connection forever. And what that would look like In a graph would just be right. So we just have a connection like that. All right, let's make more friends with our pets. Let's see we'll have Gibson will make friends with dobby.

[00:08:41] And so, we're gonna add the edge, so we're gonna add dobby to gibson.
>> Bianca Gandolfo: And then we're also going to add gibson to dobby.
>> Bianca Gandolfo: Cool and now what we just did is we just added this connection.
>> Bianca Gandolfo: Cool and now if we wanted to add pickles, right?

[00:09:24] Then we would have to put pickles inside of Gibson's friend list and then we'd have to put Gibson inside pickles' friendship list. Cool and then that is, represents this relationship. Something like that. So now we have graph though it really like, friend, yehey.