From the course: Python Data Structures and Algorithms
Visualize breadth-first search in a grid - Python Tutorial
From the course: Python Data Structures and Algorithms
Visualize breadth-first search in a grid
- [Instructor] We are now going to trace the path, of Breadth-first Search for a small sample maze. So the initial configuration is very similar to what we had for Depth-first Search. We have our initial cell marked in blue, and our destination cell marked in green and then down in these text boxes we have our data structure, which in this case is a queue containing just the initial cell. And we also have a list of predecessors currently only containing A which has none as its predecessor because it's the initial cell. So let's begin our algorithm. First of all I dequeue so that means A comes off my queue. And I'm going to mark A in red now to show that it's actually been visited. Then I ask myself is this the goal? Well, it's not the goal. So I have to go into my loop which tells me I have to enqueue undiscovered neighbors, so that means D, that's the only one I can actually access from here. That goes onto my queue. And also I'm going to update the predecessors so D now has predecessor of A because that is where we came from on our grid. Then we may have to repeat until the queue is empty which it isn't yet So we then dequeue again, because there's just one item. It has to be D. We ask ourselves is that the goal? No, it isn't. So we have to get into our loop, which tells us we have to enqueue our undiscovered neighbors but first I'm just going to mark D in red to show that it's actually been visited. And then I'm going to enqueue the undiscovered neighbors so that means E and G go onto my queue. And I update the predecessors for E and for G. And just noticed that the predecessor is always going to be the current cell. That's how you determine what to do for your predecessor there. Then repeat until the queue is empty Well, it's not empty. So I have to take another item off of my queue but I have to be careful to make sure that I take the correct one. Now remember, we're using FIFO, first in first out. Which means E went in first so it has to be the first one that comes out. And in our implementation that means take it always from the left-hand side. So we're always dequeuing from the left-hand side. So E comes off. I mark it in red to show that it's been visited. I ask myself, is it the goal? No, it isn't. So I have to enqueue my undiscovered neighbors. That means enqueuing F and H. So, F goes onto my queue, H goes onto my queue and also update the predecessors. So F comes from E and H also comes from E and then repeat until the queue is empty. So now G comes off. It gets marked in red. I ask myself is it the goal? Is not the goal. However there's no undiscovered neighbors, so I can go straight back to the top and now I can dequeue F. Mark it in red, ask myself if it's the goal. And no, it isn't. So I'm going to enqueue undiscovered neighbors so I'm going to enqueue C, and I update the predecessors, C came from F, and I came from F. And I repeat until the queue is empty is not empty. So next off the queue is going to be H. I mark that in red, ask myself if it's the goal No, it isn't. And because there's no undiscovered neighbors, I can go straight back to the top of my algorithm, so I can now dequeue C. Mark that in red, ask myself is this the goal? No, it isn't. So we have to continue. So if there were any undiscovered neighbors, I'd be enqueuing them but there aren't so I can just get back to the top of my algorithm, I can, dequeue this time I'm going to be dequeuing I. So I mark it in red. I ask myself, is this the goal? And infact it is. So we are now done. Let's just consider briefly how these predecessors are helpful. So because we've kept track of where every new cell came from, we can actually go back through those predecessors to find our path. In the right hand text box here, I've actually written out the predecessors and showing you how the path can be derived. So we know that I came from F, which we know from our predecessors in this middle box. We know that F came from E, E came from D and D came from A. So if you want to actually determine the path, we just take the reverse order of those that came from A working backwards, ending up at I You can see the path in fact here is A, D, E, F, I that's A,D,E,F,I and I've marked that in green to show the path that this algorithm produced for this particular maze.
Practice while you learn with exercise files
Download the files the instructor uses to teach the course. Follow along and learn by watching, listening and practicing.