younger - 6 months ago 72

Python Question

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.)