Python Non Recursive Depth First Search

Question

I have written some code to identify the connected components in a binary image. I have used recursive depth first search. However, for some images, the Python Recursion Limit is not enough. Even though I increase the limit to the maximum supported limit on my computer, the program still fails for some images. How can I iteratively implement DFS? Or is there any other better solution?

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

Input and Output:

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

use a task stack to record the parameters of the calls to dfs you need to perform, and pop the stack until there's nothing left in it, in a loop. — Jean-François Fabre
– Jean-François Fabre ♦, Commented Jun 21, 2017 at 19:15
Ok. I assume I would push into the stack in the last line of the dfs function, replacing the recursive call. Where would I pop from the stack and perform the necessary operation? — Sibi
– Sibi, Commented Jun 21, 2017 at 19:20
let me find an answer of mine where I recode recursive flood fill by iterative: there: stackoverflow.com/questions/40963288/… — Jean-François Fabre
– Jean-François Fabre ♦, Commented Jun 21, 2017 at 19:22
This is unrelated to your actual question, but none of your global statements are necessary. You don't need those if you're only accessing or mutating a global in-place. A global statement is only need if you want to be able to rebind the global name to a completely new value. — Blckknght
– Blckknght, Commented Jun 21, 2017 at 19:40
You can just increase the maximum recursion limit too. Just set it using import sys and then sys.setrecursionlimit(100000) or any other number. — Mikael
– Mikael, Commented Jun 21, 2017 at 19:44

Tadhg McDonald-Jensen · Accepted Answer · 2017-06-22 00:59:31Z

1

Have a list of locations to visit
Use a while loop visiting each location, popping it out of the list as you do.

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

answered Jun 22, 2017 at 0:59

Tadhg McDonald-Jensen

21.6k5 gold badges40 silver badges69 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Python Non Recursive Depth First Search

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related