Need Help in improving recursive DFS implementation

Question

I am trying to implement DFS using recursion in Python I am not so good in python but trying to learn it by exploration and experience. The Following is the code I have designed based on my visualization



rowNums = [0, -1, 0, 1]
colNums = [-1, 0, 1, 0]


class Point():
    x:int
    y:int
    def __init__(self, x, y) -> None:
        self.x = x
        self.y = y

class Node():
    coordinates:Point
    distance:int
    def __init__(self, coords:Point, distance:int):
        self.coordinates = coords
        self.distance = distance

def isSafe(point:Point, nrow, ncol):
    if point.x>=0 and point.x=0 and point.y


This Code works, But I want to know, Have I used recursion correctly in my recurTillDeath function? Is there a better, more standardized approach to recur?
Edit: as I found solution to my original issue, Modified the question to ask for code improvement help

trincot · Accepted Answer

It looks fine, except for one thing:

DFS can return -1, None, or a non-negative distance. -1 is only returned when source or target are not cells with a 1-value. None is returned in all other cases where no path could be found. This means the main program will misinterpret the result when val is None.

For example, change the input maze such that there is no path by replacing a critical 1 to 0, and then run the program:

inputMaze = [[1, 0, 0, 0],
             [1, 1, 0, 1],
             [0, 1, 0, 0],
             [1, 0, 1, 1]]
#                ^-------------changed to zero

Then your code outputs:

Length of DFS path is: None

...while it really should say:

Path does not exist

It is better to avoid None returns, and also return -1 in those cases.

Not an error, but a code smell which could lead to errors in other circumstances: don't define attributes at the level of the class when you intend to use them as instance attributes. They have a different use and behaviour. In your code there is no negative effect, because in the constructors, you always define instance attributes with the same name, so there is no confusion. But the class members serve no purpose then.

All other remarks I could have are not errors, but just code review.

I post here a revised version of your code with comments on the changes I made:

from __future__ import annotations

class Point:
    # Remove class members
    def __init__(self, x, y) -> None:
        self.x = x
        self.y = y

    # With this, never worry about how to print a Point
    def __repr__(self):
        return repr((self.x, self.y)) 

    # Make this a method to facilitate navigation from Point to neighbor
    def add(self, point: Point):
        return Point(self.x + point.x, self.y + point.y)

# Use tuples for immutable data, all CAPS for constant names, and combine
# together what is related, which in this case can be Point instances:
DIRECTIONS = (Point(0, -1), Point(-1, 0), Point(0, 1), Point(1, 0))

# Node class is not needed, as distance can be managed 
# via argument and return value

# But use a class for managing the maze
class Maze:
    # Don't ask caller to pass values that can be derived (ncol nrow)
    def __init__(self, maze: list[list[int]]):
        self.maze = maze
        self.nrows = len(maze)
        self.ncols = len(maze[0])

    # Make this a method:
    def isSafe(self, point: Point):
        # Use chained comparisons and just return the result (it is boolean)
        # Also include the cell test
        return (0 <= point.x < self.nrows and 0 <= point.y < self.ncols
                and self.maze[point.x][point.y] != 0)

    # Use lowercase method name
    # By adding visited as parameter, we can use this function for recursion
    def dfs(self, src: Point, dest: Point, visited: list[list[bool]]=None):
        if self.maze[src.x][src.y] != 1 or self.maze[dest.x][dest.y] != 1:
            return -1
    
        if visited is None:  # First call (not recursive)
            # Populate visited without append:
            visited = [[False]*self.ncols for _ in range(self.nrows)]    

        visited[src.x][src.y] = True

        print(src)
        if src.x == dest.x and src.y == dest.y:
            print("Found it")
            return 0  # Distance is 0 -- will increase when backtracking
        else:
            for step in DIRECTIONS:
                newP = src.add(step)
                print(f"Neighbor: {newP}")
                # Comparing with True can be simplified 
                # Incorporate the cell's value check in `isSafe`
                if self.isSafe(newP) and not visited[newP.x][newP.y]:
                    val = self.dfs(newP, dest, visited)  # Use dfs itself
                    if val >= 0:  # Don't work with None
                        return val + 1  # Add the one here! No need for Node.
        return -1  # Always return number


if __name__ == "__main__":
    inputMaze = [[1, 0, 0, 0],
                 [1, 1, 0, 1],
                 [0, 1, 0, 0],
                 [1, 1, 1, 1]]

    src  = [0, 0]
    dest = [3, 3]

    # Create maze instance once, allowing multiple dfs calls if wanted
    maze = Maze(inputMaze)
    # Can unpack using asterisk
    distance = maze.dfs(Point(*src), Point(*dest))

    if distance == -1:
        print("Path does not exist")
    else:
        print("Length of DFS path is: ", distance)

Need Help in improving recursive DFS implementation

Answers (1)

Related Questions