Hello and welcome back. My name is William and today's topic is the breadth first search graph traversal algorithm. Alongside the depth first search the breadth first search algorithm is another one of those fundamental search algorithms used to explore nodes and edges of a graph. It runs in a time complexity of big O of v plus e, that is vertices plus edges, and is often used as a building block in other algorithms. It differs from a depth first search in the way that it explores the graph. The breadth first search algorithm is particularly useful for one thing, finding the shortest path on an unweighted graph.

A breadth first search starts at a node in the graph and explores its neighbor nodes first before moving on to explore the next level of neighbors in a sense of breadth first search explores nodes in layers. So if we start breadth first search at zero We would visit zero first, then visit all of zeros neighbors, then we would visit all of zeros neighbors, the nodes in yellow before moving on to the next layer of notes, then we would visit all their neighbors and so on. So as you saw a breadth first search expose a graph in a layered fashion, it does this by maintaining a queue of which node it should visit next, this is most easily seen with an example. Let's begin a breadth first search at node zero once more. So let's add zero to the queue on the left, I will denote the current node in red.

So zero is the current node, and we want to explore all of zeros unvisited neighbors and add them to the queue. So we would add nine to the queue seven to the queue and 11 to the cube. So zero has no more unvisited neighbors. So we move on So nine is next up in the queue. So we add all of nines unvisited neighbors to the queue. So that is 10 and eight, then there are no more neighbors of nine to visit.

So we move on to the next node in our queue, which is seven. Then we add all of sevens unvisited neighbors to the queue. So we try and visit node 11. But note 11 is already in the queue, so we don't want to add it again. So we skip it. Then we would add six to the queue and three to the queue.

Then this process goes on and on until we run out of nodes in the queue. So I will let the animation play That's how you do a breadth first search in a nutshell. In the previous animation, we relied on a queue to help us track which node we should visit next. Upon reaching a new node, the algorithm adds it to the queue to visit it later. The queue dish structure works like a real world queue, such as a waiting line in the restaurant. People can either enter the waiting line that is get in queued, or get seated D queued.

Let's look at some pseudocode for the breadth first search. First things first, we'll need two variables and the number of nodes in our graph and G the adjacency list representing our unweighted graph. This breadth first search function takes two arguments s and E the start and end node indices of the state Search. The return value for this function is the shortest path of nodes from S to E. I've divided the function into two methods for simplicity. First, we solve the problem by executing the breadth first search, and then we reconstruct the path from S to eat. So let's take a look at the solve method.

So here we are inside the solve method. The first thing I do is initialize the queue data structure that we'll need and add the starting node to it. This queue should support at minimum the N q and dq operations I just talked about, then initialize a Boolean array with all false values and mark the starting node as visited. This array tracks whether or not node II has been visited. If the value at index is true, then the node has either been visited or is being visited and is on the queue. In the animation this corresponds to the gray and yellow nodes.

The last thing we'll need is an array called prev, which will help us reconstruct the shortest path from the start to the end node. Initially, this array should be initialized with all null values. This array tracks who the parent of node II was, so we can reconstruct the path later. Let's loop while the queue is not empty and plot the top node from the queue by issuing a dq operation, then reach inside the adjacency lists and get all the neighbors of this node loop over each unvisited node. Once we find a next unvisited node and queue it to the queue, mark it as visited and keep track of the parent node of the next node in the prep array. Once the queue is empty, and our breakfast searches complete, simply return the prev array.

Back inside the breadth first search method, take the output of the solve method, which gives us the prev array and call the reconstruct path method. Here we are inside the reconstruct path method, the first thing we do is actually reconstruct the path by looping backwards from the end node and making our way back to the start node. That is assuming we can reach it. The reason the prep array had to be initialized to all null values is because that is the way I'm checking whether or not the for loop should stop. Since we loop through the prep array backwards starting with the end node, we need to reverse the order of the nodes so that the path starts at the start node and ends at the end node. Last but not least, we actually have to make sure the path between nodes s and He exists, it might not be possible to reach node E from node s. If the graph is disjoint.

If this is the case, then simply return an empty path. And that's it for this breadth first search video. Thank you for watching. Please give this video a thumbs up and subscribe for more mathematics and computer science videos.