Python 非递归深度优先搜索

Question

我编写了一些代码来识别二进制图像中的连接组件。我使用了递归深度优先搜索。然而，对于某些图像，Python Recursion Limit 还不够。即使我将限制增加到计算机上支持的最大限制，程序对于某些图像仍然失败。如何迭代实现 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]

输入和输出:

[[0 0 0 0 1]
 [0 1 1 0 1]
 [0 0 1 0 0]
 [1 0 0 0 1]]
[[ 0.  0.  0.  0.  1.]
 [ 0.  2.  2.  0.  1.]
 [ 0.  0.  2.  0.  0.]
 [ 3.  0.  0.  0.  4.]]

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))