Graphs: breadth-first search - Beau teaches JavaScript

Key Takeaways

i gave an introduction about graphs in a previous video in this video i'm going to talk about how to find the distances between two nodes in a graph this is one of the main uses of graphs and is called graph traversal traversal algorithms are algorithms used to traverse or visit nodes in a graph the main types of traversal algorithms are breadth first search and depth first search in this video i will be showing how to implement breadth first search in javascript as you can see the algorithm starts at one node first visits all its neighbors that are one edge away then goes on to visiting each of their neighbors the point is to determine how close nodes are to a root node there are different ways to implement breadth first search in this version you pass in an adjacency matrix graph and the index of the root node remember in an adjacency matrix each nested array in the matrix shows which nodes in the graph are connected to the node at that index for example this array is at index 0 so it shows which nodes that node 0 is connected to if it is connected to a node there is a 1 at that index but if it is not connected there is a 0 at that index before i go through the code let's see it in action so here is a graphical representation of this adjacency graph check out my previous graph video to see how this adjacency graph goes into this graph so we ran the breadth first search function we passed in this graph up here and then we passed in the number one so that means we're trying to find out how far away every node is from the first node so you can see this graphical representation of the exact same graph and if you see the first node right here that's the node we passed in to the the breadth first search function we're going to see how far away each node is so you can see right here it shows how far away is so node zero is two nodes away see because of the direction of the graph we can't just go straight across a zero first from one we go to two then we go to zero so that's two nodes away one the the node itself is always zero nodes away and then the second node is one node away just one third node is three nodes away see first you have to start at one then you go to two then zero then three so that's three hops and four is infinity because when you're on from the first node it's impossible to get to the fourth node because the fourth node only points back to the first node this function will output an object of key value pairs where key is the node and the value is its distance from the root this object will be used to store the distances to the root node we will start all the distances at infinity which in this version of breadth first search indicates that a node is not reachable from the start node here the distance to the root node from the root node is set to zero instead of infinity we are going to create a simple queue to keep track of nodes to visit and the purpose of this variable is to keep track of the current node that we are traversing now we will start a while loop to keep traversing nodes until there are no more nodes in the queue to traverse we'll start the loop by popping off a node from the queue to traverse which at the beginning is the root node here we get all the nodes connected to the current node remember each index of the graph is an array that shows what nodes are connected to the root node associated with that index so in this example we are first looking at node one at node 1 the array shows that it is connected to nodes 0 and 2. now we set the neighbor index variable to an empty array this will keep track of a list of nodes that are connected to the current node this line gets the first node connected to the current node when it says index of 1 this finds the first connected node because the number 1 in our array means that the node is connected to another node at that index if there is no node with an index of one the index variable will be set to negative one so while index does not equal negative one push the index onto our list of neighbors this line searches for the next connected node we look for the next one in the array starting after the previous one we found that's what this plus one means now that we know all the nodes connected to the current node we loop through these connected nodes and get the distance if the value in the node's lin array at the index of the neighbor from the neighbor index array equals infinity that means we haven't set the distance of that node yet so we will set it now we are going to set it to the value of the the node's length array for the current node plus one then we'll push that neighbor to the queue so the next time we go through the while loop we'll check the neighbors of that node too this for loop is the most complicated part of this and you may have to read through it a couple times to completely understand it at the end we return the node's length array and that's breadth first search of a graph thanks for watching my name is beau carnes don't forget to subscribe and remember use your code for good