Breadth First Search Algorithm | Shortest Path | Graph Theory

Key Takeaways

hello and welcome back my name is William and today's topic is the breath for search graph traversal algorithm alongside the depth first search the breath 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 for search in the way that it explores the graph the bread for search algorithm is particularly useful for one thing finding the shortest path on an unweighted graph a breath for 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 a breath first search explores nodes in layers so if we start breath first search at zero we would visit zero first then visit all of Zero's neighbors then we would visit all of Zero's neighbors the nodes in yellow before moving on to the next layer of nodes then we would visit all their neighbors and so on so as you saw a breath for search explores a graph in a layered fashion it does this by maintaining a cue of which node it should visit next this is most easily seen with with an example let's begin a breath for search at node 0 once more so let's add Zer to the Q on the left I will denote the current node in Red so zero is the current node and we want to explore all of Zero's unvisited neighbors and add them to the Q so we would add 9 to the Q 7 to the Q and 11 to the CU so zero has no more unvisited neighbors so we move on so nine is next up in the que so we add all of Nine's unvisited neighbors to the que 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 que which is seven then we add all of Seven's unvisited neighbors to the que so we try and visit node 11 but node 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 Q and 3 to the Q then this process goes on and on until we run out of nodes in the Q so I will let the animation play and that's how you do a breath for search in a nutshell in the previous animation we relied on a q to help us track which node we should visit next upon reaching a new node the algorithm adds it to the que to visit it later the queue data structure works like a realworld queue such as a waiting line in a restaurant people can either enter the waiting line that is get enced or get seated dced let's look at some pseudo code for the breath for search first things first we'll need two variables n the number of nodes in our graph and G the adjacency list representing our unweighted graph this breath for search function takes two arguments S and E the start and end node indices of the the 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 bre for search and then we reconstruct the path from s to e 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 Q data structure that we'll need and add add the starting node to it this Q should support at minimum the NQ 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 I has been visited if the value at index I 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 I 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 I was so we can reconstruct the path later let's Loop while the Q is not empty and pull out the top node from the que by issuing a DQ operation then reach inside the adjacency list and get all the neighbors of this node Loop over each unvisited node once we find a next unvisited node enq it to the Q mark it as visited and keep track of the parent node of the next node in the prev array once the queue is empty and our breath first search is complete simply return the prev array back inside the breath first search method take the output of the solve method which gave 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 prev 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 prev 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 E 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 breath for search video thank you for watching please give this video a thumbs up and subscribe for more mathematics and computer science videos