A brief introduction to algorithms — Maze problem and breadth-first search

This article originated from personal public account: TechFlow, original is not easy, for attention

In the LeetCode column last weekend, we described depth-first search and backtracking in detail, so today we continue this topic by talking about another branch of search algorithms, breadth-first search.

Our English is Breadth First Search, abbreviated as BFS. Depth First Search (DFS) is a Depth First Search. So if you’re reading my code or someone else’s code and you find a function called BFS or DFS, if you remember those acronyms, you’ll know what they mean.

DFS and BFS

Before we get into the concept of BFS, let’s review the concept of DFS for comparison.

From previous articles, we’ve seen that implementing DFS often requires the use of recursion. We need to iterate through all the current decisions in a recursion, and then recursively execute those decisions. If these decisions have an impact on future decisions, we also need to use backtracking to undo the current action after the decision traversal is complete.

So we have the template code for DFS:

def dfs(n):

    if n > depth:

        return 

    for i in decisions:

        do_decision(i)

        dfs(n+1)

        rollback(i)

Copy the code

Let’s say we have a tree and we need to walk through the tree. Obviously, since the tree is a tree of nodes, not a list, we can’t just loop through it. To avoid repetition, we need to traverse the tree in a certain order. The most common is to use DFS and BFS, so let’s look at how DFS solves this problem.

Using the template above, we can easily write:

def dfs(node):

    if node is None:

        return

    for child in node.childs:

        print(child)

        dfs(child)

Copy the code

Since we only need to traverse the nodes, the traversal process does not affect the subsequent traversal, so we do not need the rollback step. And trees are naturally structured, so we recurse in exactly the same order as the tree itself, going from parent to child. So no other processing is required.

Suppose we had a tree like this:

If I iterate over it using DFS, what order will I get?

The order is A->B->C->D->E->F->G->H.

Do you see a pattern? In fact, DFS is to go one way and then go back to go the other way. That is, when we are faced with multiple decisions, we prioritize going in a deeper direction.

Breadth-first search is the opposite of its logic, as you might expect from the literal meaning that BFS tends to make all of its current decisions first, meaning that it tends to go in the direction of breadth.

To take a very simple example, let’s say we play a game with multiple endings. Depth-first search is about playing until you’ve finished, and then changing your choices to get another outcome. Breadth-first search, on the other hand, saves the game as it faces a choice, runs through all the possibilities, then reads the save one by one and repeats the process.

So back to the tree traversal problem above, if it is BFS, the traversal order is obviously A->B->D->E->C->F->G->H.

Implementation method

Careful analysis reveals that DFS traverses the search tree vertically, while BFS traverses the tree horizontally. When we implemented DFS, we actually borrowed the system stack to store the state for us. Now when we need to traverse horizontally, recursion obviously doesn’t work, but we also need a data structure to store the state of the traverse, like a game archive.

If you look at this tree, node A has three branches B, D, and E. We can get these three nodes through node A. And then we’re going to go through each of these nodes, get all of their branches. That is, the order in which we traverse the three nodes of the BDE is the order in which we encounter it. We think of the storage state as being written to the container, and we think of it as being ejected from the container when we read, so the container should be first in, first out.

The stack is fifo so it’s not satisfying, and the queue is fifO, which is what we want. So BFS is implemented based on queues.

With queues in place, we can leave it to maintain state and focus on the logic of traversing individual nodes. Because the queue connects these nodes for us, when there are no elements in the queue, we are done traversing.

We write the template code:

queue = Queue()

while not queue.empty():

    state = queue.front()

    queue.pop()

    print(state)

    for new_state in state.new_states():

        queue.put(new_state)

Copy the code

It’s pretty simple, right? Once you use a queue, there’s no more than a few lines of code to traverse. There are many ways to implement queues. Once you understand the principle, it doesn’t matter which implementation you use, list or linked list. Python implements queues for us, so in Python3 it’s a queue, Python2 it’s a queue, so notice that. I’m using Python3, so it’s queue, and it’s easy to use:

from queue import Queue

que = Queue()

while not queue.empty():

    state = queue.get()

    print(state)

    for new_state in state.new_states():

        queue.put(new_state)

Copy the code

