younger - 1 year ago 178

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

Recommended for you: Get network issues from **WhatsUp Gold**. **Not end users.**

Answer Source

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