In this video, we're going to have a look at how queues are used to do a breadth first search and then we're going to look at the actual implementation details of how n queuing and D queuing elements works. Okay onto the breadth first search example. So a breadth first search is an operation we can do on the graph to do a graph traversal. If you don't know what I mean when I say graph, I mean a network not a bar graph or a line graph or anything like that. But first session explain the breadth first search in the breadth first search. The objective is to start a node and traverse the entire graph first by visiting all the neighbors of the starting node and then visiting all the neighbors of the first node you visited and then all the neighbors are the second node you visited and so on so forth, expanding throughout Neighbors as you go.

So you can think of each iteration of the breadth first search as expanding the frontier from one node outwards at each iteration as you go on. So let's begin our breadth first search at node zero. So I'm going to label node zero as yellow and put it in the frontier, or the visiting group. And now I'm going to visit all the neighbors of zero being one and nine, add those to the frontier. And then which was our neighbors of one and nine being only eight. Similarly for eight, so seven, and visit all the neighbors of seven, so added a bunch of elements, my frontier, and now visit all the neighbors of the yellow nodes.

And now we're done. breadth first search because we no longer have any elements on frontier. Notice that there's 12 that is the unvisited because 12 is a loner node on an island all by itself. So we are not able to reach it via breadth first search, which is fine. Suppose you wanted to actually code a bath for search, how would that be done? Well, the idea is to use a queue.

So first, we add the starting node to our queue. And then we mark the starting as visited. And while our queue is not empty, we pull an element from our queue or D queuing. And then for every neighbor of this node, we just queued if the neighbor has not been visited, Mark, the neighbors visited and added to the queue. So now we have a way of processing all the nodes in our graph and a breadth first search order. Really, really useful, very, very popular graph traversal algorithm.

So now let's look at implementation of queues. So let's begin with an queueing. So it turns out that you can implement the queue abstract data type in multiple different ways. But the most popular methods are to either use arrays, singly linked lists, or doubly linked lists. If you're using an array, you have to make sure your arrays going to be big enough. If it's a static array.

If it's a dynamic array, then you'll be fine. But here I'm going to show you how to do it with a singly linked list and the source code we're using a doubly linked list so stay tuned for that. In the singly linked lists, we're going to have a head pointer and a tail pointer. So Initially, they're both No. But as we mq we add, we just add the first node. So nothing really interesting is going on right now.

But as we incue more elements, you can see that we're pushing the tail pointer forward. So we're adding a node and then getting the tail pointer point to the next node. Now D queuing is a bit of the opposite. And so pushing the tail forward, we're going to be pushing the head forward. So push the head forward one, and then the element that was left over was the one we want to dq and return to the user. So when we push the head pointer forward, we set the last node to null so that it can be picked up by the garbage collector if you're in Java, I'm sure another programming language which requires you to explicitly deallocate or free memory, yourself like C or c++ class, now's the time to do that.

So you see, as we keep D queuing, we're just pushing the head forward and forward again. And at the very end, if we add a bunch of elements and remove them all, then the head and the tail again, point to know, which is where we started. Alright, now it's going to be time to look at some source code, I implemented a queue. So we can look at that in some details. Also, if you want the Q source code, that's in the next video, how work code repository I posted below. There should also be a link in the description.

So guys, thanks for watching and see you in the next video.