the best explanation I 've seen fo far. Simple, clear, and focus without redundant words. Saving a lot of time. Love it and subscribed

@shadmansudipto7287

3 жыл бұрын

Agreed

@alnnvk3186

3 жыл бұрын

@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!

You turned 2 hours of confusing lectures into a simple 7 minute video. Thank you!

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.

Good explanation. That queue drawing finally helped me get it.

Wow this is by far the most understandable explanation of this concept that I've seen. Thank you!

Crystal clear explanation. Many implementation details well covered!

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 have saved my academic.

Best Explanation and Representation for BFS topic on KZread...

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

This was extremely useful. Thanks! Keep working this way!

Currently implementing this "in the wild". Good to see that the "right" way to do it is pretty much what I figured out

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!

thanks man, amazing video. so straightforward and useful!

Quality vids.. Subscribed. Thanks for your time and effort!

Best explanation possible. Thanks a lot!

Thank you very much William. You are the best!

The best video about BFS I've watched! Thanks I already understand it! :D

Great video! Thaaanks for the clear explanation.

Very clear, thank you so much!

Your animation just clicked it for me. Awesome :)

Awesome video - thank you!

Thank you - this was easy to understand.

Very good explanation and it is nice that you added pseudocode !!!!

This is the best explanation I've seen so far. Thank you!

Thank you so much, it helped a lot! Great video and explanation! (Greetings from Brazil!)

thank you so much !! 😄 ... awesome video 👍

That's a fantastic explanation. re watching BFS for my job interview. thanks mate.

@CloroxBleach-hi6jd

4 жыл бұрын

why the fuck do you need to know that shit for a job interview. Is the interviewer gonna give you a algorithm exam.

@ade1819

4 жыл бұрын

@@CloroxBleach-hi6jd Plenty of job interviews go over your data structure and algorithms knowledge...

@CloroxBleach-hi6jd

4 жыл бұрын

@@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

@hungp9227

4 жыл бұрын

@@CloroxBleach-hi6jd this is why companies don't hire you

@CloroxBleach-hi6jd

4 жыл бұрын

@@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 explanation easy to understand , animations are great to follow along.Liked 👍and subscribed

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

this is an awesome explanation. Thank you very much.

this video is a miracle of learning

Thank you bhai! I am grateful for your teachings

thanks for the amazing explanation!

best explanation!!!!!! may god bless you

I could listen to your voice all day

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!

@WilliamFiset-videos

5 жыл бұрын

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]'.

@VOLTDOGmusic

5 жыл бұрын

@@WilliamFiset-videos Thanks William! Really appreciate the reply! Keep up the great work!!

@bl4ck21

3 жыл бұрын

@@WilliamFiset-videos thanks I also got stuck there

@softwarecraftsman3091

Жыл бұрын

@@bl4ck21 In the first iteration, at =e. In the second iteration, at = prev[at]. Each time, at is incrementally progressed to prev[at].

Thanks for your time sir ...the best and simple explanation .

Should not the reconstructPath function definition have ( if at == s { break; } ) in the for loop?

Thank you, this was very helpful!

Best explanation!

Thanks for the easy and understandable explanation

I am late to the Party but i want to say: Great Tutorial! Exactly what i needed!

what tool do you use to make these diagrams?

This is awesome

Great videos. Thank you so much.

Cant thank enough for this !!!

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!

someone i can understand thank god

brilliant video thanks

Thanks! You're godsend!

Thanks!

Holy crap the queue example is perfect

thank you sir very helpful but if you talk about algorithm analysis more it would be better.

One of the best!

Thank you! Thank you! Thank U!!!!!!!!!!!

What if there are multiple shortest path for s to e? And I want to retrieve all of them.

beautiful explanation :)

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 :)

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. :)

@arvindojha1101

4 жыл бұрын

you can map the node value while constructing the the graph using adjacency list or adj matrix.

very helpful!

How do we implement this on a weighted graph?

Your videos are the best on graph theory!

Best of the best! thank you

The first half was totally understandable. and the other half... also understandable

