了解python广度优先搜索算法

Question

[我正在尝试了解此“广度优先搜索” python实现，并且我理解我的评论中显示的大部分内容，但我在这里没有得到这一行：

for dx, dy in [(-1, 0), (0, +1), (+1, 0), (0, -1)]:
           a, b = current[0] + dx, current[1] + dy #Start searching in a random direction

           if maze.in_maze(a, b) and not maze.is_wall(a, b) and (a, b) not in parent: #Check to see if the coordinates that are searching is inside the wall is not a wall and not inside of parent
               parent[(a, b)] = current #?
               dist[(a, b)] = dist[current] + 1; #?
               queue.append((a, b)) #Add the coordinates to the end of the queue

完整的代码可以在这里找到，如果有任何注释错误，请随时致电我。我还是Python的新手，所以我不知道每一行的确切含义，但我有一个大概的主意。

from collections import deque #A double-ended queue, or deque, supports adding and removing elements from either end. Import this from collections

nodes = 0 #Initialise nodes with value 0


def solve(maze, start, end): #Solve function that takes in the maze, start and end points as arguments
   global nodes #Declare nodes as a global variable
   nodes = 0 #Set nodes value to 0

   queue = deque() #Set queue as a double ended queue
   parent, dist = dict(), dict() #Set parent and dist

   queue.append(start) #Add start point to the queue
   parent[start], dist[start] = start, 1

   while len(queue): #While there are items in the list
       current = queue.popleft() #Set current to the first thing in the queue from the left
       nodes += 1 #Increment nodes by 1

       if current == end: #If the current place is the end target then solution has been found and we can exit the loop
           break #Exit the loop

       for dx, dy in [(-1, 0), (0, +1), (+1, 0), (0, -1)]:
           a, b = current[0] + dx, current[1] + dy #Start searching in a random direction

           if maze.in_maze(a, b) and not maze.is_wall(a, b) and (a, b) not in parent: #Check to see if the coordinates that are searching is inside the wall is not a wall and not inside of parent
               parent[(a, b)] = current #Set later
               dist[(a, b)] = dist[current] + 1; #set later
               queue.append((a, b)) #Add the coordinates to the end of the queue

   if end not in parent: #If there is no solution
      return [] #Return an empty solution
   else: #Otherwise if there is a solution
      path = [] #Initialise path as an empty list
      while start != end: #While the starting point is not the end point, the solution has not be found so
          path.append(end) #Keep appending the end node to the path queue until they meet the condition
          end = parent[end] #Set end point to the position it is in the parent dictionary
      path.append(start) #Insert the starting point to the end of the queue
      path.reverse() #Reverse the path queue since the solution was found back to front
      return path #Return the final solution

Answer 1

parent[(a, b)] = current

用于存储您来到坐标current的位置来源的坐标（(a, b)）。哦，顺便说一句，这里的评论是错误的：

   for dx, dy in [(-1, 0), (0, +1), (+1, 0), (0, -1)]:
       a, b = current[0] + dx, current[1] + dy #Start searching in a random direction

应该是“在每个方向上一次搜索”。这里没有什么随机的。