Recursive DFS into Iterative DFS with global state-CodePudding

Here is this graph algorithm that finds a path between two nodes in a DAG.

from typing import *
def find_path(graph: List[List[int]], start: int, end: int) -> List[int]:
    path = []
    def dfs(node):
        path.append(node)
        if node == end: return True
        for neighbor in graph[node]:
            if dfs(neighbor): return True
            path.pop()
        return False

    dfs(start)
    return path

I was wondering if this code could be turned into an iterative DFS.

Here is a sample input:

graph = [[1,2],[3],[3],[]]
start = 0
end = 3
find_path(graph, start, end)

CodePudding user response：

You could stack the node together with an iterator object that iterates its neighbors. Since your original code does not use visited flags (to avoid revisiting the same node), I will not use them here either:

def find_path(graph: List[List[int]], start: int, end: int) -> List[int]:
    stack = [[start, iter(graph[start])]]
    while stack:
        neighbor = next(stack[-1][1], None)
        if neighbor:
            stack.append([neighbor, iter(graph[neighbor])])
            if neighbor == end:
                return [node for node, _ in stack]
        else:
            stack.pop()

CodePudding user response：

Iteration requires a stack:

#  from https://stackoverflow.com/a/39376201/1911064
def dfs_paths(graph, start, goal):
    stack = [(start, [start])]
    visited = set()
    while stack:
        (vertex, path) = stack.pop()
        if vertex not in visited:
            if vertex == goal:
                return path
            visited.add(vertex)
            for neighbor in graph[vertex]:
                stack.append((neighbor, path   [neighbor]))
 
graph = [[1,2],[3],[3],[]]
start = 0
end = 3
path = dfs_paths(graph, start, end)

for i in path:
    print(i)

Here, stack entries are tuples combining a vertex and a partial path. Whenever a new node is pushed on the stack, the partial path of the previous node is extended by the new node.

Alternative with reduced memory consumption:

def dfs_paths(graph, start, goal):
    stack = [start]
    predecessor = [-1 for i in len(graph)]
    visited = set()
    while stack:
        vertex = stack.pop()        
        if vertex not in visited:
            if vertex == goal:
                return path
            visited.add(vertex)
            for neighbor in graph[vertex]:
                predecessor[neighbor] = vertex
                stack.append(neighbor)
    return predecessor