Python非遞歸深度優先搜索

我寫了一些代碼來識別二進制映像中的連接組件。我已經使用遞歸深度優先搜索。但是，對於某些圖像，Python遞歸限制是不夠的。儘管我將限制增加到了我的計算機上支持的最大限制，但程序對於某些圖像仍然失敗。我如何迭代實現DFS？或者還有其他更好的解決方案嗎？Python非遞歸深度優先搜索

我的代碼：

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.]]

來源

2017-06-21 Sibi

使用任務堆棧的調用的參數記錄到'dfs'需要執行，並彈出堆棧，直到什麼都不剩在裏面，在一個循環。 –

好的。我假設我會在dfs函數的最後一行插入堆棧，取代遞歸調用。我會在哪裏彈出堆棧並執行必要的操作？ – Sibi

讓我找到我的答案，我重新編碼迭代遞歸洪水填充：有：https://stackoverflow.com/questions/40963288/fatal-python-error-cannot-recover-from-stack-overflow-during-flood填充 –

有位置列表訪問
使用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))

來源

2017-06-22 00:59:31

Python非遞歸深度優先搜索

回答

相關問題