If you look at it, getting the element in the head of the queue and popping the element in the head, as I understand it, are really two operations. But in the queue library, merge them into one. When we use get to get the header element, it’s already out of the queue. Most of the time this is fine, but there are times when we might want to fetch first and then decide whether to get out of a column, so we can’t use the library. Consider inserting a pop-up deque with both ends, or implementing a list ourselves.

The key to the

If you hold the spirit of criticism and knowledge in the process of learning, there will be a question, that is, why do we invent two traversal methods? What is the use of learning BFS? Isn’t it nice that DFS recursive implementations don’t have to maintain their own data structures?

This is very important when you think about it, and if you don’t understand this, how do you know what algorithm to use when you have a problem in practice? Unfortunately, most textbooks don’t cover this, leaving it up to the reader to figure it out.

In fact, there is only one difference, which is that when we find the answer without ending the search, BFS can end early, while DFS often can’t.

There are actually two points to ending this problem early, but let’s look at one of the simpler ones: BFS implementations usually go through a while loop rather than using recursion. So, when we have found the answer, we can simply break out of the loop and end the loop prematurely. But DFS is more difficult. Some of you might say we can return in a recursive function, but isn’t that the same thing?

When we return in recursion, we can only exit from the current execution. When we return, we go back to the previous call. The search process is not complete. Here’s an example:

def dfs(n):

    if n > 20:

      return

    print(n)

    for i in range(n+1.50) :

      dfs(i)

Copy the code

When n =21, the condition n > 20 will be triggered to return, but after return, it will return to the position of the previous loop, and then I =21, 22…… 50 is still going to be executed. In other words, even though I return, the recursive process doesn’t end, it just ends at the current node. In the case of BFS, since we are traversing in a loop, we can just break the loop and end the BFS process.

Deep thinking

DFS and BFS are similar if we just want to search for an answer, or if we just want to get an answer. Although DFS can not directly exit the problem, but this is not completely impossible to solve, by introducing global variables and other methods, we can also disguised early exit, although a little more troublesome.

But if we’re looking for optimal answers, DFS often doesn’t work.

Let’s look at a classic example, and a classic use case for BFS, which is the maze problem.

# # # # # # # # # # #

#  S      #

#         #

#     # # #

#     #E# #

# # # # # # # # # # #

Copy the code

The picture above shows a very simple maze with S for the beginning and E for the end. # represents a fence, a position that cannot be reached. DFS and BFS are the same if we just ask if the maze has a viable solution. And from a coding convention, we might prefer to use DFS for backtracking.

But if we want to know the shortest path from start to finish, we basically have to use BFS.

The reason is simple, because when we find the destination through DFS, we don’t know if it is the shortest path. To find the shortest path, we can only record all the paths to the destination and return the shortest by comparing them. This is obviously unscientific, because we’re going through a lot of unnecessary states, which can be quite a lot in a single search problem. Since BFS is a horizontal traversal, when the end point is found, it must be the optimal solution. Therefore, it is enough to directly break the loop and return, avoiding a lot of unnecessary traversal.

That is to say, the ability to find the answer in the first place, and the fastest path to the answer, this is the biggest characteristic of BFS. This is the essence of why we use BFS in our problems.

Beginners tend to use DFS because they are not familiar with Queue, and lack an understanding of the nature of the two search algorithms, in addition to the principle of the algorithm itself, which is also very important.

Finally, we attach the code for the BFS maze:

from queue import Queue

from collections import defaultdict



que = Queue()

directions = [[0.1], [1.0], [0.- 1], [- 1.0]]

visited = defaultdict(bool)





def bfs(S, E, maze):



    # S is start, E is end

    # maze map

    # visited Records locations traveled

    n, m = len(maze), len(maze[0])

    que.push((S, []))

    visited[S] = True

    

    while not que.empty():

        position, states = que.get()

        if position == E:

            states.append(E)

            return states

        for xi, xj in directions:

            # copy, Python list is passed by reference, not using copy will cause an error

            cur = states.copy()

            x, y = position[0] + xi, position[i] + xj

            if 0 < x < n and 0 < y < m andmaze[x][y] ! =The '#' and not visited[(x, y)]:

                visited[(x, y)] = True

                cur.append((x, y))

                que.put(((x, y), cur))

              

    return []

Copy the code

This is the end of the introduction of BFS algorithm. In the LeetCode topic, we will introduce more usage of BFS based on specific topics. Those of you who are interested can look forward to it.

If you feel that something has been gained, please feel free to click on or forward, your help is very important to me.