我正试图在Python中使用递归实现DFS我不太擅长python，但我试图通过探索和经验来学习它。以下是我基于我的可视化设计的代码
rowNums = [0, -1, 0, 1]
colNums = [-1, 0, 1, 0]
class Point():
x:int
y:int
def __init__(self, x, y) -> None:
self.x = x
self.y = y
class Node():
coordinates:Point
distance:int
def __init__(self, coords:Point, distance:int):
self.coordinates = coords
self.distance = distance
def isSafe(point:Point, nrow, ncol):
if point.x>=0 and point.x<nrow and point.y>=0 and point.y<ncol:
return True
return False
def DFS(maze:list[list[int]],
src:Point,
dest:Point,
nrow:int,
ncol:int):
visited = []
if maze[src.x][src.y] != 1 or maze[dest.x][dest.y] != 1:
return -1
for i in range(len(maze)):
visited.append([False]*len(maze[i]))
visited[src.x][src.y] = True
def recurTillDeath(node:Node):
point = node.coordinates
if point.x == dest.x and point.y == dest.y:
print("Found it")
return node.distance
else:
print(str(point.x) + " " + str(point.y))
for i in range(0,4):
print("i Values for Point ("+ str(point.x) + " " + str(point.y) +") is "+str(i))
newP = Point(point.x+rowNums[i],point.y+colNums[i])
print(str(newP.x) + " " + str(newP.y))
if isSafe(newP,nrow,ncol) and maze[newP.x][newP.y] != 0 and visited[newP.x][newP.y] != True:
visited[newP.x][newP.y]=True
val = recurTillDeath(Node(newP,node.distance+1))
if val is not None:
return val
return recurTillDeath(Node(src,0))
if __name__ == "__main__":
inputMaze = [[1, 0, 0, 0],
[1, 1, 0, 1],
[0, 1, 0, 0],
[1, 1, 1, 1]]
src = [0, 0]
dest = [3, 3]
srcObject = Point(src[0], src[1])
destObject = Point(dest[0], dest[1])
val = DFS(inputMaze, srcObject, destObject, len(inputMaze), len(inputMaze[0]))
if val == -1:
print("Path does not exist")
else:
print("Length of DFS path is: ", val)
这个代码有效，但我想知道，我在递归TillDeath函数中正确使用递归了吗？有没有更好、更标准化的复发方法？
编辑：当我找到我原来问题的解决方案时，修改了这个问题以请求代码改进帮助
它看起来很好，除了一件事：
DFS可以返回-1、None或非负距离-只有当源或目标不是具有1值的单元格时，才返回1。在找不到路径的所有其他情况下返回CCD_ 3。这意味着当val是None时，主程序将误解结果。
例如，通过将关键的1替换为0来更改输入迷宫，使其没有路径，然后运行程序：
inputMaze = [[1, 0, 0, 0],
[1, 1, 0, 1],
[0, 1, 0, 0],
[1, 0, 1, 1]]
# ^-------------changed to zero
然后你的代码输出：
DFS路径的长度为：无
。。。而它真的应该说：
路径不存在
最好避免None返回，在这种情况下也要返回-1。
这不是错误，而是在其他情况下可能导致错误的代码气味：当您打算将属性用作实例属性时，不要在类级别定义属性。它们有不同的用途和行为。在代码中没有负面影响，因为在构造函数中，您总是定义具有相同名称的实例属性，因此不会出现混淆。但是班上的人没有任何作用。
我所能做的所有其他评论都不是错误，只是代码审查。
我在这里发布了你的代码的修订版本，并对我所做的更改发表了评论：
from __future__ import annotations
class Point:
# Remove class members
def __init__(self, x, y) -> None:
self.x = x
self.y = y
# With this, never worry about how to print a Point
def __repr__(self):
return repr((self.x, self.y))
# Make this a method to facilitate navigation from Point to neighbor
def add(self, point: Point):
return Point(self.x + point.x, self.y + point.y)
# Use tuples for immutable data, all CAPS for constant names, and combine
# together what is related, which in this case can be Point instances:
DIRECTIONS = (Point(0, -1), Point(-1, 0), Point(0, 1), Point(1, 0))
# Node class is not needed, as distance can be managed
# via argument and return value
# But use a class for managing the maze
class Maze:
# Don't ask caller to pass values that can be derived (ncol nrow)
def __init__(self, maze: list[list[int]]):
self.maze = maze
self.nrows = len(maze)
self.ncols = len(maze[0])
# Make this a method:
def isSafe(self, point: Point):
# Use chained comparisons and just return the result (it is boolean)
# Also include the cell test
return (0 <= point.x < self.nrows and 0 <= point.y < self.ncols
and self.maze[point.x][point.y] != 0)
# Use lowercase method name
# By adding visited as parameter, we can use this function for recursion
def dfs(self, src: Point, dest: Point, visited: list[list[bool]]=None):
if self.maze[src.x][src.y] != 1 or self.maze[dest.x][dest.y] != 1:
return -1
if visited is None: # First call (not recursive)
# Populate visited without append:
visited = [[False]*self.ncols for _ in range(self.nrows)]
visited[src.x][src.y] = True
print(src)
if src.x == dest.x and src.y == dest.y:
print("Found it")
return 0 # Distance is 0 -- will increase when backtracking
else:
for step in DIRECTIONS:
newP = src.add(step)
print(f"Neighbor: {newP}")
# Comparing with True can be simplified
# Incorporate the cell's value check in `isSafe`
if self.isSafe(newP) and not visited[newP.x][newP.y]:
val = self.dfs(newP, dest, visited) # Use dfs itself
if val >= 0: # Don't work with None
return val + 1 # Add the one here! No need for Node.
return -1 # Always return number
if __name__ == "__main__":
inputMaze = [[1, 0, 0, 0],
[1, 1, 0, 1],
[0, 1, 0, 0],
[1, 1, 1, 1]]
src = [0, 0]
dest = [3, 3]
# Create maze instance once, allowing multiple dfs calls if wanted
maze = Maze(inputMaze)
# Can unpack using asterisk
distance = maze.dfs(Point(*src), Point(*dest))
if distance == -1:
print("Path does not exist")
else:
print("Length of DFS path is: ", distance)