Prepare for a technical interview by learning about the graph data structure and basic traversal algorithms like depth-first search (DFS) and breadth-first search (BFS). https://fireship.io/courses/javascript/interview-graphs/

#compsci #JavaScript #100SecondsOfCode

Install the quiz app 🤓

iOS https://itunes.apple.com/us/app/fireship/id1462592372?mt=8
Android https://play.google.com/store/apps/details?id=io.fireship.quizapp

Upgrade to Fireship PRO at https://fireship.io/pro
Use code lORhwXd2 for 25% off your first payment. 

My VS Code Theme

- Atom One Dark 
- vscode-icons
- Fira Code Font
2024-02-04T06:14:08.630Z
nova-2
2-general-nova
2024-01-09.29447
30089e05-99d1-4376-b32e-c263170674af
53959ee7-5462-408b-8661-a023f83bd70c
ece39b70b555c5fa4c89fe049dc53ebdda76ba28043075d686c19e6e86e393b7
67875a7f-c9c4-48a0-aa55-5bdb8a91c34a
deprecated
A graph is a nonlinear data structure that contains nodes and edges.
A node or vertex is just a single unique value, while an edge represents a connection or relationship between 2 of these nodes.
Think of something like Instagram.
Every user is a node.
Every time you follow a user, you create a new edge connecting 2 nodes together.
This is known as a directed graph because the relationship flows one way.
The follower follows the followee and not vice versa.
Now consider Facebook.
Your edges on the graph are friendships.
This relationship goes both ways, which is known as an undirected graph.
Graphs can to be weighted, which means the node has some additional data about the relationship, like the distance between 2 airports.
A node might also point to itself, like an airplane that takes off and comes back to land at the same airport.
This is known as a cycle.
Graphs are used in many real life software products, and you'll often be asked to represent a graphic code in in a technical interview.
One way to represent a graph is with a 2 d array or adjacency matrix.
Create 1 row and 1 column for every node.
When 2 nodes have an edge or connection at a one at the point they intersect.
This makes it fast and easy to look up a specific edge or to add a new edge.
But as a 2 d array, it takes quadratic space complexity and quadratic time to insert a new node into the graph.
An alternative approach is an adjacency list.
In this representation, we start with a collection of nodes, then each item has its own array of its neighbors.
This makes it faster to iterate over a node's edges and is more efficient with memory, especially when you have many nodes and few edges.
In your interview, you'll likely need to traverse your graph.
One option is a depth first search.
Start with any random node, go to its first child, then its first child, and do that for as long as you can.
When there are no more children, backtrack to the last node and continue the process.
A this algorithm is usually implemented with a recursive function.
Another option is a breadth first search.
From your starting node, add all of the direct children to a queue.
Once they've been visited, a move on to the grandchildren and continue following this pattern in layers.
This has been graphs in 100 seconds, but hang out for a few minutes because now we're going to implement these algorithms in JavaScript.
If you're new here, like and subscribe, hit the like button, open your IDE, and get ready to go beyond 100 seconds.
A as a developer, you'll come across all kinds of different real life implementations of graphs.
I mentioned Facebook's social graph at the beginning of the video, and they're commonly used for recommendation engines, like Yelp, for example, to connect businesses to users to reviews, or Netflix to connect the movies that you watch 2 movies that you might want to watch in the future.
They're also used to represent geographic data.
For example, on Google Maps, you can think of every intersection as a node a and then every road and its distance as the edge connecting these two nodes.
Over the next few minutes, we'll implement a basic graph in JavaScript based on the flight connections between airports.
A in this case, every airport is a node, and the edge represents whether or not you can fly from one airport to another.
This edge could contain additional information like the kilometers between the two a words, in which case that would give us a weighted graph.
The routes between 2 airports could be one way or two way.
When they go one way, we have a directed graph.
A if they go both ways, it's an undirected graph.
For this demo, we'll try to keep things simple.
We'll make an undirected graph assuming that when an airplane has a route, it can fly back and forth between the two a it'll be unweighted, so the routes between the two airports won't carry any additional data, and we'll assume cycles are not possible.
The first thing we'll need to do is represent our graph and code.
Most programming interviews will have you write code in whatever language you prefer.
We'll be using JavaScript here, but the most important tip I can give you is to a simply explain your thinking process as you're writing your code.
Most technical interviewers are trying to get some insight into your thinking process and care less if you write perfectly formatted code.
Let's go ahead and walk through a few examples.
You might get a question like this.
Here's a list of airports and a list of routes connecting these airports.
Now represent this data as a graph.
So given this data, we can represent the graph in 2 ways, a matrix or an adjacency list.
A matrix takes up more space, but it's generally easier to visualize and represent because it's just a 2 dimensional array filled with ones and zeros.
Now looking at this data, I can see there are not very many routes relative to the number of possible combinations between these airports.
That means our matrix would be very sparse or, in other words, filled with a bunch of zeros and take up a lot of unnecessary space, and it would be less efficient to iterate over and search through.
Therefore, I choose to represent my graph as an adjacency list.
We can implement an adjacency list as a set of key value pairs a where the key is the name of the airport or the node and the value is an array of edges or the other airports that it's connected to.
We could implement this with a regular JavaScript object, but a better option might be a map.
When you're doing algorithm problems in JavaScript, a map tends to be a better option than a regular object.
It has some additional API methods that can be useful for problems a like this.
And it just behaves more like a regular dictionary or hash map that you'll find in other languages.
So the map is our graph, and at this point, it's empty.
The first thing we'll do is define a function that can add a node to the map.
This function takes the airport code as its argument and then calls adjacency list set on the airport and starts it off with an empty array.
And that's all it takes to represent a node on the graph.
To add an edge, we need to update the entries for both the origin airport and the destination.
First, we'll grab the entry for the origin airport and then push the destination onto its list.
And then we'll do the inverse of that by getting the destination and then pushing the origin onto its list.
And that's our entire API for building a graph as an adjacency list.
The next step is to use this API with our source data.
We can loop over the airports with 4 each and for each one call the add node method to add a node to the graph.
Once we have our nodes, we can then loop over the routes a and add an edge for each route in that array.
That function takes 2 arguments, so I'm going to use the rest syntax here to destructure them.
Now you can go ahead and console log this graph by running it in Node.
Js, and you should get an output that looks similar to this.
Congratulations.
You just got through the first part of the interview, a but that was the easy part.
Now the interviewer wants you to implement an algorithm to figure out if there's a route between Phoenix and Bangkok.
A and as you know from earlier in the video, there are 2 main ways we can approach this, depth first search or breadth first search.
I think the easier one to understand is BFS.
You know, in order to search a graph, you have to start somewhere.
In this case, we'll start with the Phoenix node.
So we need a function that takes a starting node as its argument.
A write that out on the whiteboard or as pseudo code in whatever editing tool you're using for the interview.
From the starting node, you want to visit all the children and see if any of them are Bangkok.
If not, you'll want to visit their children and do the same thing.
And you'll continue doing this in layers until you find the airport you're looking for.
We can represent this process as a queue, which in JavaScript is just an array where the first item in is the first item out.
And, of course, the first item in your queue should be the starting node.
A now while the queue has items in it or the length is greater than 0, we'll grab the first item in the array using the array shift method.
This method will mutate the original array by removing the first item in it and then return that item to us here that we set as the airport variable.
A our next step is to grab all the edges for this node in the graph.
We can do that by calling adjacency list get with that airport name as the key.
That'll give us all the destinations for the airport or its children so we can loop over them and add them to the queue as well.
We can also go ahead and log out if any of these airports are Bangkok, the airport we're looking for.
Now one major problem with this code at the moment is that airports have many interconnected routes, and that means our algorithm will be visiting the same nodes over and over again.
A and in our case, this creates an infinite loop because the queue is never emptied.
We can avoid that by keeping track of the airports that we visited in the past.
An easy way to do that in JavaScript is with a set, which is basically an array, but all the values in it are unique.
We set it up as an empty set when the function is first called, then we can use it to set up some conditional logic in our loop.
We will only enqueue an item if it does not have this destination.
A set has a has method a where you can pass a value to see if it exists currently in the set.
And then we'll mark the destination as visited by adding it to the set.
Then we'll move the line of code that adds this item to the queue inside of our condition here.
So an item only gets enqueued if it has not been visited already.
Now let's go ahead and call our function using Phoenix as the starting node.
What you'll notice is that it goes through 9 airports before it finally finds Bangkok.
It starts with all the connections to Phoenix, then all the connections to JFK, then from Mexico City, it finds a route to Bangkok.
And then it also finds a second route through Lima, Peru.
So breadth first search would be really good for finding all the possible routes to determine which one is the most efficient.
At this point, your interviewer is super impressed.
A but then here she says our only concern is if a route from Phoenix to Bangkok exists.
We don't care if there are multiple routes.
We don't care if it's the best route.
We just want to find a route as quickly as possible.
How can you traverse this graph more efficiently to meet that need?
An approach that would be more efficient for this particular requirement is a depth first search.
A instead of going through all the children or destinations for each airport, we'll go to its first child and then to its first child and its first child and so on until we hit Bangkok.
And if we don't find it, we'll backtrack to the top of the graph and follow the same pattern.
In the last example, we used a queue.
But in this example, we're going to use a recursive function, or in other words, a function that calls itself until it reaches some kind of stopping point.
This function will take a starting node as its first argument and then a set as a second argument that keeps track of the different cities that we visited because, again, we don't want to visit the same node more than once.
From there, we'll grab the edges or destinations from our adjacency list.
We'll loop over them just like we did before.
And when we find what we're looking for, we'll just return from the function.
Now here's the interesting part.
If a node has not been visited, then we'll go ahead and call the same function, or in other words, call it recursively with the current destination in the loop as well as our visited set.
That means this function call will be pushed to the top of the call stack, making the algorithm go deeper and deeper into the tree until it reaches a stopping point.
And that means this function will continue calling itself recursively until all the airports have been visited or until it finds Bangkok.
In this example, it only takes 3 steps or 3 function calls to find the route as opposed to 8 in our previous algorithm.
But the interviewer has one last question.
What is the time complexity of the algorithm that you just implemented as expressed in big o notation?
A for both breadth first and depth first search, big o is expressed as v plus e, which is the total number of nodes or vertices plus the number of edges.
Or, in other words, the time performance of the algorithm will scale linear based on the number of nodes and edges that are added to the graph.
I'm gonna go ahead and wrap things up there, but there are many other algorithms you can use to traverse a graph.
So if you wanna see more videos like this, let me know in the comments.
Thanks for watching and I will see you in the next a.

Speaker 0: A graph is a nonlinear data structure that contains nodes and edges. A node or vertex is just a single unique value, while an edge represents a connection or relationship between 2 of these nodes. Think of something like Instagram. Every user is a node. Every time you follow a user, you create a new edge connecting 2 nodes together.

This is known as a directed graph because the relationship flows one way. The follower follows the followee and not vice versa. Now consider Facebook. Your edges on the graph are friendships. This relationship goes both ways, which is known as an undirected graph.

