If you are beginner in graph, watch his videos twice or thrice because then you will feel like no one can explain better than him and you will understand each and every point mentioned in the video. Thank you Sir for this playlist.
This is probably one of the most helpful 'Algorithms & Data Structures' channels I've yet encountered. The idea of maintaining multiple queues for each dimension is really handy.
Can you please explain why its better to have separate queues for each dimension? I cant see how its better than having one queue with the dimensions encapsulated into one object..
@@alikhansmt It's just a personal preference of mine. I've found this approach quicker to implement, and reuse over larger code structures, where I don't like to maintain a vast amount of structs, dot callbacks etc... Speaking in terms of competitive programming of course.
I was hammering about how to solve these ki9nd of problems. You are a savior! Please make these kind of tutorials more. I cannot thank you enough. Subscribed!
A lot of you are asking about how to reconstruct the path, so let me just explain it here. To reconstruct the path from the start to the end you need to maintain additional information, namely a 2D matrix which tracks the cell which was used to reach the current cell. Let me call this matrix "prev", short for previous. Every time you advance to the next cell, keep track of which cell you came from in the prev matrix. Once you reach the end of the BFS, start reconstructing the path by beginning at the end node in the prev matrix and work your way to the start node. The obtained path will be in reverse order, so you will need to reverse it. This is explained in more detail in the BFS video except that the prev matrix is 1D for the general case: ruclips.net/video/oDqjPvD54Ss/видео.html
@@austind649 Hi Austin, whenever we reach a '#' cell, that cell can not be visited as it's an obstacle so can not be in our path. so we don't need to process it and we need to find another path through a reachable cell. The whole point here is only go through the path that is reachable.
@@ss4036 Here is my code in C++, implemented by the williamfiset approach, which stores the the path and also shows BFS path taken in the matrix. pastebin.com/TeMDhspF
Hi, what about if you can move diagonally? Mine calculates the distance correctly and I had the path reconstruction working for the cardinal directions but once I add diagonal vectors then the path reconstruction works strangely. I know its probably hard to say without looking at my code but how do you modify the above algorithm to account for diagonal? Or should it "just work" if you add the new vectors?
this is exactly what i needed to know to solve graph problems, thanks for the video :) watching your tutorial for the first time, should have watched it earlier.
Your videos are amazing, but there is one possible improvement: run through the pseudo-code with the animation for the algorithm, so visualizing the pseudo-code becomes easier
Amazing explanation, thanks for the video! I've been always avoiding BFS and going with DFS since I wasn't comfortable with it, but not anymore! Subscribed to your channel... Will be waiting for more tutorials from you!
An alternative to using 'nodes_left_in_layer' and 'nodes_in_next_layer' variables is to store the distance/level along with the coordinates into your queue. It does have the downside of using an Object or Array to hold the coordinates and the level, but is easier to understand.
Good stuff, for my dumb brain it wasn't clear in the first glance why we needed the nodes_in_next_layer and nodes_left_in_layer and how it's used. Had to replay and follow through the algorithm to understand its use.
Try to think this way: BFS is visiting graph layer by layer. Initially the nodes_left_in_layer = 1; supposed that there're 2 adjacent nodes (A, B)connecting the starting node(S), so the nodes_in_next_layer will be incremented to 2 after the explorer_neighbours(), then the nodes_left_in_layer is decremented to 0. Here, we reset the nodes_left_in_layer to 2 and nodes_in_next_layer to 0 and increment the move_count to 1. It means after visiting layer 1, we are expecting to visit 2 nodes in layer 2. We can image node A has 3 adjacent nodes (C, D, E) and node B has 1 adjacent nodes (F). Now try to go-thru layer 2 with the imaginary graph - we visit A, nodes_in_next_layer is set to 3, nodes_left_in_layer is set to 1, then visit B, nodes_in_next_layer is set to 4 and nodes_left_in_layer to 0. Here, we are finishing visit layer 2 and expecting to visit layer 3 with 4 coming nodes. snap shots of queue: (S) (A) (B) // nodes_in_next_layer = 2, after visiting layer 1; (B) (C) (D) (E) // pop (A) and push all neighbours (C) (D) (E) (C) (D) (E) (F) // pop (B) and push neighbour (E) // nodes_in_next_layer = 4, after visiting layer 2; Hope this helps.
i think level would be better name compared to layer as BFS processes nodes which are at same level/distance from current node. Once we process all the nodes in current level, we move onto the next level. BFS is also called commonly referred to as level order traversal
@@jsarvesh yea, level is a much better name. I also find easier to code and understand passing an additional information into the object/struct of the queue, that is the level so when i push neighbors to the queue i increment this level/distance like this: q.push((position){.level=nextLevel, .row=nextRow, .col=nextCol, .distance=pos.distance + 1});
Very clear approach! Just would like to share something regarding using 2 queues for 2D Matrixes, it just affects the performance very badly single Queue implementation is much more efficient. Other than this, great explanation thanks.
Brilliant video, thank you so much for these. I think you could also modify solve() to return a prev collection as in the BFS Shortest Path video, and add the end cell coordinates or marker character ('E') as a parameter to the enclosing function. Then you no longer need all the global counting variables (nodes_left_in_layer etc). You would need to perform [number of steps in shortes path] iterations over prev to get the shortest path and return shortest_path.size() - 1. Maybe not optimal since you have to iterate over the shortest path too, but as long as you still break inside solve() when reached_end = True, the time complexity should stay the same.
I created a ArrayList variable to store the steps taken, but it store all the block the BFS explored instead of the green block that shown in the video. How can I only store the shortest block need to be explored only?
I also use two int arrays instead of an array of int,int objects. Before I was shy to tell about it because it is "not OOP". Now my design is backed by this video.
11:16 does this pseudo code applies for a 3d grid graph? im confused you mention to use 3 queues for 3ds grid graph and then went straight back to 2d pseudo code
What about the Robot Vacuum Cleaner problem, a double array 3x3 a robot is somewhere in the grid and in some cells there is dirt and the robot must find the optimal path in order to clean the cells and doing that with the BFS algorithm. Any suggestions?
Thanks for the multiple queue trick. Storing them as pairs does not scale well to higher dimensions and p.first and p.second looks really ugly and ambiguous.
Hi William, shouldn't the move count be move_count+1(if reached_end is true) as we are breaking the loop and not incrementing move_count for the last layer(where end node was found)?
You can using backtracking, however I wouldn't recommend it since it'll be quite slow. If you need a faster shortest path algorithm have a look at my Dijkstra video
Looking at the order of direction vectors which is (-1,0), (+1,0), (0,+1), (0, -1)...it looks like you are interested to move row wise first and then column wise. Then how does it become breadth first algorithm. As BFA says, we to move across the row first right.
Hi Shiva, it doesn't matter which direction vector is applied first because you're doing the BFS layer by layer and adding newly discovered nodes to the end of the queue.
That's exactly is my question.. how does this approach taking breadth first. With the use of vectors we go on finding the next node to traverse and looking at the these vectors, traversing need not be breadth wise. Because you are looking for next node above and below the current node first. I hope it makes sense.
Let me try and make this as clear as possible. For any given node, we add all the neighbors of that node to the list of nodes that need to be visited (unless the neighboring node has already been visited, is not traversable or something weird). The list of nodes to be visited is stored in a queue data structure. The queue has the property that the most recent node added to the queue is found at the end and the oldest node which has been in the queue the longest at the beginning. This means that we can add nodes to the queue and know that they will eventually get processed at a later stage. When the BFS starts you add the starting node to the queue to indicate that it should be visited. The algorithm begins by dequeuing (removing) the start node from the beginning of the queue, after which you add the left, right, down and up neighbors of the start node to the queue in that order (which shouldn't matter). Then the starting node's left node is first in the queue, so you add its left, right, down and up neighbors to the queue, then the starting node's right node if first in the queue, so you add its left, right, down and up neighbors to the queue, and etc... So the algorithm circles around if you will and the graph is explored layer by layer
Hi, I have a (maybe so stupid question). BFS cannot use as a shortest path finding with weighted graph right? (it just work with unweight - or all the edge have the same priority). I am not sure about this because at the video Overview, you said it can be use as shortest path finding algorithms. (But to my knowlege, it is impossible). Maybe i got mistake, thanks.
can someone please help me understand, why is it we choose BFS over DFS to find "shortest path" ? i believe it has to be the way BFS traverses a graph as compared to DFS, but looking for a better explanation
@@WilliamFiset-videos wow awesome! Could you please provide me with a hint or some advice as to how one can solve it? I've been struggling along time with it. My idea was to turn the grid into a graph and find the shortest path through it using the Dijkstra algorithm but this proved to be inefficient. How do you recommend one should solve this problem? Thank you!
@@WilliamFiset-videos thank you for the answer. But just to be a little more specific: if we go with the second alternative for instance, how would the algorithm look like (if you wouldn't mind explaining it briefly)? I imagine that I'd sort the grid ascending at first using (as you recommend) binary search and then apply the BFS algorithm. But how is that guaranteed to give me the path with the minimum height?
No sorting is required for approach #2. You need to binary search on the height h to determine the minimum height required. More specifically, during each BFS subroutine of the binary search iteration only take squares where the height is < h (
Am I the only one who missed the part where we select the path that he colored in green? What's explained in this video only shows how many steps we need to reach the end, but not the actual path.
thanks very useful video can someone please tell me how i can solve a maze that does not have walls (boundaries) which means a maze that allows wrapping
Hi Can someone please help me on this doubt. like if there are 2 routes from Cell Start to Cell End then how we are keeping track of steps for the 2 routes and taking minimum steps.
You will need additional information to do that. Maintain a 2D matrix which tracks the cell from which you came for every cell. Once you reach the end of the BFS, start reconstructing the path by beginning at the end node and work your way to the start node. The obtained path will be in reverse order, so you will need to reverse it.
![Blox Fruits Dragon Rework Update [Full Stream]](http://i.ytimg.com/vi/EqDAp8udhm0/mqdefault.jpg)
If you are beginner in graph, watch his videos twice or thrice because then you will feel like no one can explain better than him and you will understand each and every point mentioned in the video. Thank you Sir for this playlist.
YOU ARE A LIFE SAVER I COULD NEVER FIND A VIDEO LIKE THIS THANK YOU SO MUCH FOR THE GIFT YOUVE BESTOWED UPON THIS LAND
Finally, i'm waiting for this kind of tutorial
You're great dude
I rewrote your pseudocode in JavaScript adjusted it a bit to suit my needs. Worked perfectly right out of the box! Awesome work, William!
Can you share it?
@@saiffyros
// ruclips.net/video/KiCBXu4P-2Y/видео.html
// Globals
// number of rows and columns
const R = 10;
const C = 14;
// start cell values
const sr = 4;
const sc = 0;
// row and column queue
const rq = [];
const cq = [];
// save the directions found
const dir = [];
// variables to track the steps taken
let move_count = 0;
let nodes_left_in_layer = 1;
let nodes_in_next_layer = 0;
// variable to check if we've reached the end
let reached_end = false;
const map = {
cols: 14,
rows: 10,
sSize: 64,
tsize: 40
}
const gameGrid = [
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9, 0],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
[ 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0],
[ 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0],
[ 8, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0],
[ 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0],
[ 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0],
[ 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0],
[ 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
]
// R x C matrix of false values aka visited positions
const visited = [
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
]
// north, south, east, west direction vectors
const dr = [ -1, +1, 0, 0];
const dc = [ 0, 0, +1, -1];
function findPath(){
rq.push(sr);
cq.push(sc);
visited[sr][sc] = true;
// Keep going as long as there are items in the queue
while(rq.length > 0 || cq.length > 0){
let r = rq.shift();
let c = cq.shift();
if(gameGrid[r][c] === 'E'){
reached_end = true;
break;
}
check_neighbors( r, c)
nodes_left_in_layer --;
if(nodes_left_in_layer === 0){
nodes_left_in_layer = nodes_in_next_layer;
nodes_in_next_layer = 0;
move_count ++;
}
}
if(reached_end){
return move_count;
}
return -1;
}
function check_neighbors( r, c){
for(let i = 0; i < 4; i++){
let rr = r + dr[i];
let cc = c + dc[i];
//skip out of bounds cells
if(rr < 0 || cc < 0){
continue;
}
if(rr >= R || cc >= C){
continue;
}
// skip blocked or visited cells
if(visited[rr][cc]){
continue;
}
if(gameGrid[rr][cc] === 0){
continue;
}
let move = [dc[i], dr[i]];
dir.push(move);
rq.push(rr);
cq.push(cc);
visited[rr][cc] = true;
nodes_in_next_layer ++;
}
}
findPath();
function getTile(c, r){
return gameGrid[r][c];
}
export { dir, map, getTile };
This is probably one of the most helpful 'Algorithms & Data Structures' channels I've yet encountered. The idea of maintaining multiple queues for each dimension is really handy.
Can you please explain why its better to have separate queues for each dimension? I cant see how its better than having one queue with the dimensions encapsulated into one object..
@@alikhansmt It's just a personal preference of mine. I've found this approach quicker to implement, and reuse over larger code structures, where I don't like to maintain a vast amount of structs, dot callbacks etc... Speaking in terms of competitive programming of course.
@@brunokawka I see thanks!
William your explanation and animation creates a clear picture in my head about the underlying Concept, Thanks alot man!
Thank you William for the great video. Fellow Canadian here. thank you for the high-quality content!
This channel is a gem. very high quality content in these tutorial videos!
I was hammering about how to solve these ki9nd of problems. You are a savior! Please make these kind of tutorials more. I cannot thank you enough. Subscribed!
i love how slow you speak and how thoroughly you explain everything. thanks!
Best explanation for coding problems and approaches!! Thanks for making such high quality content on RUclips
A lot of you are asking about how to reconstruct the path, so let me just explain it here.
To reconstruct the path from the start to the end you need to maintain additional information, namely a 2D matrix which tracks the cell which was used to reach the current cell. Let me call this matrix "prev", short for previous. Every time you advance to the next cell, keep track of which cell you came from in the prev matrix. Once you reach the end of the BFS, start reconstructing the path by beginning at the end node in the prev matrix and work your way to the start node. The obtained path will be in reverse order, so you will need to reverse it.
This is explained in more detail in the BFS video except that the prev matrix is 1D for the general case: ruclips.net/video/oDqjPvD54Ss/видео.html
Hi William - @14:47, shouldn't we enqueue prior to "continue" on the # equality check? Otherwise certain positions would never be processed.
@@austind649 Hi Austin, whenever we reach a '#' cell, that cell can not be visited as it's an obstacle so can not be in our path. so we don't need to process it and we need to find another path through a reachable cell. The whole point here is only go through the path that is reachable.
Can you please share the code for saving the actual path along with the moves?
@@ss4036 Here is my code in C++, implemented by the williamfiset approach, which stores the the path and also shows BFS path taken in the matrix.
pastebin.com/TeMDhspF
Hi, what about if you can move diagonally? Mine calculates the distance correctly and I had the path reconstruction working for the cardinal directions but once I add diagonal vectors then the path reconstruction works strangely. I know its probably hard to say without looking at my code but how do you modify the above algorithm to account for diagonal? Or should it "just work" if you add the new vectors?
What a great tutorial! A great explanation complemented by incredibly clear slides and animations. Thanks.
I am preparing for IOI and this video was very Helpful, continue to make great contents like this. Thanks!
This is nice.I have seen this trick used by competitive programmers for traversing in the grid.
this is exactly what i needed to know to solve graph problems, thanks for the video :) watching your tutorial for the first time, should have watched it earlier.
Your videos are amazing, but there is one possible improvement:
run through the pseudo-code with the animation for the algorithm, so visualizing the pseudo-code becomes easier
Video for visualization!!
Watch till end for better visualization.
Used exactly same concept as explained!!
ruclips.net/video/EdJa84ymIXg/видео.html
Thank you so much, William, tons of good information in a very nice format
Amazing explanation, thanks for the video! I've been always avoiding BFS and going with DFS since I wasn't comfortable with it, but not anymore! Subscribed to your channel... Will be waiting for more tutorials from you!
Thanks a lot Will! This is from cracking the coding interview and your walkthrough is well explained. I'm subbing to your channel now
Great video. thank you very much. This is exactly what I needed to understand how to solve graph problem using adjacency matrix. Thank you once again!
excellent explanation. I particularly liked your concept for using direction vectors
You are just brilliant man! I hope your channel grows big!
An alternative to using 'nodes_left_in_layer' and 'nodes_in_next_layer' variables is to store the distance/level along with the coordinates into your queue.
It does have the downside of using an Object or Array to hold the coordinates and the level, but is easier to understand.
Thanks for this approach! Very intuitive indeed!
This is some of the best fucking content I've ever seen. Absolutely fucking incredible. 10/10 would peek again!
really like the summary in the end, as well. it's a nice touch.
My mind is blown at how many things can be modeled as a graph. I go out into the world and just see graphs now.
Bravo! you are one of a kind, keep rocking!!!
Good stuff, for my dumb brain it wasn't clear in the first glance why we needed the nodes_in_next_layer and nodes_left_in_layer and how it's used. Had to replay and follow through the algorithm to understand its use.
Try to think this way: BFS is visiting graph layer by layer. Initially the nodes_left_in_layer = 1; supposed that there're 2 adjacent nodes (A, B)connecting the starting node(S), so the nodes_in_next_layer will be incremented to 2 after the explorer_neighbours(), then the nodes_left_in_layer is decremented to 0. Here, we reset the nodes_left_in_layer to 2 and nodes_in_next_layer to 0 and increment the move_count to 1. It means after visiting layer 1, we are expecting to visit 2 nodes in layer 2. We can image node A has 3 adjacent nodes (C, D, E) and node B has 1 adjacent nodes (F). Now try to go-thru layer 2 with the imaginary graph - we visit A, nodes_in_next_layer is set to 3, nodes_left_in_layer is set to 1, then visit B, nodes_in_next_layer is set to 4 and nodes_left_in_layer to 0. Here, we are finishing visit layer 2 and expecting to visit layer 3 with 4 coming nodes.
snap shots of queue:
(S)
(A) (B) // nodes_in_next_layer = 2, after visiting layer 1;
(B) (C) (D) (E) // pop (A) and push all neighbours (C) (D) (E)
(C) (D) (E) (F) // pop (B) and push neighbour (E)
// nodes_in_next_layer = 4, after visiting layer 2;
Hope this helps.
i think level would be better name compared to layer as BFS processes nodes which are at same level/distance from current node. Once we process all the nodes in current level, we move onto the next level. BFS is also called commonly referred to as level order traversal
@@jsarvesh yea, level is a much better name. I also find easier to code and understand passing an additional information into the object/struct of the queue, that is the level so when i push neighbors to the queue i increment this level/distance like this:
q.push((position){.level=nextLevel, .row=nextRow, .col=nextCol, .distance=pos.distance + 1});
Very clear approach! Just would like to share something regarding using 2 queues for 2D Matrixes, it just affects the performance very badly single Queue implementation is much more efficient. Other than this, great explanation thanks.
Efficient in terms of memory complexity, right?
(Because handling so many queues in n-dimensional space would require a lot of memory I presume).
Thank you so much! You definitely have talent in explaining!
Brilliant video, thank you so much for these.
I think you could also modify solve() to return a prev collection as in the BFS Shortest Path video, and add the end cell coordinates or marker character ('E') as a parameter to the enclosing function. Then you no longer need all the global counting variables (nodes_left_in_layer etc). You would need to perform [number of steps in shortes path] iterations over prev to get the shortest path and return shortest_path.size() - 1.
Maybe not optimal since you have to iterate over the shortest path too, but as long as you still break inside solve() when reached_end = True, the time complexity should stay the same.
This is amazing ♥️
Please keep solving that kind of problems ♥️♥️😍
Best video on 2d Grid Thank You for the explanation
A fellow student from hyperskill, psted your video link. On the lee algorithm course conent.
It is helpful.
Thank you so much for simplifying it
This helped me so much you don't even know TYSM
Great buddy! Got it in the first go!
Such a great explanation!!
Now that I know the shortest path in value. How do i highlight the path it took.
Awesome video, thank you so much!
Amazing tutorial! Keep filming please :)
Quality content. Really appreciate it👍
Спасибо вам, за хорошее объяснение
thank you so much for these videos!
I didnt understand how r u calculating nodes left in layer and nodes in next layer
Same
8:36 I understand the "Fill" method to get all the tiles, yet how are you getting this path from that ?
keep with the good job!
Thank you very much. It helped me a lot.
Thank you.. this is helpful for making games as well
Thank you very much sir!!
Amazing video! Thanks a ton!
Awesome video!!! Thanks bro!
Great tutorial! Congrats
what happen if we are allowed to go in 8 direction diagonal also included then i think only BFS will not work anybody??
Could anyone explain what is the use of 'nodes_left_in_layer' and 'nodes_in_next_layer' variables?
Good explanation, thanks a lot
Brilliant ! Thank you :)
8:55 how do we find the number of steps without tracing the path itself?
I created a ArrayList variable to store the steps taken, but it store all the block the BFS explored instead of the green block that shown in the video.
How can I only store the shortest block need to be explored only?
what is the time complexity for this?
What do you mean by a 'layer'? (I am sorry if I missed it but I think its missing from the video)
I also use two int arrays instead of an array of int,int objects. Before I was shy to tell about it because it is "not OOP". Now my design is backed by this video.
11:16 does this pseudo code applies for a 3d grid graph? im confused you mention to use 3 queues for 3ds grid graph and then went straight back to 2d pseudo code
Man, wish I could see this before. Encountered this same problem in my First Round of Google Interview For Software Engineer.
Dude, their on site is all day variations of BFS problems, there's no hope lol
@@kickhuggy really? thats actually pretty cool lol
thanks it s really great bt how can I get the source code for this?
I don't understand the nodes left in layer and nodes in next layer part. Can someone link to a C++ solution to this problem using STL?
What about the Robot Vacuum Cleaner problem, a double array 3x3 a robot is somewhere in the grid and in some cells there is dirt and the robot must find the optimal path in order to clean the cells and doing that with the BFS algorithm. Any suggestions?
How is it possible to get returned the coords for the path? I dont think the queue in the end contains the path or my implementation is wrong.
Your videos are amazing, but how do I get the short path if reached end ?, because my move_count data has already been calculated
Thanks for the multiple queue trick. Storing them as pairs does not scale well to higher dimensions and p.first and p.second looks really ugly and ambiguous.
Hi William, shouldn't the move count be move_count+1(if reached_end is true) as we are breaking the loop and not incrementing move_count for the last layer(where end node was found)?
No. When reaching the layer containing the E, the step to get to that layer is already accounted for.
I was wondering how I can solve the same problem using DFS (bearing in mind I want to get any path not the shortest one)
You can using backtracking, however I wouldn't recommend it since it'll be quite slow. If you need a faster shortest path algorithm have a look at my Dijkstra video
THANK YOU!
Looking at the order of direction vectors which is (-1,0), (+1,0), (0,+1), (0, -1)...it looks like you are interested to move row wise first and then column wise. Then how does it become breadth first algorithm. As BFA says, we to move across the row first right.
Hi Shiva, it doesn't matter which direction vector is applied first because you're doing the BFS layer by layer and adding newly discovered nodes to the end of the queue.
That's exactly is my question.. how does this approach taking breadth first. With the use of vectors we go on finding the next node to traverse and looking at the these vectors, traversing need not be breadth wise. Because you are looking for next node above and below the current node first. I hope it makes sense.
Let me try and make this as clear as possible. For any given node, we add all the neighbors of that node to the list of nodes that need to be visited (unless the neighboring node has already been visited, is not traversable or something weird). The list of nodes to be visited is stored in a queue data structure. The queue has the property that the most recent node added to the queue is found at the end and the oldest node which has been in the queue the longest at the beginning. This means that we can add nodes to the queue and know that they will eventually get processed at a later stage. When the BFS starts you add the starting node to the queue to indicate that it should be visited. The algorithm begins by dequeuing (removing) the start node from the beginning of the queue, after which you add the left, right, down and up neighbors of the start node to the queue in that order (which shouldn't matter). Then the starting node's left node is first in the queue, so you add its left, right, down and up neighbors to the queue, then the starting node's right node if first in the queue, so you add its left, right, down and up neighbors to the queue, and etc... So the algorithm circles around if you will and the graph is explored layer by layer
Thanks for the detailed explanation ....
Sir, one doubt.
At first u said about using Adjacency List/Matrix.
Later u worked directly on the grid.
How to do it using Adjacency List/Matrix???
You can use a regular BFS with an adjacency list (or matrix), see ruclips.net/video/oDqjPvD54Ss/видео.html.
Ok, thank you sir
for the dungeon problem, why do we have to use bfs? why not dfs?
Hi, I have a (maybe so stupid question). BFS cannot use as a shortest path finding with weighted graph right? (it just work with unweight - or all the edge have the same priority). I am not sure about this because at the video Overview, you said it can be use as shortest path finding algorithms. (But to my knowlege, it is impossible). Maybe i got mistake, thanks.
is there a related leetcode problem to practice?
Your videos are amazing, really!
Can I know where do you run your animations, please?
They're slides. Linked them in the description.
can someone please help me understand, why is it we choose BFS over DFS to find "shortest path" ? i believe it has to be the way BFS traverses a graph as compared to DFS, but looking for a better explanation
How do we know that this algorithm gives the shortest path ?
I have one question about these can you help me please
can you explain why we use BFS algorithm? why you did not solve it by DFS or any other?
I could have solved this using DFS, but the BFS has the advantage that it'll find the shortest path because all edges are unweighted
@@WilliamFiset-videos but what if the cost of moving left, right and diagonal cell cost us. then which algo you will prefer?
@@luqmanahmad3153 Dijkstras algorithm. I also have a video on it.
What about uniform cost search? It will find cheapest path
Hello!
Have you solved the Muddy Hike problem from Kattis?
Indeed I have! The creator of that problem happens to be a very close friend of mine :)
@@WilliamFiset-videos wow awesome! Could you please provide me with a hint or some advice as to how one can solve it? I've been struggling along time with it. My idea was to turn the grid into a graph and find the shortest path through it using the Dijkstra algorithm but this proved to be inefficient. How do you recommend one should solve this problem? Thank you!
Modified Dijkstras I believe should work, or binary search + BFS too :)
@@WilliamFiset-videos thank you for the answer. But just to be a little more specific: if we go with the second alternative for instance, how would the algorithm look like (if you wouldn't mind explaining it briefly)? I imagine that I'd sort the grid ascending at first using (as you recommend) binary search and then apply the BFS algorithm. But how is that guaranteed to give me the path with the minimum height?
No sorting is required for approach #2. You need to binary search on the height h to determine the minimum height required. More specifically, during each BFS subroutine of the binary search iteration only take squares where the height is < h (
You are the best
This guy is insane
where can if find the video about tracing back the path?
I guess you're talking about backtracking technique which is used in the DFS method of maze solving
Am I the only one who missed the part where we select the path that he colored in green? What's explained in this video only shows how many steps we need to reach the end, but not the actual path.
what if we are allowed to take off one obstacle???
thanks very useful video can someone please tell me how i can solve a maze that does not have walls (boundaries) which means a maze that allows wrapping
Big like for you. Thanks a lot :))
Damn this was good
Hi Can someone please help me on this doubt. like if there are 2 routes from Cell Start to Cell End then how we are keeping track of steps for the 2 routes and taking minimum steps.
ok. Got it
Can you please share the link for the code, not able to find in your github link
I think there's only the pseudo code I show in this video. The previous video explaining generalized BFS has code though :)
thanks teacher but how i can get this code please reply
He includes the Github repo in the video description - github.com/williamfiset/algorithms
how do you show the path once its done?
hey could we get the complete source code file?
Something is missing from this solution: The shortest path. The function returns the shortest number of steps, but how do I find the actual path?
You will need additional information to do that. Maintain a 2D matrix which tracks the cell from which you came for every cell. Once you reach the end of the BFS, start reconstructing the path by beginning at the end node and work your way to the start node. The obtained path will be in reverse order, so you will need to reverse it.
I go over this in my previous video for general graphs: ruclips.net/video/oDqjPvD54Ss/видео.html
Thanks a lot