Breadth First Search Algorithm | Shortest Path | Graph Theory
ฝัง
- เผยแพร่เมื่อ 28 เม.ย. 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 TH-cam:
www.udemy.com/course/graph-th...
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!
You're one of the few explaining it with an end node and path reconstruct. Thank you!
I appreciate the effort you put into making these tutorials man. You are the best.
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.
You turned 2 hours of confusing lectures into a simple 7 minute video. Thank you!
Good explanation. That queue drawing finally helped me get it.
Crystal clear explanation. Many implementation details well covered!
Best explanation ever, hope to see more videos like this from you William! Keep up the good work
You have saved my academic.
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
Best Explanation and Representation for BFS topic on TH-cam...
This was extremely useful. Thanks!
Keep working this way!
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.
You are a legend! Best explanation ever!
Best explanation possible. Thanks a lot!
The best video about BFS I've watched! Thanks I already understand it! :D
Your animation just clicked it for me. Awesome :)
Currently implementing this "in the wild". Good to see that the "right" way to do it is pretty much what I figured out
Quality vids.. Subscribed. Thanks for your time and effort!
thanks man, amazing video. so straightforward and useful!
Great video! Thaaanks for the clear explanation.
This is the best explanation I've seen so far. Thank you!
Very good explanation and it is nice that you added pseudocode !!!!
Awesome explanation easy to understand , animations are great to follow along.Liked 👍and subscribed
Thank you very much William. You are the best!
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
I could listen to your voice all day
Thank you - this was easy to understand.
Thank you so much, it helped a lot! Great video and explanation! (Greetings from Brazil!)
Very clear, thank you so much!
best explanation!!!!!! may god bless you
Thanks for the easy and understandable explanation
thank you so much !! 😄 ... awesome video 👍
this video is a miracle of learning
Thanks for your time sir ...the best and simple explanation .
I am late to the Party but i want to say: Great Tutorial! Exactly what i needed!
thanks for the amazing explanation!
Thank you bhai! I am grateful for your teachings
brilliant video thanks
Best explanation!
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
Awesome video - thank you!
beautiful explanation :)
Thank you, this was very helpful!
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].
Holy crap the queue example is perfect
thank you sir very helpful but if you talk about algorithm analysis more it would be better.
Just keep it up. Nice videos
Great videos. Thank you so much.
This is awesome
Best explanation
Cant thank enough for this !!!
Best of the best! thank you
The first half was totally understandable. and the other half... also understandable
One of the best!
Thanks! You're godsend!
someone i can understand thank god
Your videos are the best on graph theory!
Should not the reconstructPath function definition have ( if at == s { break; } ) in the for loop?
very helpful!
Thank you sir🙏
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 :)
great Video!
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!
Thank you!
you are a legend
u r the best
Thank you! Thank you! Thank U!!!!!!!!!!!
thank you!!
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?
YOU BEAUTIFUL MAN!
thank you
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 👍
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.
What if there are multiple shortest path for s to e? And I want to retrieve all of them.
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?
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
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
Thnxxx!!!!
what tool do you use to make these diagrams?
Hello! Why don't you check neighbours for null here 5:42?
we need an order, right ? it goes like we start from the smallest number to the biggest or backward, am i right ?
tysm
awesome
How do we implement this on a weighted graph?
Animation for path memorizing/reconstruction would be highly appreciated
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
How do u create suuch presentation
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.
It was nice uptill midway, You didn't show, via diagram, the reconstruct path method logic. What happens after 3:00 ?
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
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
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.
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 :)
Can you explain why it's not O(nlogn + m)? is it because each time you add or remove a node from a queue it's logx time (rather than logn)? so you're effectively doing n number of logx operations which round down to n number of primitive operations? ... like log(|Q|) < log(N) < N
Adding and removing from the queue is O(1). I think you're confusing a queue with a priority queue.
@@WilliamFiset-videos Right! sorry I was somehow only thinking of priority queues (binomial and binary heaps) forgot about the properties of a simple linear queue! Thanks a bunch William!!
I think this one could use a little bit better explanation at the start. DFS is pretty obvious and intuitive but this one left me kind of wondering exactly how a BFS gets you the shortest path.
Do it with an example, it'll be much more clearer.
I completely agree. It took me a while to realize that when constructing the prev array we're basically calculating the shortest path to any given node in the graph from the start one.
@@jomalomal Everything is probably right in the video but i don't understand what happens (or rather how the right thing would happen) when a node has multiple parent nodes, as only one parent node is is saved in the prev list? And after the first parent node is saved, the "kid" node won't be visited anymore to save any other parent nodes.
Is there any order for the queue ? Can i add 7 then 11 then 9 for example ? thx
The queue will be ordered by layer, but the nodes of any particular layer can appear in any order, so if you start at 0, in the next layer it's valid to add 7, 11 and then 9
explanation is ok code is complicated
is the prev array like parents?