younger younger - 4 months ago 52
Python Question

dfs to implement a graph, python

I was trying to implement a graph using dfs in python to find all the possible path from 'A' to 'F'.
The graph is:

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


And the following is my code:

def dfs_path(graph,start,end):
res = []
dfs(graph,start,end,[],res)
return res
def dfs(graph,start,end,path,res):
path+=[start]
if start == end:
res+=[path]
elif not graph.has_key(start):
return
else:
for node in graph[start]:
if node not in path:
dfs(graph,node,end,path,res)
print dfs_path(graph,'A','F')


by process the print, I did not get what I want, but instead, I get
[['A', 'B', 'D', 'E', 'F', 'C']]


Can anyone tell me what's wrong with my code, and if is possible, I would like to know the correct way to write this code with the same format.
Thanks

Answer

The basic problem is that there is only one path. When you make the recursive call to dfs, it modifies path. When the call returns, it does not restore the old value of path. The way around this is to pass a copy of path to dfs. Note the path[:] in the recursive call.

The second problem is that when you do find a path, you are concatenating it with res, whereas you actuall want to append it to res.

In the code below, I have eliminated the check on whether start is a key in graph. There is no way it could have been passed to the function without being a key in graph.

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

def dfs_path(graph,start,end):
    result = []
    dfs(graph,start,end,[],result)
    return result

def dfs(graph,start,end,path,result):
    path+=[start]
    if start == end:
        result.append(path)
    else:
        for node in graph[start]:
            if node not in path:
                dfs(graph,node,end,path[:],result)
print(dfs_path(graph,'A','F')) 

This prints

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

which looks right to me.

I would say that you got the function basically correct, but you need to review technicalities of python lists (and probably mutable data structures in general.)