CODEWITHSUNDEEP
python
Prakhar
Prakhar

Reputation: 3536

Writing a better recursive depth-first search in python

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?

Upvotes: 4

Views: 8609

Answers (3)

kuzand
kuzand

Reputation: 9806

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

Upvotes: 3

chutsu
chutsu

Reputation: 14103

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)

Upvotes: 3

Sebastian Paaske Tørholm
Sebastian Paaske Tørholm

Reputation: 50868

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.

Upvotes: 5

Related Questions