Python:questions about my dfs code

Question

here are my python code for dfs path search:

class Graph(object):
   def __init__(self,dict=None):
       Graph.node = dict if dict != None else {}
   def add_node(self,nodedict):
       self.node = dict(self.node,**nodedict)
   def traversal_dfs(self,start,target,path = []):
       path = path + [start]
       for vertex in self.node[start]:
           print path,vertex,target
           if vertex == target:
               return path + [vertex]
           elif vertex not in path:
               path = self.traversal_dfs(vertex,target,path)
if __name__ == "__main__":
    g = Graph({'a':['b','c'],'b':['c','e'],'c':['d'],'d':['e'],'e':['f','a'],'f':['b']})
    print g.traversal_dfs('a','f')

But when I run it, I got errors like that:

Traceback (most recent call last):
  File "/Users/zzzyui/PycharmProjects/python_test/Traversal.py", line 25, in <module>
['a'] b f
    print g.traversal_dfs('a','f')
['a', 'b'] c f
['a', 'b', 'c'] d f
['a', 'b', 'c', 'd'] e f
  File "/Users/zzzyui/PycharmProjects/python_test/Traversal.py", line 19, in traversal_dfs
['a', 'b', 'c', 'd', 'e'] f f
    path = self.traversal_dfs(vertex,target,path)
stop flag
None e f
  File "/Users/zzzyui/PycharmProjects/python_test/Traversal.py", line 18, in traversal_dfs
    elif vertex not in path:
TypeError: argument of type 'NoneType' is not iterable

I wonder why the condition vertex == target does not work and how to fix it?

As seen in the Traceback, ```elif vertex not in path:``` is the line causing the problem. Seems ```path``` is None. [Catch the exception](https://docs.python.org/3/tutorial/errors.html#handling-exceptions) and in the except suite, inspect ```path``` and anything else that may be relevant - printing is a good start. — wwii, Jul 29 '17 at 15:08
```def __init__(self,dict=None):``` ... You shouldn't use variable names that shadow Python keywords or builtins. — wwii, Jul 29 '17 at 15:13
```def traversal_dfs(self,start,target,path = []):``` [mutable default arguments](https://stackoverflow.com/q/1132941/2823755) can give you headaches. — wwii, Jul 29 '17 at 15:17

score 1 · Answer 1 · answered Jul 29 '17 at 15:17

1

you should add a return statement in elif statement. for e.g return path

answered Jul 29 '17 at 15:17

Pritam Pan

133
7

Like ```return self.traversal_dfs(vertex,target,path)``` intead of ```path = ...```? – wwii Jul 29 '17 at 15:20

Python:questions about my dfs code

1 Answers1