python - 递归到迭代 DFS python
问题描述
我正在尝试将递归代码转换为迭代代码。任务是在网格中找到最大的区域(由单元组成的连接单元)。
代码从这里引用:https ://www.geeksforgeeks.org/find-length-largest-region-boolean-matrix/ 我尝试使用堆栈和循环来替换递归,但它不起作用
这是我尝试过的代码,它不会重现与递归方法相同的结果。
我已经测试过
M = np.array([[0, 0, 1, 1, 0], [1, 0, 1, 1, 0], [0, 1, 0, 0, 0], [0, 0, 0, 0, 2],[0, 0, 0, 1, 0],[0, 0, 3, 0, 0]])
def DFS(M, row, col, visited):
rowNbr = [-1, -1, -1, 0, 0, 1, 1, 1]
colNbr = [-1, 0, 1, -1, 1, -1, 0, 1]
# Mark this cell as visited
visited[row][col] = True
stack = []
for k in range(8):
if (isSafe(M, row + rowNbr[k],
col + colNbr[k], visited)):
stack.push(M[row][col])
row = row + rowNbr[k]
col = col + colNbr[k]
for k in range(8):
if (isSafe(M, row + rowNbr[k],
col + colNbr[k], visited)):
stack.push(M[row][col])
解决方案
使用堆栈的 DFS 的一般结构是
stack = [] # initialize Stack
visited = set() # initialize hash table for looking at visited nodes
stack.append(startNode) # put in the start node
while len(stack) != 0: # check whether there is anything in the To-Do list
newNode = stack.pop() # get next node to visit
if newNode not in visited: # update visited if this node has not been visited
visited.add(newNode)
for neighbor in newNode.neighbors: # iterate over neighbors
if neighbor not in visited: # check whether neighbors were visited
stack.append(neighbor) # this node was not seen before, add it to To-Do list
在您的情况下,您似乎没有使迭代次数取决于堆栈中是否还有一个元素,并且您没有从堆栈中获取下一个要访问的元素,因为您没有从中取出任何元素。
您可以尝试以下方法:
def DFS(M, row, col, visited):
rowNbr = [-1, -1, -1, 0, 0, 1, 1, 1]
colNbr = [-1, 0, 1, -1, 1, -1, 0, 1]
# initialize stack
stack = []
stack.append((row, col))
while len(stack) != 0:
row, col = stack.pop()
if not visited[row, col]:
visited[row, col] = 1
# iterate over neighbors
for k in range(8):
if (isSafe(M, row + rowNbr[k], col + colNbr[k], visited)):
row = row + rowNbr[k]
col = col + colNbr[k]
if not visited[row, col]:
stack.append((row, col))
这使用一个元组(row, col)
来标记位置并将它们存储在堆栈中。
推荐阅读
- c# - 使用 OneDrive filePicker 访问数据
- image - docker镜像语法错误
- jenkins - 较新版本的 Artifactory 与 Jenkins Artifactory 插件有问题
- sql - 标签名称不正确
- vba - MS Access - VBA:使用表格中的电子邮件地址发送电子邮件
- android - 我无法检测到手机或模拟器上的长按
- python - 从 ESA Sentinel-2 产品在 python 中加载 RGB 图像并使用 openCV 保存
- java - 当应用程序安装在外部时,内部文件在哪里?
- spring-boot - @Group 注释中的 minOccurs 属性导致 UnexpectedRecordException
- c# - 如何从字节数组返回pdf