From the course: Python Data Structures and Algorithms

Code a breadth-first search in Python - Python Tutorial

From the course: Python Data Structures and Algorithms

Start my 1-month free trial

Code a breadth-first search in Python

“

- Now the time has come to code Breadth first search in Python. So this is chapter O six O three. And if you open up BFS.PY you'll see there's some template code. Now this is very, very similar to what we had with DFS. So we mentioned in the comments that we're using row column tuples on line five, we have the same imports, almost the same, except instead of the stack, we have queue being imported from queue_ll. And just a point of interest, notice that when we're importing from a module, we don't put .PY at the end of our file. So this is the queue_ll.PY file without the .PY being mentioned, that's how the inputs work. Then we have the same test, exactly the same as we had in DFS at the bottom. The only difference being that we're testing on a different maze. So if you were to go into mazes, you'd see that the maze here is slightly different. Mini maze BFS. I've said it to be the same maze that we looked at in the previous video when we were using the Grit Tracer App. So mini maze BFS is this one with just one black square on the top row. (mouse clicking) So everything else is the same. We have a blank function definition that we're going to complete. We have our imports and we have our tests. And you might be surprised at how similar this is actually to DFS. So let's make a start. We create a queue instead of a stack. Was queue then we own queue our start position. So queue.enqueue Okay, and that start is the argument that's being passed in on line 12. We're using to add to our key. And then predecessors, (keyboard clicking) is equal to a dictionary containing the key value pair start none to begin with. Then the main algorithm. So the deal is while the queue is not empty. So while not queue.is empty, these are all methods that we coded previously. So while not queue.is empty, although I don't want that underscore at the beginning, then I perform the following sequence of operations. I get a current cell. Current cell is equal to queue.dequeue. and you get used to the spelling after a while. It's very strange bit of spelling for queue and dequeue. And then we've got a current cell. So if that current cell is equal to our goal, then we're done. So we return the path produced by this function code to our helper function when it's code with our predecessors and I'll start and I'll goal. However, if we don't find it, then we need to check the other directions. So for direction (keyboard clicking) in up right down and left. Let me get our offset. So row offset and column offsets are equal to the offsets. That's from the help of fall, for our particular direction. (keyboard clicking) And then we get our neighbor. So our neighbor is equal to current cell zero, that's the row position plus row offset and our current cell, a one, that's our column, plus our column offset col, col offset. Okay, so we've got a neighbor and then we say, if is legal pos within our particular maze that we're considering this particular neighbor, if that's the case. And also if we haven't added it yet. So if it's undiscovered and neighbor not in predecessors. Then we on cue (keyboard clicking) the neighbor and we also update our predecessors. So predecessors for this neighbor are equal to our current cell. And again, try and match what we're doing here to what we did in the Grid Tracer App, because they are directly comparable. And if none of that succeeds, then we return none. That means we haven't been able to find a path using this algorithm on that particular maze. And then let's just tidy stuff up with code reformat code and see what happens when we run it. Okay. So there's no errors. That's a very good sign. I've commented out lines 40 and 41. So the first major we're testing is just a blank maze, created using this comprehension as exactly in the DFS video. And then here, let's just uncomment those and run it again. So control forward slash, control S to save control shift F 10 Okay, and this time we get a printout of our maze, just to kind of show us what's going on in the background. And the result there we've correctly asserted that it's going to be 0 0 1 0 1 1 1 2 2 2. And so we didn't get any assertion errors. And for tests three, we asserted that the path was going to be none because there was no viable path to a cell that was on our maze. So that's all working as expected. So there it is. The algorithm is surprisingly similar to Depth first search. And like I say, the only difference being we're using a different data structure in the background, but the same basic procedure, this section from line 17 to line 27 is almost identical to in the Depth first search. And there you have a Python implementation of Breadth first search.

Contents