Graphs can to be weighted, which means the node has some additional data about the relationship, like the distance between 2 airports. A node might also point to itself, like an airplane that takes off and comes back to land at the same airport. This is known as a cycle. Graphs are used in many real life software products, and you'll often be asked to represent a graphic code in in a technical interview. One way to represent a graph is with a 2 d array or adjacency matrix.

Create 1 row and 1 column for every node. When 2 nodes have an edge or connection at a one at the point they intersect. This makes it fast and easy to look up a specific edge or to add a new edge. But as a 2 d array, it takes quadratic space complexity and quadratic time to insert a new node into the graph. An alternative approach is an adjacency list.

In this representation, we start with a collection of nodes, then each item has its own array of its neighbors. This makes it faster to iterate over a node's edges and is more efficient with memory, especially when you have many nodes and few edges. In your interview, you'll likely need to traverse your graph. One option is a depth first search. Start with any random node, go to its first child, then its first child, and do that for as long as you can.

When there are no more children, backtrack to the last node and continue the process. A this algorithm is usually implemented with a recursive function. Another option is a breadth first search. From your starting node, add all of the direct children to a queue. Once they've been visited, a move on to the grandchildren and continue following this pattern in layers.

This has been graphs in 100 seconds, but hang out for a few minutes because now we're going to implement these algorithms in JavaScript. If you're new here, like and subscribe, hit the like button, open your IDE, and get ready to go beyond 100 seconds. A as a developer, you'll come across all kinds of different real life implementations of graphs. I mentioned Facebook's social graph at the beginning of the video, and they're commonly used for recommendation engines, like Yelp, for example, to connect businesses to users to reviews, or Netflix to connect the movies that you watch 2 movies that you might want to watch in the future. They're also used to represent geographic data.

For example, on Google Maps, you can think of every intersection as a node a and then every road and its distance as the edge connecting these two nodes. Over the next few minutes, we'll implement a basic graph in JavaScript based on the flight connections between airports. A in this case, every airport is a node, and the edge represents whether or not you can fly from one airport to another. This edge could contain additional information like the kilometers between the two a words, in which case that would give us a weighted graph. The routes between 2 airports could be one way or two way.

When they go one way, we have a directed graph. A if they go both ways, it's an undirected graph. For this demo, we'll try to keep things simple. We'll make an undirected graph assuming that when an airplane has a route, it can fly back and forth between the two a it'll be unweighted, so the routes between the two airports won't carry any additional data, and we'll assume cycles are not possible. The first thing we'll need to do is represent our graph and code.

Most programming interviews will have you write code in whatever language you prefer. We'll be using JavaScript here, but the most important tip I can give you is to a simply explain your thinking process as you're writing your code. Most technical interviewers are trying to get some insight into your thinking process and care less if you write perfectly formatted code. Let's go ahead and walk through a few examples. You might get a question like this.

Here's a list of airports and a list of routes connecting these airports. Now represent this data as a graph. So given this data, we can represent the graph in 2 ways, a matrix or an adjacency list. A matrix takes up more space, but it's generally easier to visualize and represent because it's just a 2 dimensional array filled with ones and zeros. Now looking at this data, I can see there are not very many routes relative to the number of possible combinations between these airports.

That means our matrix would be very sparse or, in other words, filled with a bunch of zeros and take up a lot of unnecessary space, and it would be less efficient to iterate over and search through. Therefore, I choose to represent my graph as an adjacency list. We can implement an adjacency list as a set of key value pairs a where the key is the name of the airport or the node and the value is an array of edges or the other airports that it's connected to. We could implement this with a regular JavaScript object, but a better option might be a map. When you're doing algorithm problems in JavaScript, a map tends to be a better option than a regular object.

It has some additional API methods that can be useful for problems a like this. And it just behaves more like a regular dictionary or hash map that you'll find in other languages. So the map is our graph, and at this point, it's empty. The first thing we'll do is define a function that can add a node to the map. This function takes the airport code as its argument and then calls adjacency list set on the airport and starts it off with an empty array.

And that's all it takes to represent a node on the graph. To add an edge, we need to update the entries for both the origin airport and the destination. First, we'll grab the entry for the origin airport and then push the destination onto its list. And then we'll do the inverse of that by getting the destination and then pushing the origin onto its list. And that's our entire API for building a graph as an adjacency list.

The next step is to use this API with our source data. We can loop over the airports with 4 each and for each one call the add node method to add a node to the graph. Once we have our nodes, we can then loop over the routes a and add an edge for each route in that array. That function takes 2 arguments, so I'm going to use the rest syntax here to destructure them. Now you can go ahead and console log this graph by running it in Node.

Js, and you should get an output that looks similar to this. Congratulations. You just got through the first part of the interview, a but that was the easy part. Now the interviewer wants you to implement an algorithm to figure out if there's a route between Phoenix and Bangkok. A and as you know from earlier in the video, there are 2 main ways we can approach this, depth first search or breadth first search.

I think the easier one to understand is BFS. You know, in order to search a graph, you have to start somewhere. In this case, we'll start with the Phoenix node. So we need a function that takes a starting node as its argument. A write that out on the whiteboard or as pseudo code in whatever editing tool you're using for the interview.

From the starting node, you want to visit all the children and see if any of them are Bangkok. If not, you'll want to visit their children and do the same thing. And you'll continue doing this in layers until you find the airport you're looking for. We can represent this process as a queue, which in JavaScript is just an array where the first item in is the first item out. And, of course, the first item in your queue should be the starting node.

A now while the queue has items in it or the length is greater than 0, we'll grab the first item in the array using the array shift method. This method will mutate the original array by removing the first item in it and then return that item to us here that we set as the airport variable. A our next step is to grab all the edges for this node in the graph. We can do that by calling adjacency list get with that airport name as the key. That'll give us all the destinations for the airport or its children so we can loop over them and add them to the queue as well.

We can also go ahead and log out if any of these airports are Bangkok, the airport we're looking for. Now one major problem with this code at the moment is that airports have many interconnected routes, and that means our algorithm will be visiting the same nodes over and over again. A and in our case, this creates an infinite loop because the queue is never emptied. We can avoid that by keeping track of the airports that we visited in the past. An easy way to do that in JavaScript is with a set, which is basically an array, but all the values in it are unique.

We set it up as an empty set when the function is first called, then we can use it to set up some conditional logic in our loop. We will only enqueue an item if it does not have this destination. A set has a has method a where you can pass a value to see if it exists currently in the set. And then we'll mark the destination as visited by adding it to the set. Then we'll move the line of code that adds this item to the queue inside of our condition here.

So an item only gets enqueued if it has not been visited already. Now let's go ahead and call our function using Phoenix as the starting node. What you'll notice is that it goes through 9 airports before it finally finds Bangkok. It starts with all the connections to Phoenix, then all the connections to JFK, then from Mexico City, it finds a route to Bangkok. And then it also finds a second route through Lima, Peru.

So breadth first search would be really good for finding all the possible routes to determine which one is the most efficient. At this point, your interviewer is super impressed. A but then here she says our only concern is if a route from Phoenix to Bangkok exists. We don't care if there are multiple routes. We don't care if it's the best route.

We just want to find a route as quickly as possible. How can you traverse this graph more efficiently to meet that need? An approach that would be more efficient for this particular requirement is a depth first search. A instead of going through all the children or destinations for each airport, we'll go to its first child and then to its first child and its first child and so on until we hit Bangkok. And if we don't find it, we'll backtrack to the top of the graph and follow the same pattern.

In the last example, we used a queue. But in this example, we're going to use a recursive function, or in other words, a function that calls itself until it reaches some kind of stopping point. This function will take a starting node as its first argument and then a set as a second argument that keeps track of the different cities that we visited because, again, we don't want to visit the same node more than once. From there, we'll grab the edges or destinations from our adjacency list. We'll loop over them just like we did before.

And when we find what we're looking for, we'll just return from the function. Now here's the interesting part. If a node has not been visited, then we'll go ahead and call the same function, or in other words, call it recursively with the current destination in the loop as well as our visited set. That means this function call will be pushed to the top of the call stack, making the algorithm go deeper and deeper into the tree until it reaches a stopping point. And that means this function will continue calling itself recursively until all the airports have been visited or until it finds Bangkok.

In this example, it only takes 3 steps or 3 function calls to find the route as opposed to 8 in our previous algorithm. But the interviewer has one last question. What is the time complexity of the algorithm that you just implemented as expressed in big o notation? A for both breadth first and depth first search, big o is expressed as v plus e, which is the total number of nodes or vertices plus the number of edges. Or, in other words, the time performance of the algorithm will scale linear based on the number of nodes and edges that are added to the graph.

