CODEWITHSUNDEEP
pythonrecursiondepth-first-search
samol
samol

Reputation: 20570

How to turn a iterative DFS into a recursive DFS?

I have written an iterative DFS by implementing a stack. Now I am trying to write the same DFS recursively and I am running into the problems.

My question is, when I write it iteratively, I can keep certain global variables, such as paths=[] and I will add into it as I find a new path.

The thing I am confused about the recursive approach is that, there are basically two sets of results that I want to keep track of:

1) Recursively visit nodes to find new paths 2) Each time I find a new path, I want to add that to a list of paths which is then returned.

So my recursive function is now written such that it returns a single path at the base case and it returns a list of paths at the end of the function.

What is a better way to write this?

Runnable Python Script here:

https://ideone.com/ekfFDP

Code here:

graph = {'A': ['B', 'C'],
         'B': ['A', 'D', 'E'],
         'C': ['A', 'F'],
         'D': ['B'],
         'E': ['B', 'F'],
         'F': ['C', 'E'],
         'G': ['K']}


def push(array, item):
    array.insert(0, item)

def pop(array):
    return array.pop(0)

def dfs_paths(graph, start, goal):
    paths = []
    stack = [(start, [start])]

    while stack:
        (vertex, path) = pop(stack)
        vertices = graph[vertex]

        for next_vertex in (set(vertices) - set(path)):
            new_path = path + [next_vertex]

            if next_vertex == goal:
                paths.append(new_path)
            else:
                push(stack, (next_vertex, new_path))

    return paths

print dfs_paths(graph, 'A', 'F') # [['A', 'C', 'F'], ['A', 'B', 'E', 'F']]

def dfs_paths_rec(graph, start, goal, path=[]):
    if start == goal:
        path.append(start)
        return path

    paths = []
    for next in set(graph[start]) - set(path):
        new_path = dfs_paths_rec(graph, next, goal, path + [next])
        paths.append(new_path)

    return paths

print dfs_paths_rec(graph, 'A', 'F')

# [[[[[['C', 'A', 'B', 'E', 'F', 'F']], []]], ['C', 'F', 'F']], [[[['B', 'A', 'C', 'F', 'F']]], [['B', 'E', 'F', 'F']], []]]

Upvotes: 2

Views: 1058

Answers (2)

jamesdarabi
jamesdarabi

Reputation: 290

Try something like this:

def all_paths_dfs(graph, start, end, path=None):
    if path is None:
        path = []

    path.append(start)
    all_paths = set()

    if start == end:
        all_paths.add(tuple(path))
    else:
        for neighbor in graph[start]:
            if neighbor not in path:
                all_paths |= all_paths_dfs(graph, neighbor, end, path)

    path.pop()
    return all_paths


if __name__ == "__main__":
    graph = {'A': {'B', 'C'},
             'B': {'A', 'D', 'E'},
             'C': {'A', 'F'},
             'D': {'B'},
             'E': {'B', 'F'},
             'F': {'C', 'E'},
             'G': {'K'}}

    print all_paths_dfs(graph, 'A', 'F')

Which returns:

set([('A', 'C', 'F'), ('A', 'B', 'E', 'F')])

Upvotes: 0

200_success
200_success

Reputation: 7582

To obtain the result as a flat list, you want to use list.extend() instead of list.append().

Upvotes: 1

Related Questions