Breadth First Search Algorithm | Shortest Path | Graph Theory
Вставка
- Опубліковано 20 тра 2024
- Breadth First Search (BFS) algorithm explanation video with shortest path code
Algorithms repository:
github.com/williamfiset/algor...
Video Slides:
github.com/williamfiset/Algor...
=====================================
Practicing for interviews? I have used, and recommend `Cracking the Coding Interview` which got me a job at Google. Link on Amazon: amzn.to/3cvMof5
A lot of the content on this channel is inspired by the book `Competitive Programming` by Steven Halim which I frequently use as a resource and reference. Link on Amazon: amzn.to/3wC2nix
Support me by purchasing the full graph theory course on Udemy which includes additional problems, exercises and quizzes not available on UA-cam:
www.udemy.com/course/graph-th...
Wow this is by far the most understandable explanation of this concept that I've seen. Thank you!
the best explanation I 've seen fo far. Simple, clear, and focus without redundant words. Saving a lot of time. Love it and subscribed
Agreed
@Louis Jesse dude you chose the wrong type of people to dump your bs on. computer scientists dgaf about your animal relations.
Thank you so much!! As a really confused CS student who just started algorithms course this helped me a lot!
I appreciate the effort you put into making these tutorials man. You are the best.
You're one of the few explaining it with an end node and path reconstruct. Thank you!
Wow this is such a basic concept I can't believe my teacher couldn't explain it. He just gave us actual code to start out with. Universities seriously need to stop hiring grad students as teachers.
Wow, so many great tutors on the internet already, but you have explained it in a very digestible manner, thank you for your service, this helped me in getting my first dev job.
Crystal clear explanation. Many implementation details well covered!
Good explanation. That queue drawing finally helped me get it.
You turned 2 hours of confusing lectures into a simple 7 minute video. Thank you!
Trying for 3 hours to do it myself, came here to see the solution. I forgot the prev array, and In fact even If I visited the whole graph and found the final node, didn't know how to reconstruct everything :D Thanks a lot
You have saved my academic.
This is the best explanation I've seen so far. Thank you!
Best explanation ever, hope to see more videos like this from you William! Keep up the good work
You are a legend! Best explanation ever!
Best Explanation and Representation for BFS topic on UA-cam...
This was extremely useful. Thanks!
Keep working this way!
Quality vids.. Subscribed. Thanks for your time and effort!
The best video about BFS I've watched! Thanks I already understand it! :D
Best explanation possible. Thanks a lot!
thanks man, amazing video. so straightforward and useful!
Currently implementing this "in the wild". Good to see that the "right" way to do it is pretty much what I figured out
Great video! Thaaanks for the clear explanation.
hi thanks for the very clear explaination, but I cannot find the code where we are trying to find the Min or max path from S to E
Thank you very much William. You are the best!
Your animation just clicked it for me. Awesome :)
Very good explanation and it is nice that you added pseudocode !!!!
Thanks for your time sir ...the best and simple explanation .
Thank you so much, it helped a lot! Great video and explanation! (Greetings from Brazil!)
Thanks for the easy and understandable explanation
this is an awesome explanation. Thank you very much.
Thank you - this was easy to understand.
best explanation!!!!!! may god bless you
thank you so much !! 😄 ... awesome video 👍
Very clear, thank you so much!
thanks for the amazing explanation!
Awesome explanation easy to understand , animations are great to follow along.Liked 👍and subscribed
That's a fantastic explanation. re watching BFS for my job interview. thanks mate.
why the fuck do you need to know that shit for a job interview. Is the interviewer gonna give you a algorithm exam.
@@CloroxBleach-hi6jd Plenty of job interviews go over your data structure and algorithms knowledge...
@@ade1819 That's bullshit, if you have the degree than you've taken the class. Fuck algorithms anyway, coding is fun but algorithms are confusing shit
@@CloroxBleach-hi6jd this is why companies don't hire you
@@hungp9227 I haven't applied dumbass, retarded companies will want you to answer their stupid fucking algorithm questions and give you a job that has nothing to do with algorithms. That's why algorithms are shit
Thank you bhai! I am grateful for your teachings
Hey, important little thing: krep some padding at the bottom becos of the sub. I watch videos with subs, and i could not see the bottom of the graph.
Aaaand, cool video :)
I could listen to your voice all day
this video is a miracle of learning
Just keep it up. Nice videos
Great video!
Do you mind explaining how the for loop in the reconstructPath method works?
Specifically,
for(at = e; at != null; at = prev[at])
How is this being updated to continue thru the loop?
Thanks again, William!
Yeah, the prev array at index i (i.e prev[i]) contains the index of the node used to get to node i. To reconstruct the path we work backwards from the end node 'e' until we reach the start node. The start node does not have a parent so that's why we have 'at != null' as the end condition. Each iteration of the loop you trace back one node, this is 'at = prev[at]'.
@@WilliamFiset-videos Thanks William! Really appreciate the reply! Keep up the great work!!
@@WilliamFiset-videos thanks I also got stuck there
@@bl4ck21 In the first iteration, at =e. In the second iteration, at = prev[at]. Each time, at is incrementally progressed to prev[at].
Should not the reconstructPath function definition have ( if at == s { break; } ) in the for loop?
Thank you, this was very helpful!
I am late to the Party but i want to say: Great Tutorial! Exactly what i needed!
Best explanation!
Awesome video - thank you!
Best explanation
brilliant video thanks
Thanks! You're godsend!
Best of the best! thank you
Great videos. Thank you so much.
thank you sir very helpful but if you talk about algorithm analysis more it would be better.
Thank you sir🙏
Your videos are the best on graph theory!
beautiful explanation :)
One of the best!
Cant thank enough for this !!!
This is awesome
The visited queue would contain ALL of the neighbors that were visited, right?
How would simply reversing the visited queue give you the shortest path? There would be visited neighbors in the queue that were not along the shortest path. How do you prune out those suboptimal neighbors?
Holy crap the queue example is perfect
Thank you!
very helpful!
someone i can understand thank god
Thanks!
What if there are multiple shortest path for s to e? And I want to retrieve all of them.
we need an order, right ? it goes like we start from the smallest number to the biggest or backward, am i right ?
Hi, i have a doubt. Since the values are marked from 0-12, graph.get(node) works perfectly considering the node value is the index value. What if the values aren't like this? Instead of graph.get(node), do we run a for loop to find? Please help & Nice video btw. :)
you can map the node value while constructing the the graph using adjacency list or adj matrix.
thank you!!
Thank you! Thank you! Thank U!!!!!!!!!!!
I love these ones that focus on the actual useful abstraction instead of trying to explain it concretely in mathematics. If I didn't understand the abstract, I wouldn't be studying computer science! Stop putting the cart before the horse!
what tool do you use to make these diagrams?
The first half was totally understandable. and the other half... also understandable
Why do we start at 9 after 0? would we not start at 7? how do we determine the order things are added to the queue
When adding the root node's neighbours to the queue, why does it not go in an order (e.g. smallest to largest or vice versa). Is this algorithm just trying to visit every node in the graph as quick as it can?
The algorithm will try to explore the entire graph in a breadth first manner. The order in which you add the roots neighbors to the queue doesn't matter for exploration purposes
@@WilliamFiset-videos right, thank you 👍
you are a legend
thank you
u r the best
Awesome videos william.
can you maybe discuss this problem.
there are 'n' nodes and 'm' edges in a graph.
each node may or may not contain certain number of a item.
all nodes have same item but different number of that item.
we have to go from source to destination in minimum time collecting 'k' number of this item.
each edge is weighted,weights may or may not be same.
there are no self loops.
edges are bidirectional.
I'm not sure i'm going to cover that problem per se but can you provide a link to the problem?
It was nice uptill midway, You didn't show, via diagram, the reconstruct path method logic. What happens after 3:00 ?
great Video!
Hello! Why don't you check neighbours for null here 5:42?
Hi! Thanks for the explanation - I'm confused if the algorithm still works if the start node is the very first node in the queue. Because if you try to reconstruct the path using prev then it will exist because the first one in prev in null however that's the one we're looking for and path[0] won't be s. Not sure if I explained it well - hope you can clear my confusion. Thanks again!
I also have the question
awesome
How do we implement this on a weighted graph?
How do u create suuch presentation
tysm
I didn't get it how path recreation in your code sample helps to find shortest path, looks like you just traverse it back as it was stored but there could be multiple ways to reach the same cell on the way, especially in case with diagonals and its not evident in your code how you address such issue. I am not seeing it in area about writing into the prev table and not at area where the previous node is read from it. So basically it should be dijkstra.
Excellent video! Just a question. The prev array will contain ALL the visited nodes. I can not see how the reconstruct method will return the fastest path. Can anyone explain please?
True, the prev array contains all nodes, but we're only reconstructing the shortest path between s and e. When we reconstruct the path we begin at e and add the node we used to get to e when we did the BFS (this is prev [e]), then we do the same thing and add prev[prev[e]] to shortest path and so on until we reach s. This will not visit all nodes -- except in the worst case (e.g your graph is a a straight line)
@@WilliamFiset-videos Hi, this is a little bit late, but I am having trouble understanding how we know which node was the one that led to e, when "prev" seems to hold all the nodes?
@@gruuvy8067 The BFS search creates what is called a "BFS tree". The root is the starting node s, and the edges in the tree represent that from a node we visited another node. "prev" maps each node to its parent in the BFS tree. By starting at a node e and following the sequence of parents in the BFS tree, we arrive at the start node s in the shortest number of steps.
@@gruuvy8067 In the prev array, you start with searching for the value of the e'th (e is the ending node) index, this value is the node preceding e in the shortest path from s to e. Use that value as the next index to search for in the prev array and so on till you reach the start node s.
@@roberthoffenheim7861 why not come to a grinding halt when you hit the end node in function 'solve' - instead of doing all nodes in the try, which seems inefficient
YOU BEAUTIFUL MAN!
Around 4:50 you mention "value at index i". Sorry, what is the index i? Just trying to understand
5:27 shouldn't you add the node you just dequeued to the visited list, so that it won't get added to the queue again in the following iterations?
We have marked it as visited before starting the while loop
Just a question, why not make prev a hash table? and then we can even get rid of visited. If the presence of a node is in the prev table, then it's already been visited.
When you have a fixed number of elements which can be indexed an array serves as a faster hashmap with builtin indexing.
@@WilliamFiset-videos Cant we do this. Create a Hashmap. then put something like map.put(s, new LinkedList) and then track all visited in an Array. In this case we will be simply traversing. A bit of generic approach.
Thnxxx!!!!
Can you please help me...which tool you used for making graphs....I have to make them for my project and your diagrams are very clear 😀
Keynote
@@WilliamFiset-videos thank you so much
How do you know that you are following the shortest path when you reconstruct the path from e? What if there was more than one path to e? Wouldn't the last path to reach e be the one that is set in prev?
since e is put into the visited array, prev would not be overwritten. I also wondered why always the shortest path is found but since the algorithm is filling the search field from s to e, as soon as e is reached, it has to be the shortest path. all resulting paths are parallely searched on step further so the shortest path to e will always emerge.
@@silviogames So I interpret your explanation as that the FIRST path being found is the SHORTEST path. Is this correct? And this is achieved by the layering and queueing concept of BFS. The path found first is the path found at the lowest layer (closest to the source node).
@@An-wd9kk yeah. lets assume there exist 3 paths to the goal but the algorithm will always move one step at a time so the first that wins has to be the shortest. the others will either be same length or longer
@@silviogames yes thank you for your answer.
@@silviogames I was trying to understand since two days and you exactly saved me. Thanks for explanation.
is the prev array like parents?
Complexity O(V + E) for directed graph, right? For undirected O(V + 2E). Correct me if I am wrong)
Big O takes care of the constants :)