Writing a better recursive depth-first search in python

Question

I'm trying to build a graph library in python (along with standard graph-algorithms). I've tried to implement DFS and this is what it looks like

def DFS(gr, s, path):
    """ Depth first search 
    Returns a list of nodes "findable" from s """
    if s in path: return False
    path.append(s)
    for each in gr.neighbors(s):
        if each not in path:
            DFS(gr, each, path)

This is working fine but I'm not happy with how it needs to be used. E.g. currently you need to do this

 path = []
 DFS(mygraph, "s", path)
 print path

Instead of this, I want to DFS to be used in this manner

path = DFS(mygraph, "s")
print path

With the recursive DFS, I am unable to come up with the implementation that works like above. Can someone give me some pointers on how can I achieve this?

score 4 · Accepted Answer · answered Dec 04 '12 at 09:53

4

Just make a wrapper method that calls the one you already have:

def DFS(gr, s):
    path = []
    DFS2(gr, s, path)
    return path

Here DFS2 is the method you showed above.

answered Dec 04 '12 at 09:53

Sebastian Paaske Tørholm

49,493
11
100
118

@Prakhar: Learn it well because you're likely to encounter the need for many times. It's an example of the fundamental law of computer science at play which says that all problems can be solved with yet another level of indirection. – martineau Dec 04 '12 at 10:48

score 3 · Answer 2 · answered Mar 04 '14 at 19:06

3

Actually why don't you just set path to have a default of an empty list? So using your same code but slightly different arguments:

# Original
def DFS(gr, s, path):

# Modified
def DFS(gr, s, path=[]):

# From here you can do
DFS(gr, s)

answered Mar 04 '14 at 19:06

chutsu

13,612
19
65
86

1

I would definitely not recommend this solution. passing mutable objects as default arguments can result easily in unexpected behaviour. Check this out [Mutable Default Arguments](http://python-guide-pt-br.readthedocs.io/en/latest/writing/gotchas/). So better pass None as the default value for path and create a new empty path list if path is None. – 2006pmach Jun 17 '17 at 15:00
I think if you want to print afterwards you'd need the path variable – El Rakone May 16 '21 at 19:29

Andreas K. · Answer 3 · 2018-10-01T21:15:00.657

You can use an empty default value for the visited nodes, as suggested by chutsu, but be careful with using mutable default arguments. Also I would suggest using a set instead of a list for constant lookup.

def DFS(gr, s, visited=None):
    """ Depth first search 
    Returns a list of nodes "findable" from s """
    if visited == None:
        visited = set([s])

    for each in gr.neighbors(s):
        if each not in visited:
            visited.add(each)
            DFS(gr, each, visited)

    return visited

Writing a better recursive depth-first search in python

3 Answers3