I'm gonna go ahead and wrap things up there, but there are many other algorithms you can use to traverse a graph. So if you wanna see more videos like this, let me know in the comments. Thanks for watching and I will see you in the next a.
A graph is a nonlinear data structure that contains nodes and edges. A node or vertex is just a single unique value, while an edge represents a connection or relationship between 2 of these nodes.
Think of something like Instagram. Every user is a node. Every time you follow a user, you create a new edge connecting 2 nodes together. This is known as a directed graph because the relationship flows one way. The follower follows the followee and not vice versa. Now consider Facebook. Your edges on the graph are friendships. This relationship goes both ways, which is known as an undirected graph. Graphs can to be weighted, which means the node has some additional data about the relationship, like the distance between 2 airports. A node might also point to itself, like an airplane that takes off and comes back to land at the same airport.
instagram
social media
geometry
twitter
relationships
This is known as a cycle.
Graphs are used in many real life software products, and you'll often be asked to represent a graphic code in in a technical interview. One way to represent a graph is with a 2 d array or adjacency matrix. Create 1 row and 1 column for every node. When 2 nodes have an edge or connection at a one at the point they intersect.
geometry
This makes it fast and easy to look up a specific edge or to add a new edge. But as a 2 d array, it takes quadratic space complexity and quadratic time to insert a new node into the graph. An alternative approach is an adjacency list. In this representation, we start with a collection of nodes, then each item has its own array of its neighbors. This makes it faster to iterate over a node's edges and is more efficient with memory, especially when you have many nodes and few edges. In your interview, you'll likely need to traverse your graph. One option is a depth first search. Start with any random node, go to its first child, then its first child, and do that for as long as you can.
programming
geometry
visualization
machine learning
When there are no more children, backtrack to the last node and continue the process. A this algorithm is usually implemented with a recursive function. Another option is a breadth first search. From your starting node, add all of the direct children to a queue. Once they've been visited, a move on to the grandchildren and continue following this pattern in layers. This has been graphs in 100 seconds, but hang out for a few minutes because now we're going to implement these algorithms in JavaScript. If you're new here, like and subscribe, hit the like button, open your IDE, and get ready to go beyond 100 seconds.
A as a developer, you'll come across all kinds of different real life implementations of graphs. I mentioned Facebook's social graph at the beginning of the video, and they're commonly used for recommendation engines, like Yelp, for example, to connect businesses to users to reviews, or Netflix to connect the movies that you watch 2 movies that you might want to watch in the future. They're also used to represent geographic data. For example, on Google Maps, you can think of every intersection as a node a and then every road and its distance as the edge connecting these two nodes. Over the next few minutes, we'll implement a basic graph in JavaScript based on the flight connections between airports.
geography
roads
youtube
websites
streaming
geometry
visualization
graphic design
A in this case, every airport is a node, and the edge represents whether or not you can fly from one airport to another.
This edge could contain additional information like the kilometers between the two a words, in which case that would give us a weighted graph. The routes between 2 airports could be one way or two way. When they go one way, we have a directed graph. A if they go both ways, it's an undirected graph.
geometry
For this demo, we'll try to keep things simple.
We'll make an undirected graph assuming that when an airplane has a route, it can fly back and forth between the two a it'll be unweighted, so the routes between the two airports won't carry any additional data, and we'll assume cycles are not possible. The first thing we'll need to do is represent our graph and code. Most programming interviews will have you write code in whatever language you prefer. We'll be using JavaScript here, but the most important tip I can give you is to a simply explain your thinking process as you're writing your code. Most technical interviewers are trying to get some insight into your thinking process and care less if you write perfectly formatted code. Let's go ahead and walk through a few examples.
programming
air travel
transportation
You might get a question like this. Here's a list of airports and a list of routes connecting these airports. Now represent this data as a graph. So given this data, we can represent the graph in 2 ways, a matrix or an adjacency list. A matrix takes up more space, but it's generally easier to visualize and represent because it's just a 2 dimensional array filled with ones and zeros. Now looking at this data, I can see there are not very many routes relative to the number of possible combinations between these airports.
geometry
data
That means our matrix would be very sparse or, in other words, filled with a bunch of zeros and take up a lot of unnecessary space, and it would be less efficient to iterate over and search through. Therefore, I choose to represent my graph as an adjacency list. We can implement an adjacency list as a set of key value pairs a where the key is the name of the airport or the node and the value is an array of edges or the other airports that it's connected to. We could implement this with a regular JavaScript object, but a better option might be a map. When you're doing algorithm problems in JavaScript, a map tends to be a better option than a regular object. It has some additional API methods that can be useful for problems a like this. And it just behaves more like a regular dictionary or hash map that you'll find in other languages. So the map is our graph, and at this point, it's empty. The first thing we'll do is define a function that can add a node to the map. This function takes the airport code as its argument and then calls adjacency list set on the airport and starts it off with an empty array. And that's all it takes to represent a node on the graph. To add an edge, we need to update the entries for both the origin airport and the destination.
First, we'll grab the entry for the origin airport and then push the destination onto its list. And then we'll do the inverse of that by getting the destination and then pushing the origin onto its list. And that's our entire API for building a graph as an adjacency list. The next step is to use this API with our source data. We can loop over the airports with 4 each and for each one call the add node method to add a node to the graph.
databases
transportation
Once we have our nodes, we can then loop over the routes a and add an edge for each route in that array. That function takes 2 arguments, so I'm going to use the rest syntax here to destructure them. Now you can go ahead and console log this graph by running it in Node. Js, and you should get an output that looks similar to this. Congratulations. You just got through the first part of the interview, a but that was the easy part. Now the interviewer wants you to implement an algorithm to figure out if there's a route between Phoenix and Bangkok. A and as you know from earlier in the video, there are 2 main ways we can approach this, depth first search or breadth first search.
I think the easier one to understand is BFS. You know, in order to search a graph, you have to start somewhere. In this case, we'll start with the Phoenix node. So we need a function that takes a starting node as its argument. A write that out on the whiteboard or as pseudo code in whatever editing tool you're using for the interview.
programming
From the starting node, you want to visit all the children and see if any of them are Bangkok. If not, you'll want to visit their children and do the same thing. And you'll continue doing this in layers until you find the airport you're looking for. We can represent this process as a queue, which in JavaScript is just an array where the first item in is the first item out. And, of course, the first item in your queue should be the starting node. A now while the queue has items in it or the length is greater than 0, we'll grab the first item in the array using the array shift method. This method will mutate the original array by removing the first item in it and then return that item to us here that we set as the airport variable. A our next step is to grab all the edges for this node in the graph. We can do that by calling adjacency list get with that airport name as the key.
That'll give us all the destinations for the airport or its children so we can loop over them and add them to the queue as well. We can also go ahead and log out if any of these airports are Bangkok, the airport we're looking for. Now one major problem with this code at the moment is that airports have many interconnected routes, and that means our algorithm will be visiting the same nodes over and over again.
transportation
air travel
networking
A and in our case, this creates an infinite loop because the queue is never emptied. We can avoid that by keeping track of the airports that we visited in the past. An easy way to do that in JavaScript is with a set, which is basically an array, but all the values in it are unique.
We set it up as an empty set when the function is first called, then we can use it to set up some conditional logic in our loop. We will only enqueue an item if it does not have this destination. A set has a has method a where you can pass a value to see if it exists currently in the set.
logic
And then we'll mark the destination as visited by adding it to the set. Then we'll move the line of code that adds this item to the queue inside of our condition here. So an item only gets enqueued if it has not been visited already. Now let's go ahead and call our function using Phoenix as the starting node. What you'll notice is that it goes through 9 airports before it finally finds Bangkok. It starts with all the connections to Phoenix, then all the connections to JFK, then from Mexico City, it finds a route to Bangkok. And then it also finds a second route through Lima, Peru. So breadth first search would be really good for finding all the possible routes to determine which one is the most efficient. At this point, your interviewer is super impressed. A but then here she says our only concern is if a route from Phoenix to Bangkok exists. We don't care if there are multiple routes. We don't care if it's the best route. We just want to find a route as quickly as possible. How can you traverse this graph more efficiently to meet that need? An approach that would be more efficient for this particular requirement is a depth first search. A instead of going through all the children or destinations for each airport, we'll go to its first child and then to its first child and its first child and so on until we hit Bangkok.
And if we don't find it, we'll backtrack to the top of the graph and follow the same pattern. In the last example, we used a queue. But in this example, we're going to use a recursive function, or in other words, a function that calls itself until it reaches some kind of stopping point.
operations
This function will take a starting node as its first argument and then a set as a second argument that keeps track of the different cities that we visited because, again, we don't want to visit the same node more than once. From there, we'll grab the edges or destinations from our adjacency list. We'll loop over them just like we did before. And when we find what we're looking for, we'll just return from the function. Now here's the interesting part. If a node has not been visited, then we'll go ahead and call the same function, or in other words, call it recursively with the current destination in the loop as well as our visited set.
That means this function call will be pushed to the top of the call stack, making the algorithm go deeper and deeper into the tree until it reaches a stopping point. And that means this function will continue calling itself recursively until all the airports have been visited or until it finds Bangkok.
operations
In this example, it only takes 3 steps or 3 function calls to find the route as opposed to 8 in our previous algorithm. But the interviewer has one last question. What is the time complexity of the algorithm that you just implemented as expressed in big o notation?
A for both breadth first and depth first search, big o is expressed as v plus e, which is the total number of nodes or vertices plus the number of edges. Or, in other words, the time performance of the algorithm will scale linear based on the number of nodes and edges that are added to the graph.
neural networks
I'm gonna go ahead and wrap things up there, but there are many other algorithms you can use to traverse a graph. So if you wanna see more videos like this, let me know in the comments. Thanks for watching and I will see you in the next a.
visualization
animation
A graph is a nonlinear data structure that contains nodes and edges. A node or vertex is just a single unique value, while an edge represents a connection or relationship between 2 of these nodes. Think of something like Instagram. Every user is a node. Every time you follow a user, you create a new edge connecting 2 nodes together. This is known as a directed graph because the relationship flows one way. The follower follows the followee and not vice versa. Now consider Facebook. Your edges on the graph are friendships. This relationship goes both ways, which is known as an undirected graph. Graphs can to be weighted, which means the node has some additional data about the relationship, like the distance between 2 airports. A node might also point to itself, like an airplane that takes off and comes back to land at the same airport. This is known as a cycle. Graphs are used in many real life software products, and you'll often be asked to represent a graphic code in in a technical interview. One way to represent a graph is with a 2 d array or adjacency matrix. Create 1 row and 1 column for every node. When 2 nodes have an edge or connection at a one at the point they intersect. This makes it fast and easy to look up a specific edge or to add a new edge. But as a 2 d array, it takes quadratic space complexity and quadratic time to insert a new node into the graph. An alternative approach is an adjacency list. In this representation, we start with a collection of nodes, then each item has its own array of its neighbors. This makes it faster to iterate over a node's edges and is more efficient with memory, especially when you have many nodes and few edges. In your interview, you'll likely need to traverse your graph. One option is a depth first search. Start with any random node, go to its first child, then its first child, and do that for as long as you can. When there are no more children, backtrack to the last node and continue the process. A this algorithm is usually implemented with a recursive function. Another option is a breadth first search. From your starting node, add all of the direct children to a queue. Once they've been visited, a move on to the grandchildren and continue following this pattern in layers. This has been graphs in 100 seconds, but hang out for a few minutes because now we're going to implement these algorithms in JavaScript. If you're new here, like and subscribe, hit the like button, open your IDE, and get ready to go beyond 100 seconds. A as a developer, you'll come across all kinds of different real life implementations of graphs. I mentioned Facebook's social graph at the beginning of the video, and they're commonly used for recommendation engines, like Yelp, for example, to connect businesses to users to reviews, or Netflix to connect the movies that you watch 2 movies that you might want to watch in the future. They're also used to represent geographic data. For example, on Google Maps, you can think of every intersection as a node a and then every road and its distance as the edge connecting these two nodes. Over the next few minutes, we'll implement a basic graph in JavaScript based on the flight connections between airports. A in this case, every airport is a node, and the edge represents whether or not you can fly from one airport to another. This edge could contain additional information like the kilometers between the two a words, in which case that would give us a weighted graph. The routes between 2 airports could be one way or two way. When they go one way, we have a directed graph. A if they go both ways, it's an undirected graph. For this demo, we'll try to keep things simple. We'll make an undirected graph assuming that when an airplane has a route, it can fly back and forth between the two a it'll be unweighted, so the routes between the two airports won't carry any additional data, and we'll assume cycles are not possible. The first thing we'll need to do is represent our graph and code. Most programming interviews will have you write code in whatever language you prefer. We'll be using JavaScript here, but the most important tip I can give you is to a simply explain your thinking process as you're writing your code. Most technical interviewers are trying to get some insight into your thinking process and care less if you write perfectly formatted code. Let's go ahead and walk through a few examples. You might get a question like this. Here's a list of airports and a list of routes connecting these airports. Now represent this data as a graph. So given this data, we can represent the graph in 2 ways, a matrix or an adjacency list. A matrix takes up more space, but it's generally easier to visualize and represent because it's just a 2 dimensional array filled with ones and zeros. Now looking at this data, I can see there are not very many routes relative to the number of possible combinations between these airports. That means our matrix would be very sparse or, in other words, filled with a bunch of zeros and take up a lot of unnecessary space, and it would be less efficient to iterate over and search through. Therefore, I choose to represent my graph as an adjacency list. We can implement an adjacency list as a set of key value pairs a where the key is the name of the airport or the node and the value is an array of edges or the other airports that it's connected to. We could implement this with a regular JavaScript object, but a better option might be a map. When you're doing algorithm problems in JavaScript, a map tends to be a better option than a regular object. It has some additional API methods that can be useful for problems a like this. And it just behaves more like a regular dictionary or hash map that you'll find in other languages. So the map is our graph, and at this point, it's empty. The first thing we'll do is define a function that can add a node to the map. This function takes the airport code as its argument and then calls adjacency list set on the airport and starts it off with an empty array. And that's all it takes to represent a node on the graph. To add an edge, we need to update the entries for both the origin airport and the destination. First, we'll grab the entry for the origin airport and then push the destination onto its list. And then we'll do the inverse of that by getting the destination and then pushing the origin onto its list. And that's our entire API for building a graph as an adjacency list. The next step is to use this API with our source data. We can loop over the airports with 4 each and for each one call the add node method to add a node to the graph. Once we have our nodes, we can then loop over the routes a and add an edge for each route in that array. That function takes 2 arguments, so I'm going to use the rest syntax here to destructure them. Now you can go ahead and console log this graph by running it in Node. Js, and you should get an output that looks similar to this. Congratulations. You just got through the first part of the interview, a but that was the easy part. Now the interviewer wants you to implement an algorithm to figure out if there's a route between Phoenix and Bangkok. A and as you know from earlier in the video, there are 2 main ways we can approach this, depth first search or breadth first search. I think the easier one to understand is BFS. You know, in order to search a graph, you have to start somewhere. In this case, we'll start with the Phoenix node. So we need a function that takes a starting node as its argument. A write that out on the whiteboard or as pseudo code in whatever editing tool you're using for the interview. From the starting node, you want to visit all the children and see if any of them are Bangkok. If not, you'll want to visit their children and do the same thing. And you'll continue doing this in layers until you find the airport you're looking for. We can represent this process as a queue, which in JavaScript is just an array where the first item in is the first item out. And, of course, the first item in your queue should be the starting node. A now while the queue has items in it or the length is greater than 0, we'll grab the first item in the array using the array shift method. This method will mutate the original array by removing the first item in it and then return that item to us here that we set as the airport variable. A our next step is to grab all the edges for this node in the graph. We can do that by calling adjacency list get with that airport name as the key. That'll give us all the destinations for the airport or its children so we can loop over them and add them to the queue as well. We can also go ahead and log out if any of these airports are Bangkok, the airport we're looking for. Now one major problem with this code at the moment is that airports have many interconnected routes, and that means our algorithm will be visiting the same nodes over and over again. A and in our case, this creates an infinite loop because the queue is never emptied. We can avoid that by keeping track of the airports that we visited in the past. An easy way to do that in JavaScript is with a set, which is basically an array, but all the values in it are unique. We set it up as an empty set when the function is first called, then we can use it to set up some conditional logic in our loop. We will only enqueue an item if it does not have this destination. A set has a has method a where you can pass a value to see if it exists currently in the set. And then we'll mark the destination as visited by adding it to the set. Then we'll move the line of code that adds this item to the queue inside of our condition here. So an item only gets enqueued if it has not been visited already. Now let's go ahead and call our function using Phoenix as the starting node. What you'll notice is that it goes through 9 airports before it finally finds Bangkok. It starts with all the connections to Phoenix, then all the connections to JFK, then from Mexico City, it finds a route to Bangkok. And then it also finds a second route through Lima, Peru. So breadth first search would be really good for finding all the possible routes to determine which one is the most efficient. At this point, your interviewer is super impressed. A but then here she says our only concern is if a route from Phoenix to Bangkok exists. We don't care if there are multiple routes. We don't care if it's the best route. We just want to find a route as quickly as possible. How can you traverse this graph more efficiently to meet that need? An approach that would be more efficient for this particular requirement is a depth first search. A instead of going through all the children or destinations for each airport, we'll go to its first child and then to its first child and its first child and so on until we hit Bangkok. And if we don't find it, we'll backtrack to the top of the graph and follow the same pattern. In the last example, we used a queue. But in this example, we're going to use a recursive function, or in other words, a function that calls itself until it reaches some kind of stopping point. This function will take a starting node as its first argument and then a set as a second argument that keeps track of the different cities that we visited because, again, we don't want to visit the same node more than once. From there, we'll grab the edges or destinations from our adjacency list. We'll loop over them just like we did before. And when we find what we're looking for, we'll just return from the function. Now here's the interesting part. If a node has not been visited, then we'll go ahead and call the same function, or in other words, call it recursively with the current destination in the loop as well as our visited set. That means this function call will be pushed to the top of the call stack, making the algorithm go deeper and deeper into the tree until it reaches a stopping point. And that means this function will continue calling itself recursively until all the airports have been visited or until it finds Bangkok. In this example, it only takes 3 steps or 3 function calls to find the route as opposed to 8 in our previous algorithm. But the interviewer has one last question. What is the time complexity of the algorithm that you just implemented as expressed in big o notation? A for both breadth first and depth first search, big o is expressed as v plus e, which is the total number of nodes or vertices plus the number of edges. Or, in other words, the time performance of the algorithm will scale linear based on the number of nodes and edges that are added to the graph. I'm gonna go ahead and wrap things up there, but there are many other algorithms you can use to traverse a graph. So if you wanna see more videos like this, let me know in the comments. Thanks for watching and I will see you in the next a.
A
a
graph
graph
is
is
a
a
nonlinear
nonlinear
data
data
structure
structure
that
that
contains
contains
nodes
nodes
and
and
edges.
edges
A
a
node
node
or
or
vertex
vertex
is
is
just
just
a
a
single
single
unique
unique
value,
value
while
while
an
an
edge
edge
represents
represents
a
a
connection
connection
or
or
relationship
relationship
between
between
2
2
of
of
these
these
nodes.
nodes
Think
think
of
of
something
something
like
like
Instagram.
instagram
Every
every
user
user
is
is
a
a
node.
node
Every
every
time
time
you
you
follow
follow
a
a
user,
user
you
you
create
create
a
a
new
new
edge
edge
connecting
connecting
2
2
nodes
nodes
together.
together
This
this
is
is
known
known
as
as
a
a
directed
directed
graph
graph
because
because
the
the
relationship
relationship
flows
flows
one
one
way.
way
The
the
follower
follower
follows
follows
the
the
followee
followee
and
and
not
not
vice
vice
versa.
versa
Now
now
consider
consider
Facebook.
facebook
Your
your
edges
edges
on
on
the
the
graph
graph
are
are
friendships.
friendships
This
this
relationship
relationship
goes
goes
both
both
ways,
ways
which
which
is
is
known
known
as
as
an
an
undirected
undirected
graph.
graph
Graphs
graphs
can
can
to
to
be
be
weighted,
weighted
which
which
means
means
the
the
node
node
has
has
some
some
additional
additional
data
data
about
about
the
the
relationship,
relationship
like
like
the
the
distance
distance
between
between
2
2
airports.
airports
A
a
node
node
might
might
also
also
point
point
to
to
itself,
itself
like
like
an
an
airplane
airplane
that
that
takes
takes
off
off
and
and
comes
comes
back
back
to
to
land
land
at
at
the
the
same
same
airport.
airport
This
this
is
is
known
known
as
as
a
a
cycle.
cycle
Graphs
graphs
are
are
used
used
in
in
many
many
real
real
life
life
software
software
products,
products
and
and
you'll
you'll
often
often
be
be
asked
asked
to
to
represent
represent
a
a
graphic
graphic
code
code
in
in
in
in
a
a
technical
technical
interview.
interview
One
one
way
way
to
to
represent
represent
a
a
graph
graph
is
is
with
with
a
a
2
2
d
d
array
array
or
or
adjacency
adjacency
matrix.
matrix
Create
create
1
1
row
row
and
and
1
1
column
column
for
for
every
every
node.
node
When
when
2
2
nodes
nodes
have
have
an
an
edge
edge
or
or
connection
connection
at
at
a
a
one
one
at
at
the
the
point
point
they
they
intersect.
intersect
This
this
makes
makes
it
it
fast
fast
and
and
easy
easy
to
to
look
look
up
up
a
a
specific
specific
edge
edge
or
or
to
to
add
add
a
a
new
new
edge.
edge
But
but
as
as
a
a
2
2
d
d
array,
array
it
it
takes
takes
quadratic
quadratic
space
space
complexity
complexity
and
and
quadratic
quadratic
time
time
to
to
insert
insert
a
a
new
new
node
node
into
into
the
the
graph.
graph
An
an
alternative
alternative
approach
approach
is
is
an
an
adjacency
adjacency
list.
list
In
in
this
this
representation,
representation
we
we
start
start
with
with
a
a
collection
collection
of
of
nodes,
nodes
then
then
each
each
item
item
has
has
its
its
own
own
array
array
of
of
its
its
neighbors.
neighbors
This
this
makes
makes
it
it
faster
faster
to
to
iterate
iterate
over
over
a
a
node's
node's
edges
edges
and
and
is
is
more
more
efficient
efficient
with
with
memory,
memory
especially
especially
when
when
you
you
have
have
many
many
nodes
nodes
and
and
few
few
edges.
edges
In
in
your
your
interview,
interview
you'll
you'll
likely
likely
need
need
to
to
traverse
traverse
your
your
graph.
graph
One
one
option
option
is
is
a
a
depth
depth
first
first
search.
search
Start
start
with
with
any
any
random
random
node,
node
go
go
to
to
its
its
first
first
child,
child
then
then
its
its
first
first
child,
child
and
and
do
do
that
that
for
for
as
as
long
long
as
as
you
you
can.
can
When
when
there
there
are
are
no
no
more
more
children,
children
backtrack
backtrack
to
to
the
the
last
last
node
node
and
and
continue
continue
the
the
process.
process
A
a
this
this
algorithm
algorithm
is
is
usually
usually
implemented
implemented
with
with
a
a
recursive
recursive
function.
function
Another
another
option
option
is
is
a
a
breadth
breadth
first
first
search.
search
From
from
your
your
starting
starting
node,
node
add
add
all
all
of
of
the
the
direct
direct
children
children
to
to
a
a
queue.
queue
Once
once
they've
they've
been
been
visited,
visited
a
a
move
move
on
on
to
to
the
the
grandchildren
grandchildren
and
and
continue
continue
following
following
this
this
pattern
pattern
in
in
layers.
layers
This
this
has
has
been
been
graphs
graphs
in
in
100
100
seconds,
seconds
but
but
hang
hang
out
out
for
for
a
a
few
few
minutes
minutes
because
because
now
now
we're
we're
going
going
to
to
implement
implement
these
these
algorithms
algorithms
in
in
JavaScript.
javascript
If
if
you're
you're
new
new
here,
here
like
like
and
and
subscribe,
subscribe
hit
hit
the
the
like
like
button,
button
open
open
your
your
IDE,
ide
and
and
get
get
ready
ready
to
to
go
go
beyond
beyond
100
100
seconds.
seconds
A
a
as
as
a
a
developer,
developer
you'll
you'll
come
come
across
across
all
all
kinds
kinds
of
of
different
different
real
real
life
life
implementations
implementations
of
of
graphs.
graphs
I
i
mentioned
mentioned
Facebook's
facebook's
social
social
graph
graph
at
at
the
the
beginning
beginning
of
of
the
the
video,
video
and
and
they're
they're
commonly
commonly
used
used
for
for
recommendation
recommendation
engines,
engines
like
like
Yelp,
yelp
for
for
example,
example
to
to
connect
connect
businesses
businesses
to
to
users
users
to
to
reviews,
reviews
or
or
Netflix
netflix
to
to
connect
connect
the
the
movies
movies
that
that
you
you
watch
watch
2
2
movies
movies
that
that
you
you
might
might
want
want
to
to
watch
watch
in
in
the
the
future.
future
They're
they're
also
also
used
used
to
to
represent
represent
geographic
geographic
data.
data
For
for
example,
example
on
on
Google
google
Maps,
maps
you
you
can
can
think
think
of
of
every
every
intersection
intersection
as
as
a
a
node
node
a
a
and
and
then
then
every
every
road
road
and
and
its
its
distance
distance
as
as
the
the
edge
edge
connecting
connecting
these
these
two
two
nodes.
nodes
Over
over
the
the
next
next
few
few
minutes,
minutes
we'll
we'll
implement
implement
a
a
basic
basic
graph
graph
in
in
JavaScript
javascript
based
based
on
on
the
the
flight
flight
connections
connections
between
between
airports.
airports
A
a
in
in
this
this
case,
case
every
every
airport
airport
is
is
a
a
node,
node
and
and
the
the
edge
edge
represents
represents
whether
whether
or
or
not
not
you
you
can
can
fly
fly
from
from
one
one
airport
airport
to
to
another.
another
This
this
edge
edge
could
could
contain
contain
additional
additional
information
information
like
like
the
the
kilometers
kilometers
between
between
the
the
two
two
a
a
words,
words
in
in
which
which
case
case
that
that
would
would
give
give
us
us
a
a
weighted
weighted
graph.
graph
The
the
routes
routes
between
between
2
2
airports
airports
could
could
be
be
one
one
way
way
or
or
two
two
way.
way
When
when
they
they
go
go
one
one
way,
way
we
we
have
have
a
a
directed
directed
graph.
graph
A
a
if
if
they
they
go
go
both
both
ways,
ways
it's
it's
an
an
undirected
undirected
graph.
graph
For
for
this
this
demo,
demo
we'll
we'll
try
try
to
to
keep
keep
things
things
simple.
simple
We'll
we'll
make
make
an
an
undirected
undirected
graph
graph
assuming
assuming
that
that
when
when
an
an
airplane
airplane
has
has
a
a
route,
route
it
it
can
can
fly
fly
back
back
and
and
forth
forth
between
between
the
the
two
two
a
a
it'll
it'll
be
be
unweighted,
unweighted
so
so
the
the
routes
routes
between
between
the
the
two
two
airports
airports
won't
won't
carry
carry
any
any
additional
additional
data,
data
and
and
we'll
we'll
assume
assume
cycles
cycles
are
are
not
not
possible.
possible
The
the
first
first
thing
thing
we'll
we'll
need
need
to
to
do
do
is
is
represent
represent
our
our
graph
graph
and
and
code.
code
Most
most
programming
programming
interviews
interviews
will
will
have
have
you
you
write
write
code
code
in
in
whatever
whatever
language
language
you
you
prefer.
prefer
We'll
we'll
be
be
using
using
JavaScript
javascript
here,
here
but
but
the
the
most
most
important
important
tip
tip
I
i
can
can
give
give
you
you
is
is
to
to
a
a
simply
simply
explain
explain
your
your
thinking
thinking
process
process
as
as
you're
you're
writing
writing
your
your
code.
code
Most
most
technical
technical
interviewers
interviewers
are
are
trying
trying
to
to
get
get
some
some
insight
insight
into
into
your
your
thinking
thinking
process
process
and
and
care
care
less
less
if
if
you
you
write
write
perfectly
perfectly
formatted
formatted
code.
code
Let's
let's
go
go
ahead
ahead
and
and
walk
walk
through
through
a
a
few
few
examples.
examples
You
you
might
might
get
get
a
a
question
question
like
like
this.
this
Here's
here's
a
a
list
list
of
of
airports
airports
and
and
a
a
list
list
of
of
routes
routes
connecting
connecting
these
these
airports.
airports
Now
now
represent
represent
this
this
data
data
as
as
a
a
graph.
graph
So
so
given
given
this
this
data,
data
we
we
can
can
represent
represent
the
the
graph
graph
in
in
2
2
ways,
ways
a
a
matrix
matrix
or
or
an
an
adjacency
adjacency
list.
list
A
a
matrix
matrix
takes
takes
up
up
more
more
space,
space
but
but
it's
it's
generally
generally
easier
easier
to
to
visualize
visualize
and
and
represent
represent
because
because
it's
it's
just
just
a
a
2
2
dimensional
dimensional
array
array
filled
filled
with
with
ones
ones
and
and
zeros.
zeros
Now
now
looking
looking
at
at
this
this
data,
data
I
i
can
can
see
see
there
there
are
are
not
not
very
very
many
many
routes
routes
relative
relative
to
to
the
the
number
number
of
of
possible
possible
combinations
combinations
between
between
these
these
airports.
airports
That
that
means
means
our
our
matrix
matrix
would
would
be
be
very
very
sparse
sparse
or,
or
in
in
other
other
words,
words
filled
filled
with
with
a
a
bunch
bunch
of
of
zeros
zeros
and
and
take
take
up
up
a
a
lot
lot
of
of
unnecessary
unnecessary
space,
space
and
and
it
it
would
would
be
be
less
less
efficient
efficient
to
to
iterate
iterate
over
over
and
and
search
search
through.
through
Therefore,
therefore
I
i
choose
choose
to
to
represent
represent
my
my
graph
graph
as
as
an
an
adjacency
adjacency
list.
list
We
we
can
can
implement
implement
an
an
adjacency
adjacency
list
list
as
as
a
a
set
set
of
of
key
key
value
value
pairs
pairs
a
a
where
where
the
the
key
key
is
is
the
the
name
name
of
of
the
the
airport
airport
or
or
the
the
node
node
and
and
the
the
value
value
is
is
an
an
array
array
of
of
edges
edges
or
or
the
the
other
other
airports
airports
that
that
it's
it's
connected
connected
to.
to
We
we
could
could
implement
implement
this
this
with
with
a
a
regular
regular
JavaScript
javascript
object,
object
but
but
a
a
better
better
option
option
might
might
be
be
a
a
map.
map
When
when
you're
you're
doing
doing
algorithm
algorithm
problems
problems
in
in
JavaScript,
javascript
a
a
map
map
tends
tends
to
to
be
be
a
a
better
better
option
option
than
than
a
a
regular
regular
object.
object
It
it
has
has
some
some
additional
additional
API
api
methods
methods
that
that
can
can
be
be
useful
useful
for
for
problems
problems
a
a
like
like
this.
this
And
and
it
it
just
just
behaves
behaves
more
more
like
like
a
a
regular
regular
dictionary
dictionary
or
or
hash
hash
map
map
that
that
you'll
you'll
find
find
in
in
other
other
languages.
languages
So
so
the
the
map
map
is
is
our
our
graph,
graph
and
and
at
at
this
this
point,
point
it's
it's
empty.
empty
The
the
first
first
thing
thing
we'll
we'll
do
do
is
is
define
define
a
a
function
function
that
that
can
can
add
add
a
a
node
node
to
to
the
the
map.
map
This
this
function
function
takes
takes
the
the
airport
airport
code
code
as
as
its
its
argument
argument
and
and
then
then
calls
calls
adjacency
adjacency
list
list
set
set
on
on
the
the
airport
airport
and
and
starts
starts
it
it
off
off
with
with
an
an
empty
empty
array.
array
And
and
that's
that's
all
all
it
it
takes
takes
to
to
represent
represent
a
a
node
node
on
on
the
the
graph.
graph
To
to
add
add
an
an
edge,
edge
we
we
need
need
to
to
update
update
the
the
entries
entries
for
for
both
both
the
the
origin
origin
airport
airport
and
and
the
the
destination.
destination
First,
first
we'll
we'll
grab
grab
the
the
entry
entry
for
for
the
the
origin
origin
airport
airport
and
and
then
then
push
push
the
the
destination
destination
onto
onto
its
its
list.
list
And
and
then
then
we'll
we'll
do
do
the
the
inverse
inverse
of
of
that
that
by
by
getting
getting
the
the
destination
destination
and
and
then
then
pushing
pushing
the
the
origin
origin
onto
onto
its
its
list.
list
And
and
that's
that's
our
our
entire
entire
API
api
for
for
building
building
a
a
graph
graph
as
as
an
an
adjacency
adjacency
list.
list
The
the
next
next
step
step
is
is
to
to
use
use
this
this
API
api
with
with
our
our
source
source
data.
data
We
we
can
can
loop
loop
over
over
the
the
airports
airports
with
with
4
4
each
each
and
and
for
for
each
each
one
one
call
call
the
the
add
add
node
node
method
method
to
to
add
add
a
a
node
node
to
to
the
the
graph.
graph
Once
once
we
we
have
have
our
our
nodes,
nodes
we
we
can
can
then
then
loop
loop
over
over
the
the
routes
routes
a
a
and
and
add
add
an
an
edge
edge
for
for
each
each
route
route
in
in
that
that
array.
array
That
that
function
function
takes
takes
2
2
arguments,
arguments
so
so
I'm
i'm
going
going
to
to
use
use
the
the
rest
rest
syntax
syntax
here
here
to
to
destructure
destructure
them.
them
Now
now
you
you
can
can
go
go
ahead
ahead
and
and
console
console
log
log
this
this
graph
graph
by
by
running
running
it
it
in
in
Node.
node
Js,
js
and
and
you
you
should
should
get
get
an
an
output
output
that
that
looks
looks
similar
similar
to
to
this.
this
Congratulations.
congratulations
You
you
just
just
got
got
through
through
the
the
first
first
part
part
of
of
the
the
interview,
interview
a
a
but
but
that
that
was
was
the
the
easy
easy
part.
part
Now
now
the
the
interviewer
interviewer
wants
wants
you
you
to
to
implement
implement
an
an
algorithm
algorithm
to
to
figure
figure
out
out
if
if
there's
there's
a
a
route
route
between
between
Phoenix
phoenix
and
and
Bangkok.
bangkok
A
a
and
and
as
as
you
you
know
know
from
from
earlier
earlier
in
in
the
the
video,
video
there
there
are
are
2
2
main
main
ways
ways
we
we
can
can
approach
approach
this,
this
depth
depth
first
first
search
search
or
or
breadth
breadth
first
first
search.
search
I
i
think
think
the
the
easier
easier
one
one
to
to
understand
understand
is
is
BFS.
bfs
You
you
know,
know
in
in
order
order
to
to
search
search
a
a
graph,
graph
you
you
have
have
to
to
start
start
somewhere.
somewhere
In
in
this
this
case,
case
we'll
we'll
start
start
with
with
the
the
Phoenix
phoenix
node.
node
So
so
we
we
need
need
a
a
function
function
that
that
takes
takes
a
a
starting
starting
node
node
as
as
its
its
argument.
argument
A
a
write
write
that
that
out
out
on
on
the
the
whiteboard
whiteboard
or
or
as
as
pseudo
pseudo
code
code
in
in
whatever
whatever
editing
editing
tool
tool
you're
you're
using
using
for
for
the
the
interview.
interview
From
from
the
the
starting
starting
node,
node
you
you
want
want
to
to
visit
visit
all
all
the
the
children
children
and
and
see
see
if
if
any
any
of
of
them
them
are
are
Bangkok.
bangkok
If
if
not,
not
you'll
you'll
want
want
to
to
visit
visit
their
their
children
children
and
and
do
do
the
the
same
same
thing.
thing
And
and
you'll
you'll
continue
continue
doing
doing
this
this
in
in
layers
layers
until
until
you
you
find
find
the
the
airport
airport
you're
you're
looking
looking
for.
for
We
we
can
can
represent
represent
this
this
process
process
as
as
a
a
queue,
queue
which
which
in
in
JavaScript
javascript
is
is
just
just
an
an
array
array
where
where
the
the
first
first
item
item
in
in
is
is
the
the
first
first
item
item
out.
out
And,
and
of
of
course,
course
the
the
first
first
item
item
in
in
your
your
queue
queue
should
should
be
be
the
the
starting
starting
node.
node
A
a
now
now
while
while
the
the
queue
queue
has
has
items
items
in
in
it
it
or
or
the
the
length
length
is
is
greater
greater
than
than
0,
0
we'll
we'll
grab
grab
the
the
first
first
item
item
in
in
the
the
array
array
using
using
the
the
array
array
shift
shift
method.
method
This
this
method
method
will
will
mutate
mutate
the
the
original
original
array
array
by
by
removing
removing
the
the
first
first
item
item
in
in
it
it
and
and
then
then
return
return
that
that
item
item
to
to
us
us
here
here
that
that
we
we
set
set
as
as
the
the
airport
airport
variable.
variable
A
a
our
our
next
next
step
step
is
is
to
to
grab
grab
all
all
the
the
edges
edges
for
for
this
this
node
node
in
in
the
the
graph.
graph
We
we
can
can
do
do
that
that
by
by
calling
calling
adjacency
adjacency
list
list
get
get
with
with
that
that
airport
airport
name
name
as
as
the
the
key.
key
That'll
that'll
give
give
us
us
all
all
the
the
destinations
destinations
for
for
the
the
airport
airport
or
or
its
its
children
children
so
so
we
we
can
can
loop
loop
over
over
them
them
and
and
add
add
them
them
to
to
the
the
queue
queue
as
as
well.
well
We
we
can
can
also
also
go
go
ahead
ahead
and
and
log
log
out
out
if
if
any
any
of
of
these
these
airports
airports
are
are
Bangkok,
bangkok
the
the
airport
airport
we're
we're
looking
looking
for.
for
Now
now
one
one
major
major
problem
problem
with
with
this
this
code
code
at
at
the
the
moment
moment
is
is
that
that
airports
airports
have
have
many
many
interconnected
interconnected
routes,
routes
and
and
that
that
means
means
our
our
algorithm
algorithm
will
will
be
be
visiting
visiting
the
the
same
same
nodes
nodes
over
over
and
and
over
over
again.
again
A
a
and
and
in
in
our
our
case,
case
this
this
creates
creates
an
an
infinite
infinite
loop
loop
because
because
the
the
queue
queue
is
is
never
never
emptied.
emptied
We
we
can
can
avoid
avoid
that
that
by
by
keeping
keeping
track
track
of
of
the
the
airports
airports
that
that
we
we
visited
visited
in
in
the
the
past.
past
An
an
easy
easy
way
way
to
to
do
do
that
that
in
in
JavaScript
javascript
is
is
with
with
a
a
set,
set
which
which
is
is
basically
basically
an
an
array,
array
but
but
all
all
the
the
values
values
in
in
it
it
are
are
unique.
unique
We
we
set
set
it
it
up
up
as
as
an
an
empty
empty
set
set
when
when
the
the
function
function
is
is
first
first
called,
called
then
then
we
we
can
can
use
use
it
it
to
to
set
set
up
up
some
some
conditional
conditional
logic
logic
in
in
our
our
loop.
loop
We
we
will
will
only
only
enqueue
enqueue
an
an
item
item
if
if
it
it
does
does
not
not
have
have
this
this
destination.
destination
A
a
set
set
has
has
a
a
has
has
method
method
a
a
where
where
you
you
can
can
pass
pass
a
a
value
value
to
to
see
see
if
if
it
it
exists
exists
currently
currently
in
in
the
the
set.
set
And
and
then
then
we'll
we'll
mark
mark
the
the
destination
destination
as
as
visited
visited
by
by
adding
adding
it
it
to
to
the
the
set.
set
Then
then
we'll
we'll
move
move
the
the
line
line
of
of
code
code
that
that
adds
adds
this
this
item
item
to
to
the
the
queue
queue
inside
inside
of
of
our
our
condition
condition
here.
here
So
so
an
an
item
item
only
only
gets
gets
enqueued
enqueued
if
if
it
it
has
has
not
not
been
been
visited
visited
already.
already
Now
now
let's
let's
go
go
ahead
ahead
and
and
call
call
our
our
function
function
using
using
Phoenix
phoenix
as
as
the
the
starting
starting
node.
node
What
what
you'll
you'll
notice
notice
is
is
that
that
it
it
goes
goes
through
through
9
9
airports
airports
before
before
it
it
finally
finally
finds
finds
Bangkok.
bangkok
It
it
starts
starts
with
with
all
all
the
the
connections
connections
to
to
Phoenix,
phoenix
then
then
all
all
the
the
connections
connections
to
to
JFK,
jfk
then
then
from
from
Mexico
mexico
City,
city
it
it
finds
finds
a
a
route
route
to
to
Bangkok.
bangkok
And
and
then
then
it
it
also
also
finds
finds
a
a
second
second
route
route
through
through
Lima,
lima
Peru.
peru
So
so
breadth
breadth
first
first
search
search
would
would
be
be
really
really
good
good
for
for
finding
finding
all
all
the
the
possible
possible
routes
routes
to
to
determine
determine
which
which
one
one
is
is
the
the
most
most
efficient.
efficient
At
at
this
this
point,
point
your
your
interviewer
interviewer
is
is
super
super
impressed.
impressed
A
a
but
but
then
then
here
here
she
she
says
says
our
our
only
only
concern
concern
is
is
if
if
a
a
route
route
from
from
Phoenix
phoenix
to
to
Bangkok
bangkok
exists.
exists
We
we
don't
don't
care
care
if
if
there
there
are
are
multiple
multiple
routes.
routes
We
we
don't
don't
care
care
if
if
it's
it's
the
the
best
best
route.
route
We
we
just
just
want
want
to
to
find
find
a
a
route
route
as
as
quickly
quickly
as
as
possible.
possible
How
how
can
can
you
you
traverse
traverse
this
this
graph
graph
more
more
efficiently
efficiently
to
to
meet
meet
that
that
need?
need
An
an
approach
approach
that
that
would
would
be
be
more
more
efficient
efficient
for
for
this
this
particular
particular
requirement
requirement
is
is
a
a
depth
depth
first
first
search.
search
A
a
instead
instead
of
of
going
going
through
through
all
all
the
the
children
children
or
or
destinations
destinations
for
for
each
each
airport,
airport
we'll
we'll
go
go
to
to
its
its
first
first
child
child
and
and
then
then
to
to
its
its
first
first
child
child
and
and
its
its
first
first
child
child
and
and
so
so
on
on
until
until
we
we
hit
hit
Bangkok.
bangkok
And
and
if
if
we
we
don't
don't
find
find
it,
it
we'll
we'll
backtrack
backtrack
to
to
the
the
top
top
of
of
the
the
graph
graph
and
and
follow
follow
the
the
same
same
pattern.
pattern
In
in
the
the
last
last
example,
example
we
we
used
used
a
a
queue.
queue
But
but
in
in
this
this
example,
example
we're
we're
going
going
to
to
use
use
a
a
recursive
recursive
function,
function
or
or
in
in
other
other
words,
words
a
a
function
function
that
that
calls
calls
itself
itself
until
until
it
it
reaches
reaches
some
some
kind
kind
of
of
stopping
stopping
point.
point
This
this
function
function
will
will
take
take
a
a
starting
starting
node
node
as
as
its
its
first
first
argument
argument
and
and
then
then
a
a
set
set
as
as
a
a
second
second
argument
argument
that
that
keeps
keeps
track
track
of
of
the
the
different
different
cities
cities
that
that
we
we
visited
visited
because,
because
again,
again
we
we
don't
don't
want
want
to
to
visit
visit
the
the
same
same
node
node
more
more
than
than
once.
once
From
from
there,
there
we'll
we'll
grab
grab
the
the
edges
edges
or
or
destinations
destinations
from
from
our
our
adjacency
adjacency
list.
list
We'll
we'll
loop
loop
over
over
them
them
just
just
like
like
we
we
did
did
before.
before
And
and
when
when
we
we
find
find
what
what
we're
we're
looking
looking
for,
for
we'll
we'll
just
just
return
return
from
from
the
the
function.
function
Now
now
here's
here's
the
the
interesting
interesting
part.
part
If
if
a
a
node
node
has
has
not
not
been
been
visited,
visited
then
then
we'll
we'll
go
go
ahead
ahead
and
and
call
call
the
the
same
same
function,
function
or
or
in
in
other
other
words,
words
call
call
it
it
recursively
recursively
with
with
the
the
current
current
destination
destination
in
in
the
the
loop
loop
as
as
well
well
as
as
our
our
visited
visited
set.
set
That
that
means
means
this
this
function
function
call
call
will
will
be
be
pushed
pushed
to
to
the
the
top
top
of
of
the
the
call
call
stack,
stack
making
making
the
the
algorithm
algorithm
go
go
deeper
deeper
and
and
deeper
deeper
into
into
the
the
tree
tree
until
until
it
it
reaches
reaches
a
a
stopping
stopping
point.
point
And
and
that
that
means
means
this
this
function
function
will
will
continue
continue
calling
calling
itself
itself
recursively
recursively
until
until
all
all
the
the
airports
airports
have
have
been
been
visited
visited
or
or
until
until
it
it
finds
finds
Bangkok.
bangkok
In
in
this
this
example,
example
it
it
only
only
takes
takes
3
3
steps
steps
or
or
3
3
function
function
calls
calls
to
to
find
find
the
the
route
route
as
as
opposed
opposed
to
to
8
8
in
in
our
our
previous
previous
algorithm.
algorithm
But
but
the
the
interviewer
interviewer
has
has
one
one
last
last
question.
question
What
what
is
is
the
the
time
time
complexity
complexity
of
of
the
the
algorithm
algorithm
that
that
you
you
just
just
implemented
implemented
as
as
expressed
expressed
in
in
big
big
o
o
notation?
notation
A
a
for
for
both
both
breadth
breadth
first
first
and
and
depth
depth
first
first
search,
search
big
big
o
o
is
is
expressed
expressed
as
as
v
v
plus
plus
e,
e
which
which
is
is
the
the
total
total
number
number
of
of
nodes
nodes
or
or
vertices
vertices
plus
plus
the
the
number
number
of
of
edges.
edges
Or,
or
in
in
other
other
words,
words
the
the
time
time
performance
performance
of
of
the
the
algorithm
algorithm
will
will
scale
scale
linear
linear
based
based
on
on
the
the
number
number
of
of
nodes
nodes
and
and
edges
edges
that
that
are
are
added
added
to
to
the
the
graph.
graph
I'm
i'm
gonna
gonna
go
go
ahead
ahead
and
and
wrap
wrap
things
things
up
up
there,
there
but
but
there
there
are
are
many
many
other
other
algorithms
algorithms
you
you
can
can
use
use
to
to
traverse
traverse
a
a
graph.
graph
So
so
if
if
you
you
wanna
wanna
see
see
more
more
videos
videos
like
like
this,
this
let
let
me
me
know
know
in
in
the
the
comments.
comments
Thanks
thanks
for
for
watching
watching
and
and
I
i
will
will
see
see
you
you
in
in
the
the
next
next
a.
a
success
In this conversation, the speakers discuss the use of graph structures in various software products. They recommend using a depth or breadth first search to create a graph and suggest using a method called a breadth first search and a method called a method first search to create a graph using a set of random elements. They also explain how to add an edge to a graph and discuss the use of a matrix or adjacency list to represent a graph and a map to create a adjacency list. Finally, they suggest using other algorithms for tapping a graph and suggest exploring other options for tapping a graph.
Graph Search Algorithms in 100 Seconds - And Beyond with JS
A graph is a nonlinear data structure that contains nodes and edges. A node or vertex is just a single unique value, while an edge represents a connection or relationship between 2 of these nodes. Think of something like Instagram. Every user is a node. Every time you follow a user, you create a new edge connecting 2 nodes together. This is known as a directed graph because the relationship flows one way. The follower follows the followee and not vice versa. Now consider Facebook. Your edges on the graph are friendships. This relationship goes both ways, which is known as an undirected graph. Graphs can to be weighted, which means the node has some additional data about the relationship, like the distance between 2 airports. A node might also point to itself, like an airplane that takes off and comes back to land at the same airport. This is known as a cycle. Graphs are used in many real life software products, and you'll often be asked to represent a graphic code in in a technical interview. One way to represent a graph is with a 2 d array or adjacency matrix. Create 1 row and 1 column for every node. When 2 nodes have an edge or connection at a one at the point they intersect. This makes it fast and easy to look up a specific edge or to add a new edge. But as a 2 d array, it takes quadratic space complexity and quadratic time to insert a new node into the graph. An alternative approach is an adjacency list. In this representation, we start with a collection of nodes, then each item has its own array of its neighbors. This makes it faster to iterate over a node's edges and is more efficient with memory, especially when you have many nodes and few edges. In your interview, you'll likely need to traverse your graph. One option is a depth first search. Start with any random node, go to its first child, then its first child, and do that for as long as you can. When there are no more children, backtrack to the last node and continue the process. A this algorithm is usually implemented with a recursive function. Another option is a breadth first search. From your starting node, add all of the direct children to a queue. Once they've been visited, a move on to the grandchildren and continue following this pattern in layers. This has been graphs in 100 seconds, but hang out for a few minutes because now we're going to implement these algorithms in JavaScript. If you're new here, like and subscribe, hit the like button, open your IDE, and get ready to go beyond 100 seconds. A as a developer, you'll come across all kinds of different real life implementations of graphs. I mentioned Facebook's social graph at the beginning of the video, and they're commonly used for recommendation engines, like Yelp, for example, to connect businesses to users to reviews, or Netflix to connect the movies that you watch 2 movies that you might want to watch in the future. They're also used to represent geographic data. For example, on Google Maps, you can think of every intersection as a node a and then every road and its distance as the edge connecting these two nodes. Over the next few minutes, we'll implement a basic graph in JavaScript based on the flight connections between airports. A in this case, every airport is a node, and the edge represents whether or not you can fly from one airport to another. This edge could contain additional information like the kilometers between the two a words, in which case that would give us a weighted graph. The routes between 2 airports could be one way or two way. When they go one way, we have a directed graph. A if they go both ways, it's an undirected graph. For this demo, we'll try to keep things simple. We'll make an undirected graph assuming that when an airplane has a route, it can fly back and forth between the two a it'll be unweighted, so the routes between the two airports won't carry any additional data, and we'll assume cycles are not possible. The first thing we'll need to do is represent our graph and code. Most programming interviews will have you write code in whatever language you prefer. We'll be using JavaScript here, but the most important tip I can give you is to a simply explain your thinking process as you're writing your code. Most technical interviewers are trying to get some insight into your thinking process and care less if you write perfectly formatted code. Let's go ahead and walk through a few examples. You might get a question like this. Here's a list of airports and a list of routes connecting these airports. Now represent this data as a graph. So given this data, we can represent the graph in 2 ways, a matrix or an adjacency list. A matrix takes up more space, but it's generally easier to visualize and represent because it's just a 2 dimensional array filled with ones and zeros. Now looking at this data, I can see there are not very many routes relative to the number of possible combinations between these airports. That means our matrix would be very sparse or, in other words, filled with a bunch of zeros and take up a lot of unnecessary space, and it would be less efficient to iterate over and search through. Therefore, I choose to represent my graph as an adjacency list. We can implement an adjacency list as a set of key value pairs a where the key is the name of the airport or the node and the value is an array of edges or the other airports that it's connected to. We could implement this with a regular JavaScript object, but a better option might be a map. When you're doing algorithm problems in JavaScript, a map tends to be a better option than a regular object. It has some additional API methods that can be useful for problems a like this. And it just behaves more like a regular dictionary or hash map that you'll find in other languages. So the map is our graph, and at this point, it's empty. The first thing we'll do is define a function that can add a node to the map. This function takes the airport code as its argument and then calls adjacency list set on the airport and starts it off with an empty array. And that's all it takes to represent a node on the graph. To add an edge, we need to update the entries for both the origin airport and the destination. First, we'll grab the entry for the origin airport and then push the destination onto its list. And then we'll do the inverse of that by getting the destination and then pushing the origin onto its list. And that's our entire API for building a graph as an adjacency list. The next step is to use this API with our source data. We can loop over the airports with 4 each and for each one call the add node method to add a node to the graph. Once we have our nodes, we can then loop over the routes a and add an edge for each route in that array. That function takes 2 arguments, so I'm going to use the rest syntax here to destructure them. Now you can go ahead and console log this graph by running it in Node. Js, and you should get an output that looks similar to this. Congratulations. You just got through the first part of the interview, a but that was the easy part. Now the interviewer wants you to implement an algorithm to figure out if there's a route between Phoenix and Bangkok. A and as you know from earlier in the video, there are 2 main ways we can approach this, depth first search or breadth first search. I think the easier one to understand is BFS. You know, in order to search a graph, you have to start somewhere. In this case, we'll start with the Phoenix node. So we need a function that takes a starting node as its argument. A write that out on the whiteboard or as pseudo code in whatever editing tool you're using for the interview. From the starting node, you want to visit all the children and see if any of them are Bangkok. If not, you'll want to visit their children and do the same thing. And you'll continue doing this in layers until you find the airport you're looking for. We can represent this process as a queue, which in JavaScript is just an array where the first item in is the first item out. And, of course, the first item in your queue should be the starting node. A now while the queue has items in it or the length is greater than 0, we'll grab the first item in the array using the array shift method. This method will mutate the original array by removing the first item in it and then return that item to us here that we set as the airport variable. A our next step is to grab all the edges for this node in the graph. We can do that by calling adjacency list get with that airport name as the key. That'll give us all the destinations for the airport or its children so we can loop over them and add them to the queue as well. We can also go ahead and log out if any of these airports are Bangkok, the airport we're looking for. Now one major problem with this code at the moment is that airports have many interconnected routes, and that means our algorithm will be visiting the same nodes over and over again. A and in our case, this creates an infinite loop because the queue is never emptied. We can avoid that by keeping track of the airports that we visited in the past. An easy way to do that in JavaScript is with a set, which is basically an array, but all the values in it are unique. We set it up as an empty set when the function is first called, then we can use it to set up some conditional logic in our loop. We will only enqueue an item if it does not have this destination. A set has a has method a where you can pass a value to see if it exists currently in the set. And then we'll mark the destination as visited by adding it to the set. Then we'll move the line of code that adds this item to the queue inside of our condition here. So an item only gets enqueued if it has not been visited already. Now let's go ahead and call our function using Phoenix as the starting node. What you'll notice is that it goes through 9 airports before it finally finds Bangkok. It starts with all the connections to Phoenix, then all the connections to JFK, then from Mexico City, it finds a route to Bangkok. And then it also finds a second route through Lima, Peru. So breadth first search would be really good for finding all the possible routes to determine which one is the most efficient. At this point, your interviewer is super impressed. A but then here she says our only concern is if a route from Phoenix to Bangkok exists. We don't care if there are multiple routes. We don't care if it's the best route. We just want to find a route as quickly as possible. How can you traverse this graph more efficiently to meet that need? An approach that would be more efficient for this particular requirement is a depth first search. A instead of going through all the children or destinations for each airport, we'll go to its first child and then to its first child and its first child and so on until we hit Bangkok. And if we don't find it, we'll backtrack to the top of the graph and follow the same pattern. In the last example, we used a queue. But in this example, we're going to use a recursive function, or in other words, a function that calls itself until it reaches some kind of stopping point. This function will take a starting node as its first argument and then a set as a second argument that keeps track of the different cities that we visited because, again, we don't want to visit the same node more than once. From there, we'll grab the edges or destinations from our adjacency list. We'll loop over them just like we did before. And when we find what we're looking for, we'll just return from the function. Now here's the interesting part. If a node has not been visited, then we'll go ahead and call the same function, or in other words, call it recursively with the current destination in the loop as well as our visited set. That means this function call will be pushed to the top of the call stack, making the algorithm go deeper and deeper into the tree until it reaches a stopping point. And that means this function will continue calling itself recursively until all the airports have been visited or until it finds Bangkok. In this example, it only takes 3 steps or 3 function calls to find the route as opposed to 8 in our previous algorithm. But the interviewer has one last question. What is the time complexity of the algorithm that you just implemented as expressed in big o notation? A for both breadth first and depth first search, big o is expressed as v plus e, which is the total number of nodes or vertices plus the number of edges. Or, in other words, the time performance of the algorithm will scale linear based on the number of nodes and edges that are added to the graph. I'm gonna go ahead and wrap things up there, but there are many other algorithms you can use to traverse a graph. So if you wanna see more videos like this, let me know in the comments. Thanks for watching and I will see you in the next a.
In this conversation, the speakers discuss the use of graph structures in various software products. They recommend using a depth or breadth first search to create a graph and suggest using a method called a breadth first search and a method called a method first search to create a graph using a set of random elements. They also explain how to add an edge to a graph and discuss the use of a matrix or adjacency list to represent a graph and a map to create a adjacency list. Finally, they suggest using other algorithms for tapping a graph and suggest exploring other options for tapping a graph.

        [INST]
        You are youtuber called Fireship you make engaging high-intensity and entertaining coding tutorials and tech news. 
        you covers a wide range of topics relevant to programmers, aiming to help them learn and improve their skills quickly.
        
        Given the title of the video : Graph Search Algorithms in 100 Seconds - And Beyond with JS 
        and a small summary : In this conversation, the speakers discuss the use of graph structures in various software products. They recommend using a depth or breadth first search to create a graph and suggest using a method called a breadth first search and a method called a method first search to create a graph using a set of random elements. They also explain how to add an edge to a graph and discuss the use of a matrix or adjacency list to represent a graph and a map to create a adjacency list. Finally, they suggest using other algorithms for tapping a graph and suggest exploring other options for tapping a graph.
        [/INST]
        
        Generate the video : A graph is a nonlinear data structure that contains nodes and edges. A node or vertex is just a single unique value, while an edge represents a connection or relationship between 2 of these nodes. Think of something like Instagram. Every user is a node. Every time you follow a user, you create a new edge connecting 2 nodes together. This is known as a directed graph because the relationship flows one way. The follower follows the followee and not vice versa. Now consider Facebook. Your edges on the graph are friendships. This relationship goes both ways, which is known as an undirected graph. Graphs can to be weighted, which means the node has some additional data about the relationship, like the distance between 2 airports. A node might also point to itself, like an airplane that takes off and comes back to land at the same airport. This is known as a cycle. Graphs are used in many real life software products, and you'll often be asked to represent a graphic code in in a technical interview. One way to represent a graph is with a 2 d array or adjacency matrix. Create 1 row and 1 column for every node. When 2 nodes have an edge or connection at a one at the point they intersect. This makes it fast and easy to look up a specific edge or to add a new edge. But as a 2 d array, it takes quadratic space complexity and quadratic time to insert a new node into the graph. An alternative approach is an adjacency list. In this representation, we start with a collection of nodes, then each item has its own array of its neighbors. This makes it faster to iterate over a node's edges and is more efficient with memory, especially when you have many nodes and few edges. In your interview, you'll likely need to traverse your graph. One option is a depth first search. Start with any random node, go to its first child, then its first child, and do that for as long as you can. When there are no more children, backtrack to the last node and continue the process. A this algorithm is usually implemented with a recursive function. Another option is a breadth first search. From your starting node, add all of the direct children to a queue. Once they've been visited, a move on to the grandchildren and continue following this pattern in layers. This has been graphs in 100 seconds, but hang out for a few minutes because now we're going to implement these algorithms in JavaScript. If you're new here, like and subscribe, hit the like button, open your IDE, and get ready to go beyond 100 seconds. A as a developer, you'll come across all kinds of different real life implementations of graphs. I mentioned Facebook's social graph at the beginning of the video, and they're commonly used for recommendation engines, like Yelp, for example, to connect businesses to users to reviews, or Netflix to connect the movies that you watch 2 movies that you might want to watch in the future. They're also used to represent geographic data. For example, on Google Maps, you can think of every intersection as a node a and then every road and its distance as the edge connecting these two nodes. Over the next few minutes, we'll implement a basic graph in JavaScript based on the flight connections between airports. A in this case, every airport is a node, and the edge represents whether or not you can fly from one airport to another. This edge could contain additional information like the kilometers between the two a words, in which case that would give us a weighted graph. The routes between 2 airports could be one way or two way. When they go one way, we have a directed graph. A if they go both ways, it's an undirected graph. For this demo, we'll try to keep things simple. We'll make an undirected graph assuming that when an airplane has a route, it can fly back and forth between the two a it'll be unweighted, so the routes between the two airports won't carry any additional data, and we'll assume cycles are not possible. The first thing we'll need to do is represent our graph and code. Most programming interviews will have you write code in whatever language you prefer. We'll be using JavaScript here, but the most important tip I can give you is to a simply explain your thinking process as you're writing your code. Most technical interviewers are trying to get some insight into your thinking process and care less if you write perfectly formatted code. Let's go ahead and walk through a few examples. You might get a question like this. Here's a list of airports and a list of routes connecting these airports. Now represent this data as a graph. So given this data, we can represent the graph in 2 ways, a matrix or an adjacency list. A matrix takes up more space, but it's generally easier to visualize and represent because it's just a 2 dimensional array filled with ones and zeros. Now looking at this data, I can see there are not very many routes relative to the number of possible combinations between these airports. That means our matrix would be very sparse or, in other words, filled with a bunch of zeros and take up a lot of unnecessary space, and it would be less efficient to iterate over and search through. Therefore, I choose to represent my graph as an adjacency list. We can implement an adjacency list as a set of key value pairs a where the key is the name of the airport or the node and the value is an array of edges or the other airports that it's connected to. We could implement this with a regular JavaScript object, but a better option might be a map. When you're doing algorithm problems in JavaScript, a map tends to be a better option than a regular object. It has some additional API methods that can be useful for problems a like this. And it just behaves more like a regular dictionary or hash map that you'll find in other languages. So the map is our graph, and at this point, it's empty. The first thing we'll do is define a function that can add a node to the map. This function takes the airport code as its argument and then calls adjacency list set on the airport and starts it off with an empty array. And that's all it takes to represent a node on the graph. To add an edge, we need to update the entries for both the origin airport and the destination. First, we'll grab the entry for the origin airport and then push the destination onto its list. And then we'll do the inverse of that by getting the destination and then pushing the origin onto its list. And that's our entire API for building a graph as an adjacency list. The next step is to use this API with our source data. We can loop over the airports with 4 each and for each one call the add node method to add a node to the graph. Once we have our nodes, we can then loop over the routes a and add an edge for each route in that array. That function takes 2 arguments, so I'm going to use the rest syntax here to destructure them. Now you can go ahead and console log this graph by running it in Node. Js, and you should get an output that looks similar to this. Congratulations. You just got through the first part of the interview, a but that was the easy part. Now the interviewer wants you to implement an algorithm to figure out if there's a route between Phoenix and Bangkok. A and as you know from earlier in the video, there are 2 main ways we can approach this, depth first search or breadth first search. I think the easier one to understand is BFS. You know, in order to search a graph, you have to start somewhere. In this case, we'll start with the Phoenix node. So we need a function that takes a starting node as its argument. A write that out on the whiteboard or as pseudo code in whatever editing tool you're using for the interview. From the starting node, you want to visit all the children and see if any of them are Bangkok. If not, you'll want to visit their children and do the same thing. And you'll continue doing this in layers until you find the airport you're looking for. We can represent this process as a queue, which in JavaScript is just an array where the first item in is the first item out. And, of course, the first item in your queue should be the starting node. A now while the queue has items in it or the length is greater than 0, we'll grab the first item in the array using the array shift method. This method will mutate the original array by removing the first item in it and then return that item to us here that we set as the airport variable. A our next step is to grab all the edges for this node in the graph. We can do that by calling adjacency list get with that airport name as the key. That'll give us all the destinations for the airport or its children so we can loop over them and add them to the queue as well. We can also go ahead and log out if any of these airports are Bangkok, the airport we're looking for. Now one major problem with this code at the moment is that airports have many interconnected routes, and that means our algorithm will be visiting the same nodes over and over again. A and in our case, this creates an infinite loop because the queue is never emptied. We can avoid that by keeping track of the airports that we visited in the past. An easy way to do that in JavaScript is with a set, which is basically an array, but all the values in it are unique. We set it up as an empty set when the function is first called, then we can use it to set up some conditional logic in our loop. We will only enqueue an item if it does not have this destination. A set has a has method a where you can pass a value to see if it exists currently in the set. And then we'll mark the destination as visited by adding it to the set. Then we'll move the line of code that adds this item to the queue inside of our condition here. So an item only gets enqueued if it has not been visited already. Now let's go ahead and call our function using Phoenix as the starting node. What you'll notice is that it goes through 9 airports before it finally finds Bangkok. It starts with all the connections to Phoenix, then all the connections to JFK, then from Mexico City, it finds a route to Bangkok. And then it also finds a second route through Lima, Peru. So breadth first search would be really good for finding all the possible routes to determine which one is the most efficient. At this point, your interviewer is super impressed. A but then here she says our only concern is if a route from Phoenix to Bangkok exists. We don't care if there are multiple routes. We don't care if it's the best route. We just want to find a route as quickly as possible. How can you traverse this graph more efficiently to meet that need? An approach that would be more efficient for this particular requirement is a depth first search. A instead of going through all the children or destinations for each airport, we'll go to its first child and then to its first child and its first child and so on until we hit Bangkok. And if we don't find it, we'll backtrack to the top of the graph and follow the same pattern. In the last example, we used a queue. But in this example, we're going to use a recursive function, or in other words, a function that calls itself until it reaches some kind of stopping point. This function will take a starting node as its first argument and then a set as a second argument that keeps track of the different cities that we visited because, again, we don't want to visit the same node more than once. From there, we'll grab the edges or destinations from our adjacency list. We'll loop over them just like we did before. And when we find what we're looking for, we'll just return from the function. Now here's the interesting part. If a node has not been visited, then we'll go ahead and call the same function, or in other words, call it recursively with the current destination in the loop as well as our visited set. That means this function call will be pushed to the top of the call stack, making the algorithm go deeper and deeper into the tree until it reaches a stopping point. And that means this function will continue calling itself recursively until all the airports have been visited or until it finds Bangkok. In this example, it only takes 3 steps or 3 function calls to find the route as opposed to 8 in our previous algorithm. But the interviewer has one last question. What is the time complexity of the algorithm that you just implemented as expressed in big o notation? A for both breadth first and depth first search, big o is expressed as v plus e, which is the total number of nodes or vertices plus the number of edges. Or, in other words, the time performance of the algorithm will scale linear based on the number of nodes and edges that are added to the graph. I'm gonna go ahead and wrap things up there, but there are many other algorithms you can use to traverse a graph. So if you wanna see more videos like this, let me know in the comments. Thanks for watching and I will see you in the next a.
        