Python nicht rekursive Tiefe Erste Suche

Question

Ich habe einen Code geschrieben, um die verbundenen Komponenten in einem Binärbild zu identifizieren. Ich habe rekursive Tiefensuche zuerst verwendet. Für einige Bilder ist die Python-Rekursionsgrenze jedoch nicht ausreichend. Obwohl ich das Limit auf das maximale unterstützte Limit auf meinem Computer erhöhe, schlägt das Programm für einige Bilder immer noch fehl. Wie kann ich DFS iterativ implementieren? Oder gibt es eine andere bessere Lösung?

Mein Code:

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] 

Eingang und Ausgang:

[[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. eine Liste der Standorte haben
2. eine while-Schleife verwenden besuchen jeden Ort zu besuchen, ist es aus der popping Liste wie du es tust.

Wie so:

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