recursive to iterative DFS python

Question

I am trying to convert recursive code to iterative. The task is to find the largest region (connected cells consisting of ones) in the grid.

The code is referenced from here: https://www.geeksforgeeks.org/find-length-largest-region-boolean-matrix/ I have tried using stack and a loop to replace recursion but it is not working

here is the code I have tried and it does not reproduce the same result as with recursive approach.

I have tested with

M = np.array([[0, 0, 1, 1, 0], [1, 0, 1, 1, 0], [0, 1, 0, 0, 0], [0, 0, 0, 0, 2],[0, 0, 0, 1, 0],[0, 0, 3, 0, 0]]) 

def DFS(M, row, col, visited): 
    rowNbr = [-1, -1, -1, 0, 0, 1, 1, 1]  
    colNbr = [-1, 0, 1, -1, 1, -1, 0, 1]  

    # Mark this cell as visited  
    visited[row][col] = True
    stack = [] 

    for k in range(8): 
        if (isSafe(M, row + rowNbr[k],  
                   col + colNbr[k], visited)): 

            stack.push(M[row][col])
            row = row + rowNbr[k]
            col = col + colNbr[k]
            for k in range(8): 
                if (isSafe(M, row + rowNbr[k],  
                    col + colNbr[k], visited)):
                    stack.push(M[row][col])

Could you maybe add the code of your trial and specify what you mean by "is not working"? — Michael Mitter
– Michael Mitter, Commented Jun 8, 2020 at 20:48

Michael Mitter · Accepted Answer · 2020-06-09 07:19:11Z

The general structure for DFS using a stack is

stack = [] # initialize Stack
visited = set() # initialize hash table for looking at visited nodes
stack.append(startNode) # put in the start node

while len(stack) != 0: # check whether there is anything in the To-Do list
   newNode = stack.pop() # get next node to visit
   if newNode not in visited: # update visited if this node has not been visited
      visited.add(newNode) 
   for neighbor in newNode.neighbors: # iterate over neighbors
      if neighbor not in visited: # check whether neighbors were visited
         stack.append(neighbor) # this node was not seen before, add it to To-Do list

In your case, it seems that your are not making the number of iterations dependent on whether there is an element left in the stack and your not getting the next element to visit from the stack since your not taking any elements out of it.

You could try the following:

def DFS(M, row, col, visited):
    rowNbr = [-1, -1, -1, 0, 0, 1, 1, 1]
    colNbr = [-1, 0, 1, -1, 1, -1, 0, 1]
    # initialize stack
    stack = [] 
    stack.append((row, col))
    while len(stack) != 0:
        row, col = stack.pop()
        if not visited[row, col]:
            visited[row, col] = 1
        # iterate over neighbors
        for k in range(8):
            if (isSafe(M, row + rowNbr[k], col + colNbr[k], visited)):
                row = row + rowNbr[k]
                col = col + colNbr[k]
                if not visited[row, col]:
                    stack.append((row, col))

This uses a tuple of (row, col) to mark positions and store them on the stack.

Collectives™ on Stack Overflow

recursive to iterative DFS python

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related