Python非递归深度优先搜索

Question

我写了一些代码来识别二进制图像中连接的组件。我使用递归深度优先搜索。但是，对于某些图像，Python递归限制是不够的。即使我将限制增加到计算机上支持的最大限制，程序仍无法处理某些图像。如何迭代地实现DFS？或者还有其他更好的解决办法吗？在

我的代码：

count=1
height = 4
width = 5
g = np.zeros((height+2,width+2))
w = np.zeros((height+2,width+2))
dx = [-1,0,1,1,1,0,-1,-1]
dy = [1,1,1,0,-1,-1,-1,0]

def dfs(x,y,c):
    global w
    w[x][y]=c
    for i in range(8):
        nx = x+dx[i]
        ny = y+dy[i]
        if g[nx][ny] and not w[nx][ny]:
            dfs(nx,ny,c)

def find_connected_components(image):
    global count,g
    g[1:-1,1:-1]=image
    for i in range(1,height+1):
            for j in range(1,width+1):
                    if g[i][j] and not w[i][j]:
                        dfs(i,j,count)
                        count+=1

mask1 = np.array([[0,0,0,0,1],[0,1,1,0,1],[0,0,1,0,0],[1,0,0,0,1]])
find_connected_components(mask1)
print mask1
print w[1:-1,1:-1]

输入和输出：

^{pr2}$

Answer 1

1. 列出要参观的地点
2. 使用while循环访问每个位置，并将其从列表中弹出。在

是这样的：

def dfs(x,y,c):
    global w
    locs = [(x,y,c)]
    while locs:
        x,y,c = locs.pop()
        w[x][y]=c
        for i in range(8):
            nx = x+dx[i]
            ny = y+dy[i]
            if g[nx][ny] and not w[nx][ny]:
                locs.append((nx, ny, c))