Thank you!

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!

@lokingfai5805

Жыл бұрын

I also have the question

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

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?

we need an order, right ? it goes like we start from the smallest number to the biggest or backward, am i right ?

Thank you sir🙏

Just keep it up. Nice videos

thank you!!

tysm

How do u create suuch presentation

Best explanation

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?

@siddharthshukla4338

2 жыл бұрын

We have marked it as visited before starting the while loop

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.

@WilliamFiset-videos

6 жыл бұрын

I'm not sure i'm going to cover that problem per se but can you provide a link to the problem?

At 2:07, why is 9 visited first instead of 7?

is the prev array like parents?

you are a legend

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.

@WilliamFiset-videos

5 жыл бұрын

When you have a fixed number of elements which can be indexed an array serves as a faster hashmap with builtin indexing.

@thefreakingmindistaken

4 жыл бұрын

@@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.

Is there any order for the queue ? Can i add 7 then 11 then 9 for example ? thx

@WilliamFiset-videos

3 жыл бұрын

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

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?

@WilliamFiset-videos

4 жыл бұрын

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)

@gruuvy8067

4 жыл бұрын

@@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?

@nmamano

4 жыл бұрын

@@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.

@roberthoffenheim7861

2 жыл бұрын

@@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.

@sector1734

2 жыл бұрын

@@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

thank you

Am I missing something or did this not actually talk about how to get the shortest path from BFS? Or did I just lose track? I followed the initial visualization (very helpful) but that didn't show the shortest path right?

@euclid9492

3 жыл бұрын

If you look in reconstructPath towards the end around @7:00 and observe that first for loop closely, it starts at the end node, records it and goes to its parent in prev, then it calls that parents prev until null and the only one that should have null listed in prev is the original node s. So by only jumping from child to parent, from end to start this IS the shortest path once we reverse it.

@An-wd9kk

3 жыл бұрын

@@euclid9492 I don't understand your "only jumping from child to parent" argument. It only implies that the path is non-cyclic or straightforward. It does not imply shortest path. Both path a->b->c and a->d->f->c satisfy that we jump from parent to child, but the former is clearly the shorter path.

@euclid9492

3 жыл бұрын

@@An-wd9kk That is correct if we are only looking at the reconstruct path function. What we need to remember though, is how we mapped the child to parent INITIALLY in the phase before that. We check a nodes immediate neighbors first so there is no way to get shorter than that. Once a node is visited, it’s parent is recorded and will not be overwritten. Because of this, sure a longer path could exist, but because of the way we stepped out checking immediate neighbors first, the path that we get will be guaranteed to be the shortest path. I had to follow this out on a whiteboard before it clicked, if you have time, I’d recommend doing the same! Hope that clears it up a bit.

@louisconstant8214

3 жыл бұрын

@@euclid9492 Thank you

@richirossel329

Жыл бұрын

@@euclid9492 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.

u r the best

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?

@WilliamFiset-videos

8 ай бұрын

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

@Junglemunky

8 ай бұрын

@@WilliamFiset-videos right, thank you 👍

It was nice uptill midway, You didn't show, via diagram, the reconstruct path method logic. What happens after 3:00 ?

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

@WilliamFiset-videos

4 жыл бұрын

Adding and removing from the queue is O(1). I think you're confusing a queue with a priority queue.

@jubjubfriend64

4 жыл бұрын

@@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!!

Complexity O(V + E) for directed graph, right? For undirected O(V + 2E). Correct me if I am wrong)

@roberthoffenheim7861

2 жыл бұрын

Big O takes care of the constants :)

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 😀

@WilliamFiset-videos

Жыл бұрын

Keynote

@curiousmind2330

Жыл бұрын

@@WilliamFiset-videos thank you so much

Can this search algorithm be used on weighted graphs? If not, what else can be used?

@Liam_The_Great

Жыл бұрын

If there aren’t any negative weights you can use Djikstra’s algorithm. If there are negatie weights, you can use Bellman-Ford

Animation for path memorizing/reconstruction would be highly